15puzzle

15puzzle is a sliding puzzle consisting of fifteen numbered tiles on a 4x4 grid with one empty space. A move consists of sliding a tile that is adjacent to the empty space into the space. The standard goal state has the tiles arranged in increasing order by row from top left to bottom right, with the empty space in the bottom-right corner.

The puzzle was introduced in the late 19th century and became a worldwide fad in the 1870s and 1880s. It was popularized in the United States by promoter Sam Loyd, although the precise origins are disputed. The public story around Loyd’s promotional puzzles helped propel the craze that accompanied the puzzle’s spread into toy stores and newspapers.

Not all configurations of the 15 puzzle are solvable. A position is solvable if the parity of the permutation of the tiles, together with the row position of the empty space from the bottom, satisfies a parity condition specific to the 4x4 board. In practice, this means that roughly half of the 16! possible arrangements are reachable from the solved state. The total number of distinct reachable states is 16!/2, about 10.46 trillion.

Solving the puzzle typically uses heuristic search. Algorithms such as A* with Manhattan distance or other admissible heuristics can find optimal solutions, and the worst-case optimal solution length for the 4x4 puzzle is 80 moves. Researchers also use pattern databases and other techniques to speed up solving.

Variants include the 8-puzzle (3x3) and larger NxN sliding puzzles, which share the same rules and solvability considerations but differ in state space size and difficulty. The 15-puzzle remains a classic example in artificial intelligence and combinatorial search.