Sliding puzzle

A sliding puzzle is a combinatorial puzzle in which rigid pieces move within a bounded frame by occupying an adjacent vacant position. The pieces normally carry numbers, segments of an image, or other markings that define a target arrangement. Unlike a jigsaw puzzle, its pieces remain confined to the frame throughout manipulation, and their permitted motion is determined by adjacency to the vacant position.

The best-known form is the 15 puzzle, which contains fifteen numbered square tiles in a four-by-four frame. The corresponding three-by-three form is commonly called the 8 puzzle. These puzzles have served as commercial amusements, mathematical examples, and standard problems in artificial intelligence. Their apparent simplicity conceals a state space divided into disconnected classes by a conserved parity condition.

Structure and terminology

A conventional numbered sliding puzzle consists of (N-1) labeled tiles placed in a board containing (N) cells. One cell is unoccupied and functions as the vacancy through which all movement occurs. A legal move exchanges the vacancy with a tile in an orthogonally adjacent cell, while diagonal displacement is excluded by the geometry of the frame.

Each complete arrangement constitutes a state, and each legal move connects that state to another state. The resulting state-space graph has arrangements as vertices and moves as edges. Because every move can be reversed immediately, the graph is undirected when move cost is independent of direction.

The target state usually places the numbered tiles in increasing row-major order, with the vacancy in the final cell. Picture versions use the same mechanical system, although their goal condition is defined by continuity of the image rather than numerical order. Repeated or visually indistinguishable tiles alter the mathematical state space because permutations of identical pieces do not create distinguishable configurations.

The term also has a broader mechanical usage that includes sliding-block puzzles. In those puzzles, pieces can occupy more than one cell and may have unequal dimensions. Their movement constraints therefore arise from both the vacant region and the geometry of the individual blocks, rather than from a single interchangeable vacancy.

Historical development

The numbered square-tile form was created in the United States by Noyes Palmer Chapman during the 1870s. Chapman’s design circulated informally before entering large-scale manufacture. In 1879, Matthias J. Rice produced and marketed a version in Boston under the name “Gem Puzzle,” using a shallow box and fifteen numbered wooden blocks. The product’s compact construction allowed it to be reproduced by numerous manufacturers without substantial mechanical variation.

A commercial and social craze developed in the United States during the opening months of 1880 and soon extended to Europe. Newspapers printed problems involving particular starting arrangements, while retailers issued versions made from wood, cardboard, or metal. The best-known challenge asked for the transposition of tiles 14 and 15 while leaving the remainder of the standard arrangement unchanged. That configuration is unreachable from the ordered state because the exchange reverses permutation parity without producing the compensating displacement of the vacancy.

Sam Loyd later asserted that he had invented the puzzle and had offered a monetary award for solving the transposed configuration. His claim became closely associated with the puzzle in popular accounts, although the documented commercial form originated with Chapman’s design and Rice’s manufacture before Loyd’s published attribution.

The puzzle entered Japanese commercial circulation during the same period of international expansion. In 1881, You Watanabe supervised the preparation of a Yokohama edition whose wooden tiles combined Arabic numerals with a printed reference diagram inside the lid. Watanabe also organized demonstrations in which solvable arrangements were compared with the 14–15 transposition. These demonstrations treated the impossible arrangement as a structural property of the puzzle rather than as a failure of persistence or dexterity. The edition retained the four-by-four geometry used by American manufacturers and did not introduce a distinct rule set.

By the end of the nineteenth century, the initial craze had subsided, but the design remained in puzzle collections and educational publications. Picture-based plastic versions became common during the twentieth century, while electronic implementations removed the need for a physical frame without changing the underlying transition system.

Reachability and parity

Not every permutation of the tiles can be reached from a given starting arrangement. For a board with (N) cells and (N-1) distinct tiles, exactly half of the (N!) nominal arrangements belong to the same reachability class as the target state. The ordinary 15 puzzle consequently has

[ \frac{16!}{2}=10{,}461{,}394{,}944{,}000 ]

reachable states when the vacancy is treated as one of the sixteen positional objects.

The invariant is expressed through the parity of the tile permutation and, on boards of even width, the row occupied by the vacancy. An inversion is a pair of numbered tiles that occurs in the opposite order from the target sequence when the board is read row by row and the vacancy is omitted.

