# 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$.

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]
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.