Every position in Rubik's cube can be solved in 20 moves or less. God's Number is 20.
Adam Rifkin stashed this in Hacker News!
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.
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.