God’s Number, the absolute number of moves by which any 3x3 Rubik’s Cubes can be solved (and I suppose any nxn if you want to get technical, although at the moment 3x3 is quite impressive), has been sought after for many years. Many have tried to find God’s Number but have only raised/lowered the upper and lower bounds of this problem. As of July 2010, this is now a closed problem! What is interesting about this result is that they used a brute force method to come up with God’s Number so God’s Algorithm was not found, just the number by which God’s Algorithm will have to abide. The site I linked above shows the computations that were done to arrive at this answer. They also have an analysis of which problems were the hardest with their methods.

There are different positions that the Rubik’s Cube can take on so from a computational standpoint, this was quite a feat! 35 CPU years were used in performing this computation. Not that bad for such a hugh problem actually! I would have expected a lot more. The only thing left now is to find God’s Algorithm which will solve any 3x3 Rubik’s Cube in 20 moves using only *one* method! I do not foresee this coming around anytime soon though…