With Rubik’s Cubes, victory is only 23 clicks away
Stanford-trained mathematician Tomas Rokicki has broken his own record, proving that any (solvable) Rubik’s Cube position can be cracked in 23 moves or fewer.
For anyone who’s spent hours twirling the sides of the colored puzzle, this news might just be frustrating. But for mathematicians, this is a big success for elegant computer solutions.
Rubik’s Cubes, in case you forgot about the ’70s sensation, challenge players to spin sides of 3x3x3 cube in order to make each surface a single color.
Last year, students at Northeastern University proved they could solve even the most twisted configuration in as few as 26 moves. In March, Mr. Rokicki one-upped them by whittling down that number to 25. His solution used a computer to churn through possible paths toward victory and filtered out any repeats. This is how most mathematicians solve puzzles nowadays when there are 43 quintillion possible positions – teach a computer to do it, and just wait for it to consider every possibility.
But this takes a really long time. Rokicki sped up the process by finding a clever way to divvy up the possible configurations into sets. It still took his PC 1,500 hours to come up with a solution.
The leap from 25 to 23 moves came courtesy of Sony Imageworks, the supercomputers that brought us “Spider-Man 3” and “Surf’s Up.” Rokicki programmed the Sony processors to whiz through permutations in between rendering movie special effects.
We already know that there is no position that takes exactly 21 moves to solve. (My first reaction to this was, “What do you mean? Take a finished Rubik’s Cube and spin it 21 times.” But Rokicki found that whatever configuration you land on after that 21st twirl can be solved in fewer than 21 rotations.)
This quirk suggests that, after more refinement, it’s possible that computers could push the cap down to 20 moves. Rockicki is already chugging away at 22. But it will take a lot of time and processing power to reach that number.
[Via Slashdot]
Also check out:
Computers master the game board
Wisdom of the crowd triumphs in alternate reality games
