Cracking the Rubik's Cube

David Kunkle, a computer scientist at Northeastern University in Boston, has proved that 26 moves are enough to solve any scrambled Rubik's Cube. That's one move below the previous record. In the process, he developed algorithms that can be useful for problems as disparate as scheduling air flights and determining how proteins will fold.

Rubik's Cube has approximately 43 quintillion possible configurations. Even a supercomputer can't search through every possible configuration to find the quickest way to unscramble a given starting arrangement in a reasonable amount of time.

Kunkle and his advisor Gene Cooperman approached the problem by applying various mathematical tricks. If each side of the cube is one color, the puzzle is solved regardless of which color is on which side. By considering configurations to be equivalent if they differ only in having two colors interchanged, they managed to reduce the number of truly distinct configurations to just over a quintillion.

Next, they looked at a simpler problem: they considered only configurations that could be solved by twisting facelets through half-turns only, with no quarter-turns. Only about 15,000 of the quintillion configurations can be solved in this way. The team found that any puzzle in one of those special configurations could be solved in 13 moves or fewer.

Then they figured out how many steps are required to turn any random configuration into one of the 15,000 special configurations. To do this, they first classified the configurations into sets, each containing configurations that can be transformed among themselves using only half-turns. These sets were constructed in such a way that a series of moves that gets from one member of any set to one of the special configurations will also turn any other member of the set into a special configuration. They ended up with 1.4 trillion of these sets, so they now had only 1.4 trillion problems to solve—far fewer than the original 43 quintillion, but still a formidable number.

Using a supercomputer, they 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. So 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. Kunkle and Cooperman now hope to knock the maximum number of steps down to 25. They think they can use their brute-force search method on all of the configurations that require 26 steps to find a quicker way to solve them.

Even if they manage this feat, however, it will probably leave room for improvement. Most researchers believe that just 20 steps are enough to solve any Rubik's Cube, but no one has proved it yet.

More details at MathTrek.