Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves

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\).

Keywords

• 15-puzzle, 8-puzzle, analysis of algorithms, average case analysis, greedy algorithm, (n2 — 1)-puzzle