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."
Why wasn't the Q6600 at 2.4ghz like normal? Anyone know?
This is a good example of where the inefficient method (of about 60 moves iirc) is much faster in terms of time. The 25 move solution is elegant but just not worth it in terms of computations, time etc...
:-)
This could make a good case study for business schools
I think all he proved is that a random cube can be solved in 25 moves, but those moves are unique to every starting combo.
In other words, they are left as an exercise to the reader.
This is better stated as
"for any starting position there exists a sequence of no more then 25 moves that will solve it"
it doesn't mean (among other things)
"there is a human usable method of solving a rubik's cube in 25 moves or less unassisted"
from TFA
"Where is this likely to finish? A number of configurations are known that can be solved in 20 moves"
Should read
"a number of configurations are known to have no solutions that are less then 20 moves"
whereas this
"it's also known that there are no configurations that can be solved in 21 moves."
I'm not even sure what they're trying to say here...
Is he trying to say that there is known to be no configurations for which the optimal solution is exactly 21 moves?
"What this problem is crying out for is a kindly set theorist who can prove exactly what the upper and lower limits should be without recourse to a few years of CPU time (although it may take a few years of brain time). Any takers?"
this sounds alot like "some real mathematician should prove this using non-bruteforce methods before these amatuers hurt themselves" which to me betrays a very shallow understanding of the problem coupled with a very condescending attitude
I guess that if a Rubik cube had had the same structure as an aperiodic graph (recall the recent Slashdot story), then such a fixed set of moves, that work no matter what your starting point is, would have existed. Obviously that's not the case here.
"In our tactical decisions, we are operating contrary to our strategic interest."
Wait, how did this get modded Interesting? A solved cube is indeed a member of all starting point, and it would be the only member of its set of essentially similar ones (and, for that matter, the member of the only set of essentially similar ones solvable in zero moves). I fail to see anything interesting about that.
Want a high quality FOSS RTS game? Try Warzone 2100!
Any cuber worth a damn will be able to identify that the cube has been tampered with within two minutes (significantly less if he or she is a speed cuber).
eclecti.cc
Perhaps, but that's only if you count a "switch" as a single move, rather than - Peel, Peel, Stick, Stick...
This is worthy of a /. hall of fame - we need a new moderation option :)
"Next up, 24 moves."
Unless they find a position that requires 25 moves to solve. End of argument.
Yup - that's a bizarre thing to say. Surely after the first move in solving a configuration that can be optimally solved in 22 moves you obtain a configuration that can be optimally solved in 21 moves, by definition?
part of this proof involved eliminating similar combinations. A solved cube has 24 variations. (viewed from any one of six faces, in any of four rotations)
I work for the Department of Redundancy Department.
I could never understand these idiots who removed the stickers. The rubix cube comes apary very easily, and goes together almost as easily. What sort of a fool would want to deal with the stickers??? No offence.
It would have been easier to just learn how to solve it. Once you know how, it's quite a feeling of accomplishment and people think you're smart even though it's really not that hard.
Its = possessive. It's = "it is"