Sliding Puzzle (8-puzzle)
Slide tiles on a 3×3 board to reach the goal arrangement. A classic state-space search puzzle. Click any tile adjacent to the empty space to slide it. Arrange the tiles in numerical order (1-8) with the empty space in the bottom-right corner.
The 8-puzzle and its history
The 8-puzzle (a 3×3 sliding-tile puzzle) is a descendant of the 15-puzzle (4×4), which became a worldwide craze in 1880. The 15-puzzle was popularized — and likely invented — by American puzzle maker Sam Loyd, who offered a $1,000 prize to anyone who could solve the famous "14-15 puzzle" (the standard 15-puzzle with tiles 14 and 15 swapped). The prize was never claimed because the configuration is mathematically unsolvable: the parity of a permutation determines whether a given arrangement can be reached from the goal state through legal moves, and the 14-15 swap has the wrong parity.
Our version uses the 3×3 grid (8 numbered tiles + 1 empty space) rather than the 4×4, which is harder. The 3×3 puzzle is small enough that you can typically solve it by inspection in 30-100 moves, depending on how scrambled the start is. We guarantee that every shuffle is solvable (we generate it by making random legal moves from the solved state, rather than by random permutation).
How to solve it
Most people develop an intuitive strategy after a few attempts. The standard approach is to solve the puzzle row by row, then column by column:
- Solve the top row first. Get tiles 1, 2, and 3 into their correct positions. The trick is to place 1 and 2, then maneuver 3 into place without disturbing them.
- Solve the left column. Get tiles 4 and 7 into position.
- Solve the remaining 2×2. With the top row and left column fixed, the remaining 2×2 (tiles 5, 6, 8 and the empty space) can always be solved by cycling the empty space around the 2×2.
Worked example
Suppose the grid currently has tile 1 in position (row 2, col 1), the empty space in (row 1, col 1), and tile 2 in (row 1, col 2). To get tile 1 to (row 1, col 1), you need to move the empty space adjacent to tile 1 — which it already is. Slide tile 1 up into the empty space. Now tile 1 is home.
The principle generalizes: to move any tile to a target position, you first maneuver the empty space next to the tile on the side opposite to where you want the tile to go, then slide the tile.
The mathematics
The 8-puzzle has 9! / 2 = 181,440 reachable states (the /2 reflects the parity constraint: half of all permutations are unreachable from the goal). For any solvable starting position, the shortest solution is at most 31 moves. For the 15-puzzle (4×4), the equivalent number is 80 moves, and the state space is roughly 10 trillion — far too large to solve by brute force without an informed search algorithm like A*.
Why computer scientists care
The sliding-tile puzzle is a textbook example in artificial intelligence. It is used to teach state-space search: representing each puzzle configuration as a node in a graph, defining legal moves as edges, and using algorithms like breadth-first search, A* with the Manhattan-distance heuristic, or IDA* to find the shortest solution. The Manhattan-distance heuristic — the sum of the taxicab distances of each tile from its goal position — is admissible (never overestimates), which means A* with this heuristic is guaranteed to find the optimal solution.