Daniel Kunkle can solve a Rubik's Cube in 26 moves. Or at least his computer can.
Kunkle, a computer scientist at Northeastern University in Boston, has proved that 26 moves are enough to solve any Rubik's Cube, no matter how scrambled. That's one move below the previous record. In the process of cracking the cube, 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. So Kunkle and his advisor Gene Cooperman developed some clever mathematical and computational strategies to make the puzzle more manageable.
Kunkle and Cooperman started 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, the computer scientists 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. A standard PC can find the shortest way to unscramble each of this relatively small number of configurations in less than a day, simply by searching through all possible moves. 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.
Now they put a supercomputer on the job and applied clever computational strategies to speed up the search. Because it takes computers a very long time to search for information stored on a hard drive, Kunkle and Cooperman developed ways to store the information in precisely the order the computer would later need it. That way, the computer could read the information off the drive without searching for it.
"These kinds of techniques can be applied to any combinatorial problem that you want to solve," Kunkle says. He points to checkers, chess, scheduling of air flights, and protein folding as examples. A somewhat similar set of computational techniques was recently used to find the best strategies for playing checkers (SN: 7/21/07, p. 36).
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.
They presented their result July 29 at the International Symposium on Symbolic and Algebraic Computation in Waterloo, Ontario.
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.
No comments:
Post a Comment