Algorithm Solves Rubik's Cubes of Any Size 139
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."
From TFA... (Score:3, Informative)
It's n^2/log n.
Re:From TFA... (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.
General algorithm already known (Score:4, 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.