A recent study by the Kent State University (OH) funded by Google, has proved that Rubik’s cube can be solved with 20 moves or less. Thanks to the help of Google – and the super computer they offered for the study – Morley Davidson, a mathematician from Kent State University, John Dethridge, an engineer at Google in Mountain View, Herbert Kociemba, math teacher from Darmstadt, Germany, and Tomas Rokicki, a programmer from Palo Alto, California, have been able to narrow down the upper bound of the number of moves needed to solve it.

The last upper bound had been set to 22 on 2008 by Tomas Rokicki and John Welborn.

The results can be read here, and these are a few details:

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.

We have known for fifteen years that there are positions that require 20 moves; we have just proved that there are none that require more.

Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result. We hope to have that independently confirmed by another researcher within the month.

To date we have found about twelve million distance-20 positions.

As a curiosity, this is – according to the authors – the hardest position to solve:

See ho to solve it at the authors website. Here, the news in Spanish.

Advertisements