God’s Number

Google helps prove the maximum number of moves that a perfect puzzle solver would require to solve any Rubik’s Cube position is 20.

Ever since it was invented in 1974, the quest for this God’s number has driven a few determined mathematicians and computer programmers. In 1981, the first realistic lower bounds and upper bounds were shown to exist—the minimum number stood at 18 moves and the maximum at 52. In 1995, it was first shown that the position given in the above picture requires a minimum of 20 moves to solve. Now a team comprising Tomas Rokicki, a programmer from Palo Alto, California, Herbert Kociemba, a maths teacher from Darmstadt, Germany, Morley Davidson, a mathematician from Kent State University, and John Dethridge, an engineer at Google in Mountain View, have finally shown that any position can be solved in 20 moves. Here is how they did it in their own words: 

“How did we solve all 43,252,003,274,489,856,000 positions of the Cube? 

»  We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each… Each of these subproblems was small enough to fit in the memory of a modern PC, and the way we broke it down allowed us to solve each set rapidly.

»  We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering… There are 24 different ways you can orient the same Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving. 

» We did not find optimal solutions to each position, but instead only solutions of length 20 or less. 

» We wrote a program that solved a single set in about 20 seconds… We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets. Finally, we were able to distribute these among a large number of computers at Google and complete the computation in just a few weeks.”

puzzleRubik’s Cube