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.