Slashdot Mirror
Rubik's Cube Proof Cut To 25 Moves
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."
And to save people from opening calculator, that's about 62 days of operation.
Speaking from experience (I'm on one), the Q6600 does run at 2.4 GHz. And while they are far too much for the stock heat sink if you're going to load up all four cores, if you throw a Zalman on them, you can load them up 100% without any problem at all. Their TDP is 105 watts, the old Prescotts got up to about 120 watts, if I recall.
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.
Oh, you're not stuck, you're just unable to let go of the onion rings.
the Q6600 will default to 1.6 GHz to save power, at least it does for me under ubuntu 7.10. I'm guessing the cpu actually ran at 2.4 under load...
I think a better way to think of it is that given any position, you can solve it in 25 moves or less. There are many algorithms that you can use to solve rubik's cubes, applying a general rule to solve any position, but they can take ~60 moves in some situations. So while it may be possible (completely intuitive guessing here, I'm no rubik master) to solve for a certain position in 25 moves it may be non-intuitive and require a specific strategy to that position. You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha
If you are about to mod me down, keep in mind that this post was most likely sarcastic.
Here's the paper itself, if you want more detail than the very general summary in TFA.
Why do so many people leave SELECT out of that code? Weren't you ever playing two-player? It's select start for goodness sakes.
If you want to get technical, not even START is required in some cases.
http://en.wikipedia.org/wiki/Konami_Code
This is a proof of upper limit, not an optimal solution. He proved is that all possible combinations of 26 moves yielded a position which was symmetrical to a cube with a lesser number of moves applied to it.
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...)
No sig today...
David Joyner has a book which explores some of the math behind the Rubik's cube: http://www.amazon.com/Adventures-Group-Theory-Merlins-Mathematical/dp/0801869471
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 . Sage also includes a number of efficient solvers for the Rubik's cube.
I have to admit, in reading the summary, Tomas Rokicki's name seemed very familiar....
And of course! He's the author of dvips! 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.
iSKUNK!
RTFS dude. He didn't solve a cube, he proved that a cube can be solved from any starting position in 25 moves or less.
A *human* can solve a cube in seconds - it's not impressive for a computer to do it.
Perhaps it can't be reduced to 19 moves. But then again, Kociemba's algorithm has not yet provided a proof that the diameter of the cube group is indeed 20 (in face counting). We won't have such a proof until an optimal solver is used, something that could take years of run time on current hardware. Application for a grid perhaps?