SMS scnews item created by Bill Unger at Wed 27 Jun 2007 1256
Type: Seminar
Distribution: World
Expiry: 28 Jun 2007
Calendar1: 28 Jun 2007 1505-1600
CalLoc1: Carslaw 535A
Auth: billu@galois.maths.usyd.edu.au

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.  


If you are registered you may mark the scnews item as read.
School members may try to .