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

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