How to Solve a Rubik's Cube in Only 23 Moves

I've never solved a Rubik's Cube. I'm that guy who takes the stickers off puts them where I want them in order to get it over with. (Much to the consternation of any legitimate puzzle-solver who might try to use my cube in the future.) So it was with some amazement that I learned that Rubik's Cube solutions are an area of active mathematical research. There are scholars out there working on ideal cube-solving algorithms, and major progress is being made towards "God's algorithm" -- more on that in a moment.

Math god Tom Rokicki recently proved that all possible Rubik's Cube configurations can be solved in 23 turns or fewer. In order to arrive at this conclusion he needed massive computing power -- the research was done on supercomputers at Sony Pictures Imageworks (in the idle time between rendering special effects for Hollywood movies). Rokicki's conclusion states that for any legal Rubik's Cube configuration, a solution exists in 21, 22, or 23 moves. (And a few special-case cube configurations may be solvable in 20 or fewer.) Now the trick is...what are those moves?

Rokicki's research is interesting in that it doesn't actually tell you specifically how to solve a given cube (contrary to my catchy blog title above) -- it just proves that a solution exists for all possible legal cube configurations, and that solution is guaranteed to be achievable in 23 moves or fewer.

This research is one step in a process that may arrive at "God's algorithm," a theoretically ideal solution to a puzzle. From Wikipedia's page on the algorithm to end all algorithms:

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It stands for any practical algorithm that produces a solution having the least possible number of moves, the idea being that an omniscient being would know an optimal step from any given configuration. ...It is unknown whether a practical God's algorithm exists for Rubik's Cube.

Further reading: Rokicki's paper on 25-move solutions, a nice Slashdot explanation of the implications of the research, more on God's algorithm, and a highly math-intensive page on Optimal solutions for Rubik's Cube.