## Rubic’s cube solvable in 26 moves

Tim Finin, 1:00pm 13 August 2007Northeastern 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)