Sliding Puzzle Solver

The sliding puzzle is a permutation game played on a grid of size $ n \times n $ (usually 4x4). It consists of $ n^2 - 1 $ numbered tiles and one empty square.

The goal is to reach a target configuration (often ascending order) by sliding the tiles orthogonally.

To solve the sliding puzzle efficiently by hand, use a progressive reduction strategy.

— Solve the first row: place tiles $ 1, 2, 3, \dots $ in order. The last two tiles in the row must be positioned together to avoid a blockage.

— Then solve the first remaining column using the same principle.

— Repeat this process: after fixing one row and one column, the problem reduces to a grid of size $ (n-1) \times (n-1) $

When the size reaches $ 3 \times 2 $, use local cycles (block rotations) to swap the last tiles until the target state is reached.

This method is constructive and simple to execute, but it does not guarantee a minimum number of moves.

To obtain an optimal solution (minimum number of moves), the reference algorithm is A*. It is based on an evaluation function $ f(n) = g(n) + h(n) $ where:

$ g(n) $ is the actual cost from the initial state (number of moves made),

$ h(n) $ is a heuristic estimate of the remaining cost.

If $ h $ is admissible (never overestimates the actual cost), A* guarantees optimality.

However, for a 4x4 sliding puzzle, the state space reaches about $ 10^{13} $ accessible configurations. A* requires storing a large number of open and closed states, which becomes prohibitive in terms of memory.

The IDA* (Iterative Deepening A*) variant combines A*'s cost bound with a depth-limited search. It performs several successive searches, progressively increasing the $ f(n) $ threshold. It uses much less memory while maintaining optimality with an admissible heuristic.

The performance of A* or IDA* is highly dependent on the quality of the heuristic $ h $.

— Manhattan distance: $ h = \sum_i \left( |x_i - x_i^| + |y_i - y_i^| \right) $ : it adds the horizontal and vertical distances of each tile from its target position. It is admissible and consistent, but ignores interactions between tiles.

— Linear Conflict: Manhattan Expansion: If two tiles are in their target row (or column) but in reverse order, at least two more moves will be required. Add $ +2 $ per detected conflict. This heuristic remains admissible.

— Pattern Databases (PDBs): they consist of precalculating exactly, by inverse search, the minimum cost to place a given subset of tiles. The values are stored in an indexed table. By combining several disjoint bases, it is possible to obtain very informative heuristics while remaining admissible.

Starting from the final (solved) state, apply a number of random moves to the empty cell. Solubility is guaranteed because each move corresponds to a allowed permutation within the group of reachable states.

Checking whether a state is solved is trivial and can be done in $ O(n^2) $.

However, finding an optimal solution for a generalized sliding puzzle of variable size $ n \times n $ is NP-hard.

For the classic 4x4 grid, the maximum number of moves required to reach the optimal solution (sometimes called the God's number) is $ 80 $ (compared to $ 31 $ for the 3x3).

The total number of permutations of the $ n^2 $ positions is $ (n^2)! $.

However, only half are reachable from a given state due to the parity constraint.

The number of accessible states is therefore: $ \frac{(n^2)!}{2} $.