# 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.
• 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). – WhatsUp Nov 3 '20 at 15:42