Do you know the maximum number of moves it takes to solve a Rubik’s Cube™? Well until recently, neither did anybody else. It turns out that any of the 43,252,003,274,489,856,000 possibly cube configurations can be solved in twenty moves or less. This result is rather astounding if you have ever had the pleasure of attempting to solve a cube. For many years people have pondered what the value of this maximum, lovingly termed God’s number. You can watch YouTube videos of young people competing in World Championship speed competitions and finishing the cube in mere seconds. However, they are employing solution algorithms of more than thirty steps and moving their fingers as fast as humanly possible. That is, they have memorized both mentally and with muscle-memory a certain sequence of moves that always solves a cube. Solution guides can be found all over the Internet, but it takes a lot of practice to get good enough to solve a random cube on your own.
Performing the analysis and determining algorithms to actually solve the cubes is another matter entirely. With such a large number of initial configurations, the work on proving the upper bounds on the number of moves required to reach a solved cube is relevant for many areas of computing and mathematics. That is likely what attracted the all-star cast of computer experts that harnessed the donated computing power of the Googleplex. It took the equivalent of thirty-five CPU-years worth of computing time, spread out across multiple server machines while idle, to run through the analysis work.
John Dethridge, Google engineer and former #1 ranked worldwide TopCoder coding competitor, was the man on the inside assisting Tomas Rokicki, Herbert Kociemba, and Morley Davidson. Tomas Rokicki is the founder and director of technology of the Palo Alto software company Instantis. While not contemplating the cube, Rokicki is really interested in cellular automata and even finds time to run marathons. Herbert Kociemba is a German math teacher and author of a program called Cube Explorer that not only lets you explore different cube states but also allows you to enter in a cube configuration and it will return the ordered steps to a solution. Unlike most software in this area, however, the solution returned is close to the optimal solution, often within one move. Morley Davidson is a mathematics researcher and associate professor at Kent State University.
When approached with a problem of such magnitude, it is impossible to naively allow the computer to try every possible move for every possible cube. Even if all the computers on the planet were used, this method would take an outrageously long time. Instead, computer scientists must be clever with how they can eliminate certain configurations based on things like symmetry. You can think of it this way. When you are describing the state of a cube, you start at a certain square and note the color and continue around in some specific direction to each of the other squares. However, if you rotate the cube in your hand either up, down, left, or right, and take down the state again, the two will be different. Are the cube states really different? Will they take different steps to solve? The answer is no. When it comes to having a minimal solution, both of those cubes are the same and have the same solution. The researchers that found God’s number were able to drastically reduce the number of cube positions that needed to be searched for their proof using these techniques. It still took a lot of other intelligent coding magic but they were able to reduce the processing time enough for their significant result.
The researchers have set up the following site for more information: http://www.cube20.org/. They plan to add software and other tools to help enthusiasts understand the methods they employed.
