Ebiquity Research Group
Institutional Group • 10 people
2

Researchers prove Rubics Cube solvable in 20 moves or less

Using a combination of mathematical tricks, good programming and 35 CPU-years on Google’s servers, a group of researchers have proved that every position of Rubik’s Cube can be solved in 20 moves or less. The group consists of Kent State mathematician Morley Davidson, Google engineer John Dethridge, math teacher Herbert Kociemba, and programmer Tomas Rokicki.

This is an amazing result and a testament to more than 30 years of work on the problem. The Cube was invented in 1974 and almost immediately the subject for programs to solve it. In 1981, Morwen Thistlethwaite proved that any configuration could be solved in no more than 52 moves. Periodically, tighter upper bounds for the maximum solution length were found. This result ends the quest — there are some configurations (about 300M) that require 20 moves to solve and there are none that require more than 20 moves.

In their own words, here’s how the group solved all 43,252,003,274,489,856,000 Cube positions:

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

This reminds me of the first program I wrote for my own enjoyment, which used brute force to find all solutions to Piet Hein’s Soma Cube. In 1969 I had a summer job as the night operator for an IBM 360 and I would turn off the clock to run my program so that the management wouldn’t know how much computer time I was consuming.

Here is an Java applet from the group showing one of the hardest positions to solve.


codebase="http://www.cube20.org/" archive="RubikPlayerFlat.jar" code="RubikPlayerFlat"
width="270" height="300"> value="FU-F2D-BUR-F-LD-R-U-LUB-D2R-FU2D2" />

See this BBC story more more information on this amazing result.

Visit Website