Slashdot Mirror

← Back to Stories (view on slashdot.org)

Algorithm Solves Rubik's Cubes of Any Size

Posted by timothy on from the gordian-knot-sledgehammer dept.

An anonymous reader writes with this excerpt from New Scientist: "Only the most hardcore puzzle-solvers ever go beyond the standard 3x3x3 Rubik's cube, attempting much larger ones. Now an algorithm has been developed that can solve a Rubik's cube of any size. It might offer clues to humans trying to deal with these tricky beasts. Erik Demaine, a computer scientist at the Massachusetts Institute of Technology has found that the maximum number of moves that will ever be required for a cube of side n is proportional to n/log n. 'It gives me a couple of ideas how to solve this thing faster,' says Stewart Clark, a Rubik's cube enthusiast who owns an 11x11x11 cube."

9 of 139 comments (clear)

  1. From TFA... by Lightborn · · Score: 3, Informative

    It's n^2/log n.

    --
    My .sigs are not what they used to be.
    1. Re:From TFA... by RussellSHarris · · Score: 5, Informative

      Actually, it's n²/log n, but since Slashdot doesn't like Unicode it just eats that ² character and you end up with n/log n. Which, of course, is wrong.

    2. Re:From TFA... by arth1 · · Score: 4, Funny

      Yeah, I kind of wondered about that. It would imply that a standard 3x3 cube would always be solvable in 7 moves or less, which is clearly wrong, unless these are gentoo moves.

  2. Yes, but... by Anonymous Coward · · Score: 3, Interesting

    Does it scale to >3 dimensions?

  3. General algorithm already known by Michael+Woodhams · · Score: 3, Informative

    Once you can solve a size 4 and size 5 cube, all larger sizes are obvious generalizations of the same algorithm. (At least, for the algorithm I use it is so.) I've seen an edited video of someone solving a (computer simulated) size 100 cube. So the fact of a "general algorithm" is not news.

    That it is an efficient algorithm and sets a new* upper bound on how many moves you need is interesting. (This upper bound is proportional to (n^2/log n), not (n/log n) as stated in the summary.)

    * I don't follow cubology that closely, so I'm taking their word for it that this is a new upper bound.

    --
    Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
  4. The solution? by tool462 · · Score: 4, Funny

    -After the researchers solve the 3x3x3-

    Buttercup: We'll never succeed. We may as well die here.

    Westley: No, no. We have already succeeded. I mean, what are the three terrors of the General Cube Solution? One, the pieces coming off - no problem. There's a popping sound preceding each; we can avoid that. Two, the stickers peeling off, which you were clever enough to discover what that looks like, so in the future we can avoid that too.

    Buttercup: Westley, what about the R.O.U.S.'s?

    Westley: Rubik's Of Unusual Size? I don't think they exist.

    -- Immediately, Westley is attacked by a 4x4x4 cube --

  5. It's time for Slashdot to support Unicode properly by eobanb · · Score: 4, Insightful

    Lack of support for 20 year-old standard is usually just annoying as hell, but in this case it's actually caused the summary to be wrong. For a site that frequently discusses such topics as technology, math and language (for all of which Unicode is an important part—at least insofar as even being able to TALK about these subjects) there is absolutely no excuse for not doing Unicode.

    As far as I'm concerned Slashdot ought to be able to render MathML too.

    --

    Take off every sig. For great justice.

  6. Mr Rubik by pinballer · · Score: 4, Funny

    I could only ever manage to get 5 out of the 6 sides :(

  7. Re:Well that's not good by BeardedChimp · · Score: 3, Funny

    The man was devastated by the article and as soon as he overcomes his devastation you tell him his other 12 year life long pursuit is fruitless. He is not going to be having a good day.