With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves. We consider any twist of any face to be one move (this is known as the half-turn metric.)
Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube. One algorithm might use a sequence of moves to solve the top face, then another sequence of moves to position the middle edges, and so on. 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.
It took fifteen years after the introduction of the Cube to find the first position that provably requires twenty moves to solve; it is appropriate that fifteen years after that, we prove that twenty moves suffice for all positions.
By 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions. The first upper bound was probably around 80 or so from the algorithm in one of the early solution booklets. This table summarizes the subsequent results.
|Date||Lower bound||Upper bound||Gap||Notes and Links|
|July, 1981||18||52||34||Morwen Thistlethwaite proves 52 moves suffice.|
|December, 1990||18||42||24||Hans Kloosterman improves this to 42 moves.|
|May, 1992||18||39||21||Michael Reid shows 39 moves is always sufficient.|
|May, 1992||18||37||19||Dik Winter lowers this to 37 moves just one day later!|
|January, 1995||18||29||11||Michael Reid cuts the upper bound to 29 moves by analyzing Kociemba's two-phase algorithm.|
|January, 1995||20||29||9||Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves.|
|December, 2005||20||28||8||Silviu Radu shows that 28 moves is always enough.|
|April, 2006||20||27||7||Silviu Radu improves his bound to 27 moves.|
|May, 2007||20||26||6||Dan Kunkle and Gene Cooperman prove 26 moves suffice.|
|March, 2008||20||25||5||Tomas Rokicki cuts the upper bound to 25 moves.|
|April, 2008||20||23||3||Tomas Rokicki and John Welborn reduce it to only 23 moves.|
|August, 2008||20||22||2||Tomas Rokicki and John Welborn continue down to 22 moves.|
|July, 2010||20||20||0||Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge prove that God's Number for the Cube is exactly 20.|
|Random positions||Cosets of H|
|20 moves or less||3,900||1,000,000,000|
|Distance||Count of Positions|
Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result, which has since been independently confirmed by another researcher.
To date we have found about twelve million distance-20 positions. The following position was the hardest for our programs to solve:
Rubik's Cube is a registered trademark of Seven Towns, Ltd.
Thanks to Werner Randelshofer for use of the Cube applet on this page.