Re: [math-fun] Algorithms for Solving Rubik's Cubes

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