Rubik's Cube Breakthrough
Written by Mike James   
Tuesday, 10 August 2010

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".

Banner

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.

cube

 

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...

 

Banner


Pico 2W Announced But There Is A Surprise!
25/11/2024

Raspberry Pi released the Pico 2 a few months ago and we have been waiting for the Pico 2W since then. But Pimoroni beat them to the draw with the Pico Plus 2W based on the RM2 radio module and hinted [ ... ]



Wasmer 5 Adds iOS Support
12/11/2024

The Wasmer team has released Wasmer 5.0. The WebAssembly runtime adds experimental support for more back ends including V8, Wasmi and WAMR. It also now has iOS support, and upgraded compilers includin [ ... ]


More News

<ASIN:B08DYBF1JJ>

<ASIN:B0759F54RC>

<ASIN:1593272162>

<ASIN:0553140175>

<ASIN:1402753136>

<ASIN:157912805X>

Last Updated ( Sunday, 07 July 2024 )