Leave it to Google to solve the Rubik's Cube mystery. What is the maximum number of moves required to solve the Rubik's Cube from any position? Since 1981 researchers have searched and narrowed the gap between the lower bound (God's number) and the upper bound number of moves required to solve the cube from any position. Researchers Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki have finally proven that God's Number for the Cube is exactly 20. What is the world record for solving the Rubik's Cube in an official competition? Netherland's Erik Akkersdijk did it at the 2008 Czech Open in 7.08 seconds. It took this guy just over seven seconds to solve the cube. It took researchers 35 CPU-years of borrowed idle Google computing time to finally prove God's Number was in fact 20 moves or less. There you have it folks. How did they discover God's number? Researchers explain:
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.
On other interesting news, researcher using Google's super computers have discovered what most internists have long suspected.
- There are 484,564,693,672,018,105,047,105,232 possible permutations of illness in the differential diagnosis of a hospital admission.
- There are 873,689,193,109,586,957,372,678,102 possible permutations of the Evaluation and Management rules required to accurately code every one of those possible permutations without being accused of fraud by the Medicare National Bank.
- Even Google was unable to assign any accurate level of coding to the correct permutation of illness.