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.
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...