On the 15-puzzle, what (solvable) position takes the most moves to solve if you solve it optimally?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Nov 29, 2015 at 23:20
-
3$\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$– WhatsUpNov 3, 2020 at 15:42