8-Puzzle Solver

A 3x3 sliding puzzle, also called an 8-puzzle, is a game consisting of a grid of 9 squares (3 rows and 3 columns) containing 8 numbered tiles from 1 to 8 and one empty square.

The objective is to rearrange the tiles in ascending order (usually from 1 to 8, with the empty square in the last position) by successively sliding an adjacent tile towards the empty square, in any direction (up, down, left or right).

A 3x3 configuration is solvable if the total number of inversions in the sequence of tiles (ignoring the empty space) is even.

An inversion is a pair of tiles $ (i, j) $ such that $ i > j $ and $ i $ appears before $ j $ in a row-by-row reading (from left to right, then top to bottom), ignoring the empty tile.

If $ I $ is even, the configuration has a solution.

If $ I $ is odd, the configuration is unsolvable and has no solution.

Several variations exist:

— N × N sliding puzzle: larger grids (15-puzzle, 24-puzzle, etc.). The search complexity increases rapidly.

— Puzzle with constraints: some squares may be blocked or certain moves prohibited.

— Toroidal sliding puzzle: the left/right and top/bottom edges are connected.

— Higher-dimensional sliding puzzle: extensions into 3D where moves occur in a volumetric space.

Each variation modifies the combinatorial structure of the problem and its solvable properties.

The total theoretical space of arrangements of the 9 squares is $ 9! = 362880 $. However, only half of these configurations are attainable due to the parity constraint of the permutations. The exact number of solvable configurations is therefore: $ \frac{9!}{2} = 181440 $. This means that there are 181440 distinct starting positions.

For the 3x3 (8-puzzle), the maximum number of optimal moves required to solve a solvable position is 31. This bound was determined by computer-assisted exhaustive exploration.