Rules

The 15-puzzle is a 4×4 grid containing 15 numbered tiles and one blank space. Tiles adjacent to the blank space can slide into it. The goal is to arrange the tiles in numerical order (1–15, left to right, top to bottom) with the blank in the bottom-right corner.

Controls: click any tile that is adjacent to the blank space to slide it into the blank. On mobile, tap the tile.

History

The 15-puzzle was invented around 1878 and became a nationwide craze in the United States. Legend credits Noyes Palmer Chapman, but the puzzle was widely distributed by puzzle entrepreneur Sam Loyd (who falsely claimed to have invented it). Loyd famously offered a $1,000 prize for solving a specific scrambled configuration - one that is mathematically unsolvable, guaranteeing he would never need to pay.

Solvability

Exactly half of all 15-puzzle configurations are solvable. A position is solvable if and only if the number of tile inversions (pairs of tiles out of order) plus the row distance of the blank from its solved position is even. This generator always produces solvable puzzles.

Solving strategy

Solve row by row: place tiles 1, 2, 3, 4 in the top row first, then work on rows 2 and 3. The bottom two rows can be solved together.
Use a cycle for the last two in a row: tiles at the end of a row often need a specific 5-move rotating cycle to be placed without disrupting already-solved tiles.
Avoid scrambling solved tiles: once a row is complete, restrict your moves so those tiles are never disturbed by subsequent solving moves.

Fun fact

Solving the n-puzzle in the minimum number of moves is NP-hard in the general case - it gets exponentially harder as the grid size grows. The A* search algorithm with the Manhattan distance heuristic is the standard approach for computer solvers.

AI solver: A* with Manhattan distance

The most common computer algorithm for solving the 15-puzzle is A* search with the Manhattan distance heuristic. The Manhattan distance for a tile is the sum of the horizontal and vertical distance from its current position to its goal position. Summing the Manhattan distances of all tiles gives a lower bound on the number of moves required - this admissible heuristic guarantees A* finds the optimal (minimum-move) solution.

Pattern database heuristics (storing pre-computed distance tables for subsets of tiles) further speed up the solver for competitive implementations. The IDA* algorithm (iterative-deepening A*) is preferred over standard A* when memory is limited, since it searches depth-first and avoids storing large open sets.

Optimal move count

A uniformly random scramble of the 15-puzzle requires an average of approximately 52 moves to solve optimally. This result, from Brüngger et al. (1999), is the average over all solvable configurations. The hardest positions require up to 80 moves.