24-Puzzle Solver

The 5x5 sliding puzzle, or 24-puzzle, is a puzzle game consisting of a square grid of 25 squares (5 rows and 5 columns).

This grid contains 24 tiles numbered from 1 to 24 and one empty space. The objective is to rearrange the tiles to achieve a target configuration (usually the ascending numerical order from 1 to 24, leaving the empty space in the last position). Movement is made only by sliding an adjacent tile into the empty space (up, down, left, or right), which moves the empty space to the tile's previous position.

The solvability of a 5x5 sliding puzzle relies on the parity of the permutations. Since the grid width is odd, a configuration is solvable if and only if the total number of inversions is even.

An inversion is defined as any pair of tiles $ (i, j) $ such that $ i > j $ while $ i $ precedes $ j $ when reading the grid linearly (row by row, from left to right).

If the number of inversions $ I $ is odd, the position belongs to the set of configurations that are physically inaccessible from the ordered state.

Several variations modify the combinational structure or the rules of movement:

— N-times-N-puzzles: simpler formats like 3x3 (8-puzzle) or 4x4 (15-puzzle), and more complex ones beyond that.

— Constraint-based puzzles: the presence of fixed squares (walls) or irregularly shaped tiles.

— Toroidal puzzle: the edges are connected, allowing a tile that exits on the right to reappear on the left.

— Graphic puzzle: uses a cut-out image instead of numbers, which can introduce ambiguities in solving if tiles are visually identical.

— 3D puzzle: uses movement in three dimensions, often used in wooden puzzles.

The state space of a 5x5 puzzle is immense. For 25 positions, there are 25! theoretical arrangements. Since only half of these positions are accessible by sliding, the number of solvable configurations is defined by the formula $ \frac{25!}{2} $

This represents approximately $ 7.7 \times 10^{24} $ configurations, which is more than the number of configurations of the classic Rubik's Cube ($ 4.3 \times 10^{19} $)

The maximum number of moves required to solve any solvable configuration (often called the God Number) is not yet known precisely for the 5x5 format, but estimates suggest that the diameter of the graph exceeds 200 moves.