Rubic’s cube solvable in 26 moves

August 13th, 2007

Rubic’s cubeNortheastern Computer Science PhD student Daniel Kunkle has proven that any configuration of a Rubik’s cube can be solved in 26 moves or fewer moves. The previous upper bound was 27.

D. Kunkle and G. Cooperman, “Twenty-Six Moves Suffice for Rubik’s Cube”, Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC ‘07), ACM Press, 2007, 235–242.

The number of moves required to solve any state of Rubik’s cube has been a matter of long-standing conjecture for over 25 years — since Rubik’s cube appeared. This number is sometimes called “God’s number”. An upper bound of 29 (in the face-turn metric) was produced in the early 1990’s, followed by an upper bound of 27 in 2006. An improved upper bound of 26 is produced using 8000 CPU hours. One key to this result is a new, fast multiplication in the mathematical group of Rubik’s cube. Another key is efficient out- of-core (disk-based) parallel computation using terabytes of disk storage. One can use the precomputed data structures to produce such solutions for a specific Rubik’s cube position in a fraction of a second. Work in progress will use the new “brute-forcing” technique to further reduce the bound.

Note that their approach used seven terabytes of distributed disk to hold tables needed for the algorithm.

See Cracking the Cube in Science News for a good overview. (spotted on Boing Boing)