It’s astounding what one can find on the science blogs, isn’t it? How about information the insight that a Rubik’s cube can always be solved in 26 moves or less? This work beats out last years 27-or-less moves proof.
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.
The article discusses in brief some of the work done to generate this proof. And as noted in the above snip, these algorithms could well have applicability to other work dealing in problems with massively large numbers of permutations. (via boingboing)
[tags]Rubik’s Cube, World record, Algorithms, Science news, Science[/tags]