15-puzzle

Introduction

15-puzzle (English: 15-puzzle; also known as Gem Puzzle, Boss Puzzle, Game of 15, Mystic Square, N-puzzle, etc.) is a sliding puzzle. The sliding board is a $4\times 4$ grid of tiles, 15 of which contain randomly ordered numbers, with one position left empty. A tile in the same row or column as the empty position can be moved horizontally or vertically. The goal of the puzzle is to arrange the tiles in numerical order.

The 15-puzzle is also commonly called the n-puzzle, where $n$ is the total number of tiles on the board. Variants of different sizes use similar names; for example, the $8$-puzzle is placed on a $3\times3$ board with $8$ tiles. The $15$-puzzle can also be called the $16$-puzzle, where 16 refers to the board capacity. Extended versions sometimes include sliding boards of size $n \times m$.

The 15-puzzle is a classic problem involving modeling with heuristic algorithms. Common heuristics for this problem are the Manhattan distance and the number of misplaced tiles. Both are admissible heuristics: they never overestimate the number of remaining moves, which ensures the optimality of some search algorithms, such as A* search.

Definition

Given a $4 \times 4$ board with $15$ tiles in an arbitrary arrangement, we need to arrange them by number as shown below. Each move may only exchange the empty tile with one adjacent tile. Common tasks are to find the minimum number of moves needed to solve the puzzle, count the misplaced tiles, or determine whether the final ordered arrangement is reachable.

Solvability Proof

Johnson & Story (1879) proved that if $m$ and $n$ are both at least $2$, the result extends to an $m\times n$ board: by induction starting from $m=n=2$ on $m$ and $n$, all even permutations are solvable. Archer (1999) gave another proof based on defining equivalence classes through Hamiltonian paths.

Algorithms

Finding a solution to a sliding-tile puzzle is relatively easy, but finding an optimal solution is an NP-hard problem. An optimal solution to the 15-puzzle has at most 80 moves, while one for the 8-puzzle has at most 31 moves.

N-puzzles support common graph-based search algorithms such as breadth-first search and depth-first search. We can also use A* search to find an optimal solution. A heuristic function $h(n)$ can be

• the number of misplaced tiles;
• the sum of the Euclidean distances from all misplaced tiles to their respective target positions;
• the sum of the Manhattan distances from all misplaced tiles to their respective target positions.

Group Theory

Because configurations of the 15-puzzle can be generated by “3-cycles” (English: 3-cycles), the 15-puzzle can be represented by the alternating group $A_{15}$. In fact, any sliding-tile puzzle using $2\times k-1$ square tiles of equal area can be represented by the alternating group $A_{2k-1}$.

Exercises

• N Puzzle
• A. Amity Assessment
• Sliding Puzzle
• POJ 1077 - Eight

References and Further Reading

1. 15 puzzle - Wikipedia
2. jrdnjacobson, How to Solve the 15 Puzzle - instructables
3. Korf, R. E. (2000), "Recent Progress in the Design and Analysis of Admissible Heuristic Functions", in Choueiry, B. Y.; Walsh, T. (eds.), Abstraction, Reformulation, and Approximation (PDF), SARA 2000. Lecture Notes in Computer Science, vol. 1864, Springer, Berlin, Heidelberg, pp. 45–55, doi:10.1007/3-540-44914-0_3, ISBN 978-3-540-67839-7, retrieved 2010-04-26
4. Welcome to N-Puzzle - web demo