I've never been able to solve a Rubik's Cube. It's a personal failing I chalk up to mild ADD, horrible spatial organization skills, and the desire to not get beaten up in middle school. Somehow, none of that gets in the way of my interest in reading a 10-page paper proving that all formations of a Rubik's Cube can be solved in 25 moves or less.
Ah, for the salad days of hiding my nerdery.
In 1981, Douglas Hofstadter published results in Scientific American from Morwen Thistlethwaite showing that the upper bounds for any cube would be around 100 moves. He showed the limit by combining the worst-case scenarios of various algorithms. Other researchers then broke down the bound to 50 moves, then 30, then 29, and 28, all in quest of what's known as "God's Algorithm."
In 2007, though, researchers at Northeastern turned to computers to show that only 26 moves were needed by looking at sets of positions instead of single positions. This year, Tomas Rokicki showed them all up by creating "program that is able to find solutions of length 20 or less at a rate of more than 16 million positions a second" and using it "to show that there is no position that requires 26 moves."
Now that's a mathematical smack down.
The trick of it is in condensing the permutations that Rokicki's program is looking at. On a normal 3x3x3 Cube, there are about 4.3E19 possible arrangements. Many of them are symmetrical or merely the inverse of others, though, and as such require the same distance to get to a solution, so you can reduce the set to 4.51E17 combinations. That would still take a fair amount of time to process, though--7000-years-with-7000-of-today's-computers kind of time.
Rokicki condensed it further by looking at a subset of 20 billion positions that others have proven are reachable within 12 moves from any other position and solvable within another 18 moves. Examining this and related sets for symmetry, Rokicki further condensed the number of combinations he'd need to look at to about 139 million.
1500 CPU hours later (62.5 days compared to 7000 years) and Rokicki reproduced the proof that shows an upper limit of only 25 moves to solve the Rubik's Cube. With a few more months of CPU time, he hopes to show an upper bound of 24 moves.
But really, Rokicki, two moves per year closer to God's Algorithm? I'm pretty sure that's hubris in the classical sense.
[Abstract and links to paper. Via The Physics arXiv via Slashdot.]
Add a comment