God’s Algorithm

AFP, via Yahoo, reports that a team of researchers using assistance from Google has established God’s Algorithm for the Rubik’s Cube.  The coolness of this cannot be doubted.  The Rubik’s Cube can always be solved from any position in twenty moves or fewer.

An international team of researchers … has found every way the popular Rubik’s Cube puzzle can be solved, and showed it can always be solved in 20 moves or less … At the crux of the quest has been a bid to determine the lowest number of moves required to get the cube from any given muddled configuration to the color-aligned solution.

The statement from the research team says:

Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube … There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves.  One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this is known as God’s Algorithm. The number of moves this algorithm would take in the worst case is called God’s Number. At long last, God’s Number has been shown to be 20.

Update:  If you look at the comments, particularly those from Brian, you’ll see that this is way more complicated than I or the AFP article suggest.  What the team has done is far more limited than a true “God’s Algorithm.”  Thanks for the very interesting comments; I feel better about never having been very good with Rubik’s Cubes.