Rubik's Cube Proof Cut To 25 Moves 386
KentuckyFC writes "A scrambled Rubik's cube can be solved in just 25 moves, regardless of the starting configuration. Tomas Rokicki, a Stanford-trained mathematician, has proven the new limit (down from 26 which was proved last year) using a neat piece of computer science. Rather than study individual moves, he's used the symmetry of the cube to study its transformations in sets. This allows him to separate the 'cube space' into 2 billion sets each containing 20 billion elements. He then shows that a large number of these sets are essentially equivalent to other sets and so can be ignored. Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz. Next up, 24 moves."
Re:1.6ghz? (Score:4, Informative)
Re:1.6ghz? (Score:3, Informative)
The stock heat sink isn't good at all. And their thermal compound, even after repeated heat cycling, only covers a small fraction of the CPU-heatsink interface. Just throw it away.
Re:1.6ghz? (Score:3, Informative)
Re:Which 25 moves? (Score:5, Informative)
The original paper (Score:4, Informative)
Re:Which 25 moves? (Score:3, Informative)
Re:Which 25 moves? (Score:3, Informative)
http://en.wikipedia.org/wiki/Konami_Code [wikipedia.org]
No, what he proved is the upper limit (Score:4, Informative)
An optimal solution would probably look like a bell curve going from "zero moves required" (ie. already solved) all the way up to "25 moves required" (which we now know is the upper limit...)
Math and the Rubik's Cube (Score:3, Informative)
If you are interested in playing around with the symmetry group associated to the Rubik's cube, Sage (http://www.sagemath.org) has good support for it; the documentation can be found at http://www.sagemath.org/doc/html/ref/module-sage.groups.perm-gps.cubegroup.html [sagemath.org] . Sage also includes a number of efficient solvers for the Rubik's cube.
Tomas who? (Score:3, Informative)
And of course! He's the author of dvips [radicaleye.com]! So we have him to thank not only for this cutting-edge breakthrough in mathematical solutions to Rubik's Cube, but also for turning our not-overly-portable DVI files into beautiful, beautiful Postscript.
Re:What the!? (Score:3, Informative)
A *human* can solve a cube in seconds - it's not impressive for a computer to do it.
Re:What do we know about "God's Algorithm"? (Score:3, Informative)