Solving the 15-Puzzle Game Using Local Value-Iteration

Bastian Bischoff, Duy Nguyen-Tuong, Heiner Markert, Alois C. Knoll

Introduction

The 15-puzzle is a classic sliding tile game consisting of a $4 \times 4$ grid with 15 numbered tiles and one empty space. The objective is to reach a target configuration from a scrambled state by sliding tiles into the empty slot. Despite its simple rules, the puzzle presents a significant challenge for standard Reinforcement Learning (RL) due to its combinatorial complexity. With approximately $2 \cdot 10^{13}$ reachable states, traditional methods like Value-Iteration (VI) are computationally infeasible, as they require storing and updating values for every possible configuration.

Initial and goal states of a 15-puzzle.

Methodology: Local Value-Iteration

To overcome the state space explosion, this research introduces Local Value-Iteration. This approach mimics human problem-solving strategies by decomposing the global task into a sequence of manageable local subproblems.

Instead of solving the entire board at once, the algorithm focuses on placing tiles sequentially (e.g., tile 1, then tile 2, etc.). Each subproblem is defined by a set of "Goal" tiles ($G$) to be positioned and a set of "Restricted" tiles ($R$) that are already correctly placed and must remain undisturbed.

The algorithm employs an adaptive complexity mechanism. It initially attempts to solve for a single tile while keeping all previously solved tiles locked. If a solution is not found within this constraint, the algorithm dynamically expands the "Goal" set by unlocking tiles from the "Restricted" set until a local solution is reachable.

Complexity and State Space Reduction

The core innovation of Local Value-Iteration lies in its drastic reduction of the state space. By focusing on a small subset of tiles at any given time, the agent avoids the $10^{13}$ global configurations.

Theoretical analysis and empirical testing demonstrate that no more than 5 tiles ever need to be considered simultaneously to solve any configuration of the 15-puzzle. As shown in the table below, the maximum state space size for these subproblems is capped at 10,080 states—a scale that is easily handled by modern hardware.

Maximum state space size for different subproblems.

Results and Performance

The proposed method was validated using a dataset of 100,000 random solvable puzzle configurations. The results highlight the efficiency and reliability of the local approach:

  • Success Rate: The algorithm achieved a 100% success rate across all test cases.
  • Computational Efficiency: Training for all required subproblems took only 155 seconds on a standard PC. Once trained, the agent can solve an arbitrary puzzle in approximately 0.25 seconds.
  • Solution Quality: The average solution length was 123 moves. While this is longer than the optimal average (approximately 52 moves, with a maximum of 80), the trade-off provides a significant gain in computational speed and generalizability.

Discussion and Conclusion

Local Value-Iteration proves that a "divide and conquer" strategy can effectively bypass the curse of dimensionality in combinatorial puzzles. While the solutions are sub-optimal in terms of path length, the method guarantees a solution with minimal computational overhead.

Future research could explore balancing the "local window" size to improve solution optimality or applying this hierarchical decomposition to other complex combinatorial problems. This work formalizes the intuition that local heuristics, when mathematically structured, can outperform brute-force global searches in high-dimensional state spaces.

Summary updated

Abstract

The 15-puzzle is a well-known game which has a long history stretching back in the 1870's. The goal of the game is to arrange a shuffled set of 15 numbered tiles in ascending order, by sliding tiles into the one vacant space on a 4×4 grid. In this paper, we study how Reinforcement Learning can be employed to solve the 15-puzzle problem. Mathematically, this problem can be described as a Markov Decision Process with the states being puzzle configurations. This leads to a large state space with approximately 1013 elements. In order to deal with this large state space, we present a local variation of the Value-Iteration approach appropriate to solve the15-puzzle starting from arbitrary configurations. Furthermore, we provide a theoretical analysis of the proposed strategy for solving the 15-puzzle problem. The feasibility of the approach and the plausibility of the analysis are additionally shown by simulation results.
BibTeX
@inproceedings{bischoff2013solving,
  author = {Bastian Bischoff and Duy Nguyen-Tuong and Heiner Markert and Alois C. Knoll},
  title = {{Solving the 15-Puzzle Game Using Local Value-Iteration}},
  booktitle = {SCAI},
  year = {2013},
  doi = {10.3233/978-1-61499-330-8-45},
}
Figure