Computational Algebra Seminar: Cooperman -- Twenty-Six moves or less Suffice to Solve Rubiks Cube

Speaker: Gene Cooperman (Northeastern University, Boston) Title: Twenty-Six moves or
less Suffice to Solve Rubiks Cube Time & Place: 3:05-4pm, Thursday 28 June, Carslaw 535 

Newspaper article: Boston Globe 25 June 2007
http://www.boston.com/news/globe/health_science/articles/2007/06/25/the_search_for_gods_number_in_a_rubiks_cube/ 

Abstract: The question of the maximum number of moves needed to solve any state of
Rubik’s cube became a challenge problem for computer science almost since the invention
of Rubik’s cube in the late 1970s.  In joint work with Daniel Kunkle, we recently showed
that 26 moves suffice, and we hope soon to demonstrate that 25 moves suffice.  An upper
bound of 29 was found by Reid in 1995.  This bound was reduced to 27 in 2006 by Radu.
The best upper bound is suspected to be 20.  (A move is a quarter- or a half-twist.)  

The basis for our new approach is two-fold: (1) We developed a new group-theoretic
algorithm for fast simulation of moves; and (2) We use 7 terabyes of distributed
parallel disk for intermediate storage of a data structure related to hash tables, but
more suitable for disk streaming access.  The group-theoretic algorithm allows us to
multipy a symmetrized coset (large classes of states closed under symmetries) by a
generator at a rate of more than 10 million moves per second.  

The first part of the algorithm (a variation of breadth-first search) is described.
This first part already demonstrates that 27 moves suffice.  A second part uses the data
from the first part to eliminate potentially long solutions and further reduce the upper
bound.  The second part of the algorithm has already shown that 26 moves suffice, and
further computation should further reduce the bound.