Slashdot Mirror

← Back to Stories (view on slashdot.org)

Rubik's Cube Proof Cut To 25 Moves

Posted by samzenpus on from the too-much-time-on-your-hands dept.

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

7 of 386 comments (clear)

  1. 1.6ghz? by dostert · · Score: 4, Insightful

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

  2. Theory versus practice by line-bundle · · Score: 5, Insightful

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

    1. Re:Theory versus practice by garcia · · Score: 5, Insightful

      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.

  3. Re:Which 25 moves? by calebt3 · · Score: 5, Insightful

    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.

  4. Re:Wow, it really works by Zarel · · Score: 5, Insightful

    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!
  5. Re:Wow, it really works by Vectronic · · Score: 4, Insightful

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

  6. Re:Which 25 moves? by uglyduckling · · Score: 4, Insightful

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