Thursday, August 23, 2007

Rubik's Cube solvable in 26 moves or less

David Pescovitz: No matter how scrambled a Rubik's Cube may be, it can be solved in 26 moves or fewer -- by a supercomputer anyway. The previous record was 27 moves, but Northeastern University computer science grad student Daniel Kunkle and his advisor Gene Cooperman developed new algorithms to save a step in the process and optimize the problem for a supercomputer. Their next step is to bring the magic number down to 25, which is still 5 more than the minimum number of steps that most researchers believe is possible. From Science News:
After 63 hours of calculation, the supercomputer found that it took no more than 16 steps to turn any random configuration into a special configuration that can be solved using only half-turns. And since those special puzzles can be solved in no more than 13 steps, this approach showed that 29 steps were enough to solve any Rubik's Cube.

But this answer wasn't good enough to set a new record. Last year, Silviu Radu of the Lund Institute of Technology in Sweden showed that any Rubik's Cube can be solved in no more than 27 steps. Kunkle and Cooperman realized that to set a new record, they would need to eliminate three steps.

Their existing method had established that all but about 80 million sets of configurations could be solved in 26 steps or fewer. By searching through all possible moves starting from those relatively few configurations, they succeeded in finding a solution for each one that took 26 steps or fewer.

Previously on BB:
• Video of tot solving Rubik's Cube Link
• Table shaped like huge Rubik's Cube Link
• Michel Gondry solves Rubik's Cube with feet Link