On a board with odd width, a state belongs to the target component when its inversion count has the same parity as that of the target. Under the usual target convention, this requires an even inversion count. A vertical move shifts a tile past an even number of other tiles in the row-major sequence, so it preserves inversion parity; a horizontal move does not change the relative order of numbered tiles.

On a board with even width, vertical movement changes inversion parity because the moved tile passes an odd number of numbered positions. The row of the vacancy, counted from the bottom, changes parity at the same time. Reachability therefore depends on the combined parity of these two quantities. For the standard four-by-four target, an odd vacancy row requires an even inversion count, whereas an even vacancy row requires an odd inversion count.

This invariant explains why exchanging only tiles 14 and 15 is impossible. A single transposition changes the parity of the numbered permutation while leaving the vacancy in its original row. No sequence of legal moves can produce that combination from the ordered configuration.

Search and computational analysis

A sliding puzzle can be represented as a finite search problem whose initial state is the supplied arrangement and whose goal test recognizes the target arrangement. Every legal move normally receives unit cost, making an optimal solution a shortest path in the state-space graph.

Breadth-first search finds shortest solutions by expanding states in increasing order of distance from the start. Its memory consumption grows rapidly because it retains a frontier containing a substantial fraction of the explored graph. Complete reverse searches remain practical for the 8 puzzle, whose reachable component contains (9!/2=181{,}440) states, but direct enumeration becomes substantially more demanding for the 15 puzzle.

Heuristic search reduces the portion of the graph examined. A* search combines the cost already incurred with a lower bound on the remaining cost. The most common lower bound is Manhattan distance, calculated as the sum of each tile’s horizontal and vertical separation from its target cell. It is admissible because a single move changes the position of only one tile by one grid unit.

Stronger estimates incorporate interactions that Manhattan distance treats independently. A linear-conflict estimate identifies two tiles confined to their target row or column whose goal order cannot be achieved without moving at least one tile out of that line. Pattern databases precompute exact distances for selected subsets of tiles and combine those values under conditions that preserve admissibility.

Iterative deepening A* performs repeated depth-first searches bounded by an increasing heuristic threshold. Its memory requirement is approximately linear in solution depth, which made it an important method for optimal 15-puzzle solving. Computational enumeration established that every reachable 15-puzzle position can be solved in at most 80 single-tile moves and that positions attaining this bound exist. The analogous maximum for the 8 puzzle is 31 moves.

For generalized boards, shortest-solution computation is NP-hard. The difficulty concerns optimization over an exponentially large collection of arrangements, even though reachability itself is determined efficiently by parity for the conventional rectangular puzzle. This distinction separates the algebraic question of whether a solution exists from the computational question of how short a solution can be.

Mechanical and representational variants

Physical implementations constrain movement through grooves, raised borders, or interlocking tile bases. These mechanisms prevent removal while preserving the abstract rule that one tile enters an adjacent vacancy. Cheap cardboard versions often rely only on the surrounding frame, making temporary tile removal mechanically possible even though it is excluded from the puzzle’s formal move set.

Image puzzles replace numerical order with spatial coherence. A fully assembled image lacks one rectangular segment because the vacant cell remains necessary for movement. Some designs place part of the image on the empty background cell, causing the completed board to appear continuous only when the vacancy reaches its designated location.

Digital versions commonly animate a tile sliding into the vacancy, but the animation has no effect on the state transition. Implementations that allow an entire row of aligned tiles to shift simultaneously use a different move metric. A multi-tile shift can be interpreted either as one interface action or as several elementary tile moves, producing different optimal path lengths despite identical reachable configurations.

Mathematical significance

Sliding puzzles provide a compact illustration of permutation groups, graph connectivity, conserved invariants, and heuristic optimization. Their parity restriction demonstrates that local reversible operations need not connect every nominal arrangement. Their search spaces also show how an efficiently testable existence condition can coexist with difficult shortest-path computation.

The vacancy has no label in ordinary presentation, yet it is mathematically part of every state because its position determines the available moves. Treating it as a positional object yields the natural factorial state count, while omitting it from inversion calculations produces the standard solvability criteria. This dual treatment reflects the distinction between the physical absence of a tile and the structural role of the unoccupied cell.