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

Comments

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

[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

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