[math-fun] Algorithms for Solving Rubik's Cubes
"Erik Demaine, an associate professor of computer science and engineering at MIT; his father, Martin Demaine, a visiting scientist at MIT’s Computer Science and Artificial Intelligence Laboratory; graduate student Sarah Eisenstat; Anna Lubiw, who was Demaine’s PhD thesis adviser at the University of Waterloo; and Tufts graduate student Andrew Winslow showed that the maximum number of moves required to solve a Rubik’s cube with N squares per row is proportional to N^2/log N. 'That that’s the answer, and not N^2, is a surprising thing', Demaine says." The MIT-news backgrounder titled 'The math of the Rubik’s cube' is here: http://web.mit.edu/newsoffice/2011/rubiks-cube-0629.html The to-be-presented paper (in pdf-format) is here: http://arXiv.org/pdf/1106.5736v1
the maximum number of moves required to solve a RubikÂ’s cube with N squares per row is proportional to N^2/log N. 'That thatÂ’s the answer, and not N^2, is a surprising thing', Demaine says."
Well, not that surprising. There are Omega(24^N^2) configurations, and Omega(N) elementary moves, so the lower bound is: Omega(log(24^N^2)/log(N))) = Omega((N^2)/log(N)) Sincerely, Adam P. Goucher
It is indeed reasonably surprising; there are O(N^2) cubies, so in some sense each move must place O(log N) cubies on every single move. Proving this was possible in the general case is certainly non-obvious. It's a good paper.
Well, not that surprising. There are Omega(24^N^2) configurations, and Omega(N) elementary moves, so the lower bound is:
Omega(log(24^N^2)/log(N))) = Omega((N^2)/log(N))
participants (3)
-
Adam P. Goucher -
Hans Havermann -
Tom Rokicki