Interesting (and not so interesting) problems
Rubik's Cube:
Rubik's Cubes are, in contrast to Sudoku puzzles, problems. They require a strategy to make choices from a number of non-trivial decisions. Recently I watched The Pursuit of Happyness starring Will Smith, with a scene involving solving the cube to impress an employer. I was intrigued -- I owned one as a child, but I completely forgot about the puzzle until I watched this movie. I decided to completely block any publicized solutions to the problem and asked my girlfriend if I could borrow her cube, and we started thinking about the mechanics.
The brilliance of the game is in its mechanics: For an hour, we both came up with different theories of how the corner pieces work. They cannot possibly be fully dependent on any of the layers in the 3 dimensions, and yet they are attached to something.
We both thought of 3 axis first. Her theory was that there are circular inner rails involved on which the corner pieces run (I later verified and her solution was correct and in fact the one used in the product) but for some reason I couldn't get my head around imagining the construction. I needed it to be simpler: a reduced mechanical problem. My 3D imagination doesn't keep a lot of information.
The first lemma I thought of was that if you have a small Rubik Cube inside a bigger Rubik Cube and then you attach each piece in one to the corresponding piece in the other using spikes, the construction would still function. It took more time to accept my own second lemma that a Rubik Sphere wouldn't be as strange mechanically as a Rubik Cube. In fact you can completely imagine a spheric one where each layer is attached to the construct using rails such as those around a Pringles chips cylinder lid -- but imagine that for each and every layer. Now if you put the first and second lemma together, you get a Rubik Cube with a Rubic Sphere center (by substitution) that works.
As for the game itself, I still haven't looked up a solution, and I'm trying to come up with an algorithm. I'm not sure yet whether it is possible to swap two pieces on the same face without replacing any other pieces in the net result. But if that is a possibility, the entire solution can be reduced to it: Since each 2 layers share an edge, the swap algorithm can be extended to be independent of layers through the use of a little bit of algebra. Once you can swap any piece with any other piece, all you need to do is to know where each piece goes. That is not difficult: according to the construction I described ealier, the center of each face of the cube cannot possibly move relative to the center. So the center of each face describes the color that face should have. That determines exactly which color to expect for any given co-ordinates. Pick the co-ordinate, decide what colors should the piece there have, find the misplaced piece with the disired colors, then "swap". Repeat for all co-ordinates that do not have their correct piece in place.
Will I come up with the swap algorithm itself? As soon as I get some free time, I will start thinking about it (today was a work day and last night I was up until 3:30 a.m. thinking) but I'm sure it will be a satisfying experience. Meanwhile, feel welcome to look up the solution from Wikipedia.
Sudoku puzzles:
Sudoku puzzles are not problems, they're incomplete solutions. At any state of the puzzle, there are deterministic and fully-recoverable transformations that get you to the next "more solved" state until you complete the solution. The space of the solutions based on the given values is very small.
The first time I saw a Sudoku puzzle, I ventured to write a program to automatically solve it. But as soon as I solved one myself I realized what most people who have tried it probably realize: the reason it is not an "interesting problem" has to do with the fact that at any decision node of the decision tree, at least one decision is completely deterministic and doesn't require further exploration; hence no "machine" learning is really involved.
This has 2 interesting outcomes: (1) Sudoku can be quite an addictive puzzle due to its nature: confirming our ability to make decisions in absence of risk, and (2) it can be an immensely valueable teaching tool to children because it keeps one of the variables (namely the seemingly-stochastic distribution of the decision values) pre-determined.
As for problem-solving value, I may move on to something more interesting. Say: the value of quantified indicators such as (1) the number of lines of code (2) the platform used (3) the skill-set of people (4) etc in predicting the relative performance of a final product. Another interesting problem is that my neighbor, who at times inspires me with her comments, took a look at this web site the other day and asked me "is it really English?"
I may have to rethink the niche audience factor.
The application gap:
My friend is a mathematics genius in the making who psychologically speaking, finds his sinful pleasures where no other would find sane enough to explore. Centuries ago he may have wanted to discover the North Pole, but in this day and age you'd find him describe a world named "Abstract", especially during quality times like our traditional trip to Montreal on new years. Shortly after I graduated, he wrote an abstract on "Primitive Galois Representations", which for me serves as a stark reminder that I use the word "sophisticated" too loosely. This year when he was talking about another abstract concept new to me, I asked him whether he saw any applications for his subjects of curiousity. He said yes; but those applications would serve abstract ends. Again there is this gap that oppresses the heart.
