# What is the superflip on 15-puzzle?

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.