Sliding Puzzle Solver —
8-puzzle & 15-puzzle with A* & IDA*.

Computer science guide

A*, IDA*, and the sliding puzzle: explained.

The sliding puzzle, a grid of numbered tiles with one blank space, is one of the most famous combinatorial puzzles in history and a cornerstone problem in artificial intelligence. Solving it optimally requires finding the shortest sequence of moves from any scrambled state to the goal, a challenge that motivated some of the most important algorithms in computer science.

A brief history of the 15-puzzle craze

The 15-puzzle was invented around 1874 by Noyes Palmer Chapman, a postmaster in New York, and popularized worldwide in 1880 by puzzle entrepreneur Sam Loyd. The puzzle swept the United States and Europe in a craze comparable to the Rubik's Cube a century later. Newspapers offered cash prizes for solutions, and workers neglected their duties to play it. Loyd famously offered a $1,000 prize (never collected) for solving a specific configuration; one he knew was mathematically impossible. This led directly to the first rigorous analysis of which configurations of the 15-puzzle are solvable and which are not.

Mathematician William Edward Story proved in 1879 that exactly half of the 16!/2 ≈ 10¹³ possible configurations of the 15-puzzle are reachable from the goal state: the solvable half. The other half can never reach the goal regardless of how many moves are made. The same is true for the 8-puzzle: half of the 9! = 362,880 arrangements (181,440 states) are solvable.

The A* search algorithm

A* (pronounced "A-star") is an informed search algorithm developed by Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford Research Institute in 1968. It finds the shortest path from a start state to a goal state in a weighted graph; in the puzzle context, each tile move has cost 1, and we want the minimum total moves.

A* maintains two key values for every state it explores:

• g(n): The exact cost (number of moves) from the start state to the current state n.
• h(n): The heuristic: an estimated cost from state n to the goal. Must never overestimate the true cost (this is called being "admissible").
• f(n) = g(n) + h(n): The estimated total cost through state n. A* always expands the open state with the lowest f(n) value.

When h(n) is both admissible (never overestimates) and consistent (satisfies the triangle inequality), A* is guaranteed to find the optimal solution and will never re-expand a state. For the 8-puzzle, A* typically finds the solution while exploring fewer than 100,000 states out of the 181,440 , much faster than brute-force search.

Manhattan distance heuristic

The Manhattan distance (also called taxicab distance or L1 distance) of a puzzle state is the sum of the distances each tile needs to travel to reach its goal position, counting only horizontal and vertical steps (no diagonals):

This heuristic is admissible because tiles can only move one step at a time and cannot pass through each other; each tile needs at least its Manhattan distance in moves to reach its goal. It is far more informative than the simpler "number of misplaced tiles" heuristic, dramatically reducing the states A* needs to explore.

Linear conflict heuristic

Linear conflict is an additional term added to the Manhattan distance to create a tighter (still admissible) lower bound. Two tiles are in "linear conflict" when:

• Both tiles are in their goal row (or column), and
• They are in the wrong order relative to each other.

When this happens, at least one tile must move out of the row and back in again to let the other pass, adding a minimum of 2 extra moves beyond the Manhattan distance. For each pair of tiles in linear conflict, we add 2 to the heuristic. Combined with Manhattan distance, this can reduce the number of states explored by an order of magnitude, making IDA* fast enough for the 15-puzzle.

Why A* is impractical for the 15-puzzle

The 15-puzzle has approximately 10¹³ reachable states. A* stores all explored states in memory (the "closed list") to avoid revisiting them. For the 8-puzzle ; 181,440 states fit easily in RAM. For the 15-puzzle, storing millions or billions of states would exhaust the available memory of any computer.

Even with unlimited memory, A* would explore too many nodes for deeply scrambled 15-puzzle instances. The average optimal solution length is about 52 moves, and the search tree at that depth, even with pruning, can contain millions of nodes.

IDA*: Iterative Deepening A*

IDA* (Iterative Deepening A*), published by Richard Korf in 1985, solves the memory problem by combining the space efficiency of depth-first search with the optimality guarantee of A*. Instead of storing explored states, IDA* performs a series of depth-first searches with an increasing cost bound:

• Start with bound = h(initial state).
• Perform a depth-first search, pruning any path where f = g + h exceeds the current bound.
• If the goal is found, return the solution. If not, set the new bound to the minimum f value that exceeded the current bound and repeat.

IDA* uses only O(depth) memory, specifically the current path through the search tree, instead of O(states). With a tight heuristic like Manhattan distance plus linear conflict, the effective branching factor of IDA* on the 15-puzzle is approximately 1.5, meaning most instances with optimal solutions of 52 moves are solved by examining fewer than 500,000 nodes.

Solvability: why half of all configurations are impossible

Not all scrambled states can reach the goal. The mathematical reason involves the parity of permutations. Every tile arrangement can be described as a permutation of the numbers 0 through n²−1. Each legal tile move is equivalent to a transposition (a swap of two adjacent elements in the sequence). The goal state is an even permutation (zero transpositions from sorted order). Only states reachable by an even number of transpositions from the goal are solvable.

For the 8-puzzle (3×3): count the number of inversions in the tile sequence (excluding the blank). If the inversion count is even, the puzzle is solvable.

For the 15-puzzle (4×4): the rule also depends on the blank's row from the bottom. If the blank is on an even row from the bottom (rows 2 and 4 counting from bottom), the puzzle is solvable when the inversion count is odd. If the blank is on an odd row from the bottom (rows 1 and 3), solvable when the inversion count is even.

The state space explosion: why puzzles get hard

• 8-puzzle (3×3): 9!/2 = 181,440 reachable states. A* solves it optimally in milliseconds.
• 15-puzzle (4×4): 16!/2 ≈ 10,461,394,944,000 reachable states. IDA* with good heuristics solves most instances in under a second.
• 24-puzzle (5×5): 25!/2 ≈ 7.76 × 10²⁴ states. Requires pattern databases and more advanced heuristics to solve optimally.
• 35-puzzle (6×6): Essentially unsolvable optimally with current techniques, only approximate solutions are practical.