Finally computers with a little help from math have managed to find out just how hard the Rubik Cube really is. It's a breakthrough that some are calling the "God Number".

To get straight to the point - the breakthrough is:

Every position of Rubik's Cube can be solved in twenty moves or less.

Or

the god number is 20

You need to think about this for a moment to realise the shocking truth of this assertion. No matter how much you shuffle the cube, no matter how long or how many devious twists you apply the cube can be returned to its original state in just 20 moves. So much apparent complexity is in fact simplicity. You need to remember this the next time you have been trying to solve the Cube for hours.

The tale of how this result was obtained is also fascinating. The smallest number of moves needed to solve the Cube is also known as "God's number" because it is the number of moves an all-seeing entity would take. The upper bound on this number has been slowly closing in on its lower bound for some time but now we know that any position can be solved in 20 moves or less. The way that the proof was arrived at may not please many pure mathematicians, however, as it was a pure fairly brute force approach.

The team partitioned the possible positions of the Cube into 55,882,296 cosets using symmetry and set covering. They then wrote a program that would solve a single set in about 20 seconds. The program looked for solutions that took less than 20 moves rather than finding the optimum solution in any case. After around 35 CPU years the program tested all of the sets and all could be solved in 20 or fewer moves. The computing time was provided by Google as a few weeks of idle time on its servers.

Without wanting to belittle the achievement - it's an impressive computational feat - the only clever math used was in partitioning the configurations using symmetry. The rest of the algorithm is pure exhaustive search. This is very similar to the way that many mathematical theorems are being proved using computers - the four-color theorem was proved using a similar procedure. The argument against this approach is that while the result is proven, no deep understanding of why it is true has been achieved.

In this case what has been proved is that there are no sets of distance more than 20 from the starting configuration (where distance is measured in moves). This seems all the more remarkable when you are told that there are 43,252,003,274,489,856,000 potential positions  The majority of solutions take between 15 and 19 moves to solve. There are only around 300,000,000 positions that require 20 moves to reach a solution.

Such complexity - such simplicity.

Of course there is always the 4x4 cube and then...

<ASIN:B08DYBF1JJ>

<ASIN:B0759F54RC>

<ASIN:1593272162>

<ASIN:0553140175>

<ASIN:1402753136>

<ASIN:157912805X>