15-Puzzle Solver

A 15-puzzle is a 4x4 sliding puzzle game consisting of a 16-square grid (4 rows × 4 columns) containing 15 numbered tiles from 1 to 15 and one empty square.

The objective is to rearrange the tiles in ascending order by successively sliding an adjacent tile into the empty square (up, down, left, or right).

A 4×4 sliding puzzle (even-width grid) is solvable if and only if the following condition is met: $ I + r $ is odd, where $ I $ is the total number of inversions (pairs of tiles $ (i, j) $ such that $ i > j $ with $ i $ appearing before $ j $ in the grid read row by row), and $ r $ is the position of the empty square counting rows from the bottom (1 for the last row, 2 for the second-to-last, etc.).

For the state [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 0], there is only one inversion $ (15,14) $, so $ I = 1 $, and the empty square is on the first row from the bottom, so $ r = 1 $. Since $ I + r = 2 $ is even, this configuration is unsolvable.

Yes, several variations exist:

— N×N puzzle: larger grids (for example, 5×5 or 6×6), whose complexity grows exponentially with $ N $.

— Puzzle with constraints: some squares are blocked, or some tiles can only move according to specific rules.

— Toroidal (wrap-around) puzzle: the edges are connected, which profoundly alters the structure of the state graph.

— 3D puzzle: a cube-based extension, like the Rubik's Slide here (affiliate link) where moves occur in three dimensions.

The theoretical space of configurations is $ 16! $, but only $ \frac{16!}{2} = 10461394944000 \approx 10^{13} $ configurations are attainable in practice because of a parity constraint.

The maximum number of optimal moves required to solve any solvable position is 80. This bound was established by computer-assisted exhaustive analysis.

There are 17 initial positions requiring 80 moves.

Several algorithms are suitable, with trade-offs between optimality, computation time, and memory usage:

— A*: an optimal and complete heuristic search algorithm if the heuristic is admissible and consistent. It uses $ f(n) = g(n) + h(n) $, where $ g(n) $ is the path cost from the initial state and $ h(n) $ is an estimate of the remaining cost (for example, the Manhattan distance enhanced by Linear Conflict, which remains admissible when correctly calculated).

— IDA*: a variant of A* that performs depth-first searches with an increasing cost threshold; it explores fewer nodes in memory at the cost of re-explorations.

— BFS (Breadth-First Search): theoretically optimal and complete, but impractical for 4x4 due to the combinatorial explosion of the state space.

— Metaheuristic methods: genetic or simulated annealing algorithms that allow for faster approximation of solutions, without guaranteeing optimality.