God Has Spoken: Algorithm Reveals Secret Number for the Rubik's Cube

God Has Spoken: Algorithm Reveals Secret Number for the Rubik's Cube

By "God," I mean Morley Davidson, John Dethridge, Herbert Kociemba, Tomas Rokicki and about 35 CPU-years.

Ever since Erno Rubik conceived the Rubik's Cube in 1974, math-minded cubers have been trying to find the most efficient number of moves required to solve the 3x3 Rubik's Cube in any scenario, which they refer to as "God's Algorithm".  And in God's Algorithm, the maximum number of moves for the worst case scenario has finally been solved—

"God's Number" is 20.

20 may seem like a petty number, but not in context with the 43,252,003,274,489,856,000 possible permutations of the Rubik's Cube.

So, how did a Google engineer, a Kent State mathematician, a German math teacher and a Californian programmer crack the code?

• We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
• We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
• 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.

And I thought speedcubing was complicated!

The easiest and hardest permutations that the number-crunching program solved are pictured below.  The "Superflip" (left) was the first position ever found with 20 moves.  The hardest has no name (right), but brings back awful memories of a shattered puzzle box all over the floor.

       See the solution for these two in action!

"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."

Still don't get it?  The team of researchers have a website with all the information you need, including a history of God's Number.  And if you still don't get it after that, check out Tomas Rokicki's detailed explanation.

Or maybe just try solving a Rubik's Cube first, and then go from there.