Skip to content

15-puzzle

Introduction

15-puzzle (also known as Gem Puzzle, Boss Puzzle, Game of 15, Mystic Square, N-puzzle, etc.) is a sliding puzzle. The puzzle board is a \(4\times 4\) grid, with 15 numbered tiles placed in random order and one empty square. Tiles in the same row or column as the empty square can be moved horizontally or vertically by sliding. The goal of the puzzle is to arrange the tiles in numerical order.

The 15-puzzle is commonly referred to as the n-puzzle, where the number \(n\) refers to the total number of tiles. Variants of the 15-puzzle with different sizes use similar names; for example, the \(8\)-puzzle refers to \(8\) tiles placed on a \(3\times3\) board. However, the 15-puzzle can also be called the 16-puzzle, where 16 refers to the board capacity. Its extended problems sometimes include sliding puzzles of size \(n \times m\).

The 15-puzzle is a classic problem involving modeling with heuristic algorithms. Common forms of this problem involve calculating the Manhattan distance and the number of misplaced tiles, both of which are admissible heuristics—meaning they never overestimate the number of moves remaining. This ensures the optimality of certain search algorithms, such as A* algorithm.

Note

Sliding puzzles are a type of intellectual game where tiles are slid on a plane to form a specific arrangement. Common sliding puzzles include number puzzles, Klotski, and Rush Hour. Among them, the 15-puzzle is the oldest sliding puzzle, invented by Noyes Chapman, and gained popularity in the 1880s. Unlike other tour-type puzzle games, sliding puzzles prohibit any tile from leaving the board, a characteristic that distinguishes them from rearrangement-type puzzle games.

Definition

Given a \(4 \times 4\) board with \(15\) tiles arranged randomly, the goal is to arrange them in numerical order as shown in the figure below. The rule is that only the empty square can be swapped with an adjacent tile. Common problems include finding the minimum number of steps to solve the puzzle, counting the number of misplaced tiles, or determining whether a given arrangement can reach the final ordered state.

Solvability Proof

Johnson & Story (1879) proved that if both \(m\) and \(n\) are at least \(2\), then the converse holds for a board of size \(m\times n\): by induction on \(m\) and \(n\) starting from \(m=n=2\), all even permutations are solvable. Archer (1999) provided another proof based on defining equivalence classes via Hamiltonian paths.

Algorithms

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

The N-Puzzle supports common graph-based search algorithms such as breadth-first search and depth-first search. Similarly, we can use the A* search algorithm to find the optimal solution. The heuristic function \(h(n)\) can be:

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

Group Theory

Because the combinations of the 15-puzzle can be generated by "3-cycles," it can be proven that the 15-puzzle can be represented by the alternating group \(A_{15}\). In fact, any sliding puzzle using \(2\times k-1\) tiles of equal area can be represented by the alternating group \(A_{2k-1}\).

Exercises

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
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用