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

1.6ghz?

[dostert]

Why wasn't the Q6600 at 2.4ghz like normal? Anyone know?

Theory versus practice

[line-bundle]

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 :-)

Re:Which 25 moves?

[calebt3]

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.

Re:Theory versus practice

[garcia]

IMHO it isn't proving what you seem to believe it does.

Instead, it makes a great case for doing the research on the front end to eliminate lengthy repetition of useless iterations to shorten the overall time.

Re:Theory versus practice

[QuantumG]

I'm not sure I know what you're saying, but it seems you don't either, so ok.

Re:1.6ghz?

[Cecil]

Why do both CPU manufacturers include those shitty, awful heatsinks anyway? Do they want people to think their processors overheat and are loud and suck? And that's before the fan starts shrieking and sticking due to dead bearing or crap oil or clogged with dust. I haven't gotten a CPU with a good stock heatsink since the Pentium III. Hell, if AMD or Intel decided to contract out to Zalman or something, they could suddenly start marketing their CPUs as super quiet and cool and power efficient and probably eat up a bunch of market share. People are tired of the noise and heat.

Next up, videocards, ugh.

Re:Which 25 moves?

[Anonymous Coward]

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

Re:Which 25 moves?

[DrEasy]

I guess that if a Rubik cube had had the same structure as an aperiodic graph (recall the recent Slashdot story [slashdot.org]), 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.

Re:Wow, it really works

[Zarel]

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.

Re:You only need one

[PaintyThePirate]

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

Re:Wow, it really works

[Vectronic]

Perhaps, but that's only if you count a "switch" as a single move, rather than - Peel, Peel, Stick, Stick...

Re:Which 25 moves?

[skelly33]

This is worthy of a /. hall of fame - we need a new moderation option :)

Re:Which 25 moves?

[Anonymous Coward]

"Next up, 24 moves."

Unless they find a position that requires 25 moves to solve. End of argument.

Re:Which 25 moves?

[uglyduckling]

"it's also known that there are no configurations that can be solved in 21 moves."

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?

Re:Wow, it really works

[v1]

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)

Re:Wow, it really works

[mgblst]

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.

Re:Wow, it really works

[strabes]

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.