27 moves? They don't need no stinking 27 moves. Northeastern University Computer Science professor Gene Cooperman and graduate student Dan Kunkle set out to do what no one clamored for - solving any Rubik's Cube configuration in 26 moves, a new record.
Welcome to the family of cosets.
“The Rubik's cube is a testing ground for problems of search and enumeration,” says Cooperman. "Search and enumeration is a large research area encompassing many researchers working in different disciplines – from artificial intelligence to operations. The Rubik's cube allows researchers from different disciplines to compare their methods on a single, well-known problem."
How did they do it? 7 terabytes of memory and some mathematical group theory.
Simulating at 100,000,000 times per second, they apply a single move to every coset at once. "Our program first does a large pre-computation and then it very quickly - in about a second - finds a solution in 26 moves or less for any state of Rubik's cube," says Kunkle.
UCLA computer science Professor Richard Korf said in 1997 that the optimal solution was 20 moves but no one had been able to do it with less than 27 before now. With 43 quintillion (4.3252 x 10**19) different states that can be reached from any given configuration, I'd have to say 26 moves is pretty good.
Cooperman and Kunkle used computers at Teragrid (teragrid.org) and at Northeastern, part of the first node from a $200,000 grant Cooperman and colleagues received from the National Science Foundation in 2006 to obtain 20 terabytes of storage.