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