🎮 How to Play
- Click any tile adjacent to the empty space to slide it.
- Goal: arrange tiles 1-15 in order with the blank in the bottom-right.
- Track moves and time to compete with yourself.
About this tool
15-puzzle: 4×4 grid with tiles numbered 1-15 and one empty space. Slide tiles into the empty space. Goal: 1-15 in order with empty in bottom-right. Invented in 1870s by Noyes Chapman. Half of all configurations are unsolvable.
About the 15-Puzzle
The 15-Puzzle is a sliding tile puzzle on a four-by-four grid that holds tiles numbered 1 to 15 plus one empty square. Sliding any tile orthogonally adjacent to the empty square into that square is one move; the goal is to reach the ordered configuration with 1 in the top-left, 15 in the bottom-right, and the empty square in the corner. Noyes Chapman is credited with the original 1880 craze ("the 15 Puzzle Mania") that swept the United States and Europe and offered a 1,000 dollar prize Sam Loyd later marketed for an unsolvable scramble.
The puzzle is the simplest non-trivial case of a broader family that includes 8-puzzle (3x3) and 24-puzzle (5x5). It became a textbook example in algorithms courses because the state space of about 10.5 trillion reachable configurations is large enough to be interesting yet small enough for IDA* with the Manhattan distance heuristic to solve any instance in seconds.
How solvability works
Exactly half of the 16! permutations of tiles plus blank are reachable from any starting position. A scramble is solvable when the parity of the permutation matches the parity of the blank's row distance from the bottom. Concretely:
- Count inversions: pairs of tiles (i, j) where i appears before j in row-major order but i > j.
- For a 4x4 board, the scramble is solvable when (inversions + row of blank counted from bottom) is even.
- Loyd's famous 14-15 swap fails this parity check by one inversion, which is why the prize was never claimed.
God's number for the 15-Puzzle is 80: every solvable instance can be solved in at most 80 single-tile moves, proven exhaustively by Brüngger, Marzetta, Fukuda, and Nievergelt in 1999 and refined by Korf in 2005.
Worked example: solving the first row
Starting scramble (reading top-left to bottom-right): 5 1 2 4 / 9 6 3 8 / 13 10 7 11 / 14 15 12 _. The standard human strategy solves row by row, then column by column, finishing with a 2x2 corner:
- Place 1: slide 1 to the top-left. Cost: 3 moves.
- Place 2 and 3: slide them into a 2-3 staging pattern, then rotate. Cost: 6 moves.
- Place 4 with the corner trick: park 4 below its target, place 3, then rotate. Cost: 5 moves.
- Repeat for row 2: tiles 5, 6, 7, 8. Cost: typically 18 to 22 moves.
- Solve bottom 2x2: 9, 10, 13, 14 cycle into place. Cost: 6 to 12 moves.
15-Puzzle quick reference
| Property | Value |
|---|---|
| Grid size | 4 x 4 = 16 squares (15 tiles + 1 blank) |
| Reachable states | 16! / 2 = 10,461,394,944,000 |
| God's number (max moves) | 80 (Korf, 2005) |
| Average optimal solution | ~53 moves |
| Human speedsolve world record (single) | 4.85 s (NS, 2019) |
| Solvability test | (inversions + blank row from bottom) even |
| Inventor | Noyes Palmer Chapman, ~1874 |
Common pitfalls
- Solving last row first. The bottom row cannot be ordered tile-by-tile because each placement traps the previous one. Solve top down, then finish with a 2x2.
- Placing the corner tile too early. When closing row 1, place tile 4 using the "park-rotate" technique: park 4 at position 8, place 3 next to 2, then rotate. Direct placement gets stuck.
- Believing every scramble is solvable. Half of all random permutations are unreachable. The Shuffle button on this page applies legal moves so it always returns a solvable position.
- Ignoring the blank-square invariant. The blank ends in the bottom-right corner. Any sequence that ends with the blank elsewhere has not solved the puzzle by the standard definition.
- Counting tile slides as cell moves. A single slide is one move regardless of distance because only the blank-adjacent tile actually moves; do not count a "slide three tiles along a row" as three moves until you press three times.
- Treating the 8-puzzle and 15-puzzle as identical. The 3x3 8-puzzle has God's number 31; tactics that work in 3x3 (like the L-shape trick) generalise but the move counts are different.
Related puzzles on 3Tej
Frequently asked questions
Is every scramble actually solvable?
Only half of the 16! random permutations are reachable from the solved state, so a truly random scramble has a 50% chance of being unsolvable. The Shuffle button on this page generates scrambles by applying random legal moves to the solved board, which guarantees the result stays inside the reachable half. Sam Loyd's 1880 "14-15 swap" challenge was unsolvable for exactly this parity reason.
What is God's number for the 15-Puzzle?
80 single-tile moves. Richard Korf and others proved in 1999 to 2005 that every solvable starting position can be reached in at most 80 moves, and that this bound is tight: there exist scrambles requiring exactly 80 optimal moves. Average optimal solution length is about 53 moves.
How do I check if my scramble is solvable?
Read the tiles in row-major order ignoring the blank, count inversions (pairs where a larger number appears before a smaller one), and add the row of the blank counted from the bottom (1, 2, 3, or 4). If the sum is even, the scramble is solvable. If odd, it is not.
What is the human speedsolving record?
The single-solve record on a physical 15-puzzle stands at 4.85 seconds, set in 2019. Top finger-style solvers average around 7 to 9 seconds and execute roughly 7 to 10 moves per second. The touchscreen tap version on this page is naturally slower because each move requires a separate tap.
Why is solving row by row recommended?
Row-by-row decomposition lets you "lock" already-solved tiles and shrinks the working area at each step. Once row 1 is solved you treat rows 2 to 4 as a 3x4 sub-problem; after row 2 you have a 2x4 region. The final 2x2 has only 12 reachable states and a known recipe of at most 6 moves, so the hard part is always the first two rows.