9
$\begingroup$

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

$\endgroup$

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\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, 2020 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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