On the 15-puzzle, what (solvable) position takes the most moves to solve if you solve it optimally?


The hardest positions on the 15-puzzle require $80$ moves to solve (where a move consists of sliding a single tile). Here is an example of a position requiring $80$ moves: $$ \begin{array}{|c|c|c|c|} \hline 15&14&8&12\\\hline 10&11&9&13\\\hline 2&6&5&1\\\hline 3&7&4&\\\hline \end{array} $$ This position (and several others) can be found in Ralph Gasser's PhD thesis from 1995 [G], where it is proved that $80$ moves are necessary. A few years later, it was proved in [BMFN] that no position requires more moves. Both proofs are aided by computers.

[BMFN] Brüngger, Adrian; Marzetta, Ambros; Fukuda, Komei; Nievergelt, Jurg. The parallel search bench ZRAM and its applications. Ann. Oper. Res. 90 (1999), 45-63.

[G] Gasser, Ralph Udo. Harnessing Computational Resources for Efficient Exhaustive Search. PhD Thesis, ETH Zürich, 1995.

  • $\begingroup$ A note on this answer: the position here assumes that the blank goes in upper left corner in the final position. A complete list of positions requiring $80$ moves, as well as an optimal solver, is available on this site (I'm not the author, just found it by searching). $\endgroup$ – WhatsUp Nov 3 '20 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.