Hi Twisty Puzzles fans,

Many people had already suspected that it could take many moves to solve my Over The Top 17x17x17 puzzle. But now we have proof.

Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow wrote this article, in which they calculate lower and upper bounds for the "God's number" for higher order nxnxn Rubik's Cube. Recently, it became know that the "God's number" for the 3x3x3 is 20. Even though exact numbers are yet unknown for higher orders, we now know some bounds.

The last equation seen on page 22 of the paper is this one.

[(floor(n/2) - 1)^2 * log(24!/(4!)^6)]/log(6n) <= k

When you fill in n=17, then you find k=379.

This means that there exist at least one configuration, from which it takes at least 379 moves to solve the puzzle. Or to put it differently, it requires at least 379 moves to fully scramble the puzzle.

Oskar

... or just one move with a really big sledgehammer.

The paper was also mentioned in this thread.

Note that this formula is a very conservative lower bound -- it doesn't even count edge cubies, if I understand correctly. So the actual God's Number for the 17x17x17 is probably much higher.

The only purpose of the formula was to establish that it takes at least (some constant times) n^2 / log n moves to solve an nxnxn cube. For purposes of showing this asymptotic lower bound, it doesn't matter what the constant is, but for determining God's Number, it matters very much what it is.