Why is the number 20 God's Number? New research has proven that every possible position for the Rubik's Cube can be solved in 20 moves or less.
It's been 30 years since the Rubik's Cube first came to market. Created in 1974 by Hungarian sculptor and professor of architecture Erno Rubik, the colourful cube took the world by storm, and gave science an entertaining new problem to solve: What is the least number of moves required to solve every position on the Rubik's Cube?
Everyone who solves a Rubik's Cube uses an algorithm of sorts to do so, but humans are notoriously inefficient when compared to computers and all-powerful beings. Most human solutions to the more complete Rubik's positions require more than 40 moves.
So science set out to discover God's Algorithm: The most efficient algorithm for solving all of the cube's 43,252,003,274,489,856,000 positions. The worst-case number in God's Algorithm - the largest number of moves required to solve any position - is called God's Number.
And that number is 20.
While it's been whittled down over the years from around 80 in early solution booklets to 22 as of August 2008, a team of researchers using 25 CPU-years of processing time donated by Google have nailed the exact number.
So how did Kent State University mathematician Morley Davidson, Google engineer John Dethridge, German maths teacher Herbert Kociemba and California programmer Tomas Rokicki come up with their solution? I'll let them tell you.
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.
Armed with this knowledge, humanity should soon be able to cure cancer, solve world hunger, and finally document the female orgasm. It is a great day for science!
God's Number is 20 [Project Website]