The $(n^2-1)$-Puzzle (2015)

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]

Abstract

It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\tfrac{8}{3}n^3 +O(n^2)\) expected moves. This analysis is verified experimentally on 10,000 random instances each of the \((n^2-1)\)-puzzle for \(4 \leq n \leq 200\).

Author's Comments

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.