## The Cube of Rubik

Sorry about the goofy title.  I just watched Night at the Museum 2: Battle of the Smithsonian.

A team of mathematicians, engineers, and programmers, along with some heavy duty computing power from Google, recently “solved” the Rubik’s cube.  More precisely, they found “God’s number,” proving it to equal 20, as it has been conjectured to be since 1995.  The story can be found in quite a few places now, but I first read it here; much of the text appears to have been taken from a web site put together by the research team here.

“God’s number” is the name given to the maximum number of moves required to solve the cube from any starting configuration.  This number has been known to be at least 20 since 1995, when Michael Reid proved that a particular configuration, the “superflip,” required 20 moves.  What this latest team did was to show that God’s number is at most 20, by finding a solution for every possible configuration, each involving no more than 20 moves.

Note that they found a solution, not necessarily an optimal one, for each configuration.  I was at first confused by the table in the Daily Mail article, showing the number of cube configurations grouped by “distance” (in the cube graph) from the solved configuration.  The values from 16 to 20 moves are all approximate, such as “about 1,100,000,000,000,000,000.”  Why not just “1.1 quintillion”?  Why bother with an approximation when you still include all of the zeros?

The team’s web site explains why: they only found a solution involving 20 moves or less for all configurations, but since their solution was not necessarily optimal, they aren’t sure of the true “distance” from some of the configurations to the solved state.  (However, they are sure that whatever that distance is, it’s at most 20.)

Another question I had after reading the original article was also answered by the team’s web site.  What is meant by a “move”?  That is, does a move consist of just a quarter-turn of a single face, or are half-turns included as well?  This certainly affects the structure and thus diameter of the cube graph… and I would imagine that the choice of one or other convention might make some of the symmetry reductions much “cleaner” as well.  At any rate, this question can be answered by simply inspecting the second line of the table; the fact that 18 configurations are a single move away from the solved state implies that there are 3 possible moves for each of the 6 faces, which must include half-turns.

This entry was posted in Uncategorized. Bookmark the permalink.