Home   LARC   News   Publication List   Publications by Subject   Mathematical Puzzles

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

Thumbnails.

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]

Supplementary Material

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.

Animation.

Created July 3, 2015. Written in HTML 4.01 and CSS 3 using vi. Last updated July 22, 2015.

Valid HTML 4.01 Strict Valid CSS!