Rubik’s Cube God’s Number: 20
A mere thirty years after the Rubik's Cube craze died out, a team of math geeks has proven once and for all that the puzzle can be solved in 20 moves or less from any position.
A mere thirty years after the Rubik’s Cube craze died out, a team of math geeks has proven once and for all that the puzzle can be solved in 20 moves or less from any position.
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.
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.
The basics:
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.
- 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
Also interesting:
We have known for fifteen years that there are positions that require 20 moves; we have just proved that there are none that require more. 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.
I’ve still got my Cube from circa 1981. I learned a solution to it within a few months, performed it numerous times, and got bored with it.
Well, 20 moves or 1 ball-peen hammer.
Hell, and all this time I’ve believed the answer was 42.