A preliminary version of this paper appeared as Technical Report LARC-2014-01, Laboratory for Recreational Computing, Dept. of Computer Science & Engineering, University of North Texas, April 2014. [pdf]

Ian Parberry,
"Solving the $(n^2-1)$-Puzzle with $\tfrac{8}{3}n^3$ Expected Moves",
*Algorithms*, Vol. 8, No. 3, pp. 459-465, 2015.
[open access manuscript]

This paper analyzes the expected number of moves made by the algorithm in my 1995 paper
"A Real-Time Algorithm for the
$(n^2-1)$-Puzzle",
Information Processing Letters, Vol. 56, pp. 23-28, 1995.
[pdf]

A preliminary version of this paper appeared as Technical Report LARC-2014-01, Laboratory for Recreational Computing, Dept. of Computer Science & Engineering, University of North Texas, April 2014. [pdf]

The following animation shows an example of the solution computed
by the algorithm from my 1995 paper (however, this version recurses down
to a $2\times 2$ instead of a $3 \times 3$).
Red tiles are out of place, and yellow tiles are in the process of being
moved to their correct place.