15 Puzzle

The 15 Puzzle (also called Boss Puzzle, Game of Fifteen, Mystic Square) is the 4×4 sliding-tile puzzle invented in 1880 by Noyes Chapman, an American postmaster. Fifteen numbered tiles sit in a 4×4 grid with one empty space; slide tiles into the empty space to rearrange them into numerical order (1-15 with the blank in the bottom-right). Despite looking simple, the 15 Puzzle launched one of the biggest puzzle crazes of the 19th century, and mathematicians proved that exactly half of all random shuffles are unsolvable.

How to play

• 4×4 grid with 15 numbered tiles (1-15) and one empty space.
• Click on a tile adjacent to the empty space to slide it into the empty space.
• Continue sliding until the tiles are arranged in order: 1, 2, 3, 4 in the top row, 5, 6, 7, 8 in the second, …, 13, 14, 15 in the bottom-left positions, blank in the bottom-right.
• Minimum solution length: depends on the starting position, but typical is 50-80 moves.
• Optimal solution exists for every solvable starting position.

The math: half are unsolvable

The 15 Puzzle has 16! = 20,922,789,888,000 possible permutations. But exactly HALF (10,461,394,944,000) are unsolvable. The proof relies on parity arguments: each tile slide is a transposition. Solvable states are those reachable from the goal by an even number of transpositions.

• If you randomly arrange the tiles, there’s a 50% chance the puzzle is unsolvable.
• Modern implementations only generate solvable shuffles (using verified random walks from the goal).
• God’s number: the maximum minimum solution length is 80 moves. The starting position requiring 80 is one of only 17 specific arrangements.

Beginner strategy

• Solve top row first, then bottom row, then middle. Top row: place 1, 2, 3, 4 in order.
• Use the “corner technique” for end of rows. When placing tile 4, use a temporary position for tile 3, then slide both into final.
• Don’t break solved rows. Once row 1 is solved, never move those tiles again.
• Use the blank as your manipulator. Think of the blank moving around — you’re not moving tiles, you’re moving the blank.
• Patience. 50-80 moves is normal. Don’t rush.

Intermediate strategy: solving in layers

• Layer-by-layer. Top row, then middle rows, then bottom row. Each layer locks in.
• The “twin” trick. For the last 3 tiles in a row, place them in a temporary L-shape, then cycle them into final position.
• Column-by-column for last rows. When solving the bottom two rows, work column-by-column instead of row-by-row.
• Pattern memorization. Standard 15 Puzzle solutions use ~15 distinct sub-patterns. Memorize them.
• Speed solving. Top speed solvers complete the puzzle in 25-40 seconds.

Advanced strategy

• Optimal solution algorithms. A* search with Manhattan distance heuristic finds optimal solutions efficiently. 15 Puzzle is a standard CS benchmark.
• Pattern databases. Pre-computed lookup tables for sub-state solutions enable instant optimal play.
• Move count minimization. Beyond just solving, top solvers find solutions in 50-60 moves where beginners take 200+.
• The 17 “extremal” positions. Only 17 configurations require the full 80-move maximum solution. These are mathematically known.
• Generalized n-puzzle. 8 Puzzle (3×3), 24 Puzzle (5×5), 35 Puzzle (6×6) follow same principles.

The 1880 puzzle craze

• 1880 — Noyes Chapman: creates the 15 Puzzle in New York. Mass-produced quickly.
• 1880-1881 — international craze: the puzzle becomes a worldwide sensation, comparable to Rubik’s Cube in the 1980s.
• Reports of obsession: newspapers reported people losing jobs, getting injured solving the puzzle in the streets.
• 1880 — Sam Loyd’s $1,000 prize: Loyd offered $1,000 (huge sum then) to anyone who could solve an UNSOLVABLE configuration (swapping the 14 and 15 from the goal). Nobody could; the puzzle was unsolvable from that start.
• The parity proof: Johnson and Story (1879) published the parity proof showing half of all shuffles are unsolvable.
• 1981 — Rubik’s Cube fills the void: sliding-tile puzzles fall out of favor; Rubik’s Cube becomes the dominant manipulative puzzle.

Common mistakes

• Trying to solve all at once. Layer-by-layer is the only systematic approach.
• Breaking solved rows. Once a row is locked, don’t move its tiles.
• Forgetting parity. If your puzzle starts unsolvable (rare with modern apps), no amount of effort solves it.
• Counting moves while solving. Counts distract from solving. Solve first, optimize later.

Variants

• 8 Puzzle. 3×3 grid with tiles 1-8 and one blank. Easier — God’s number is 31.
• 24 Puzzle. 5×5 grid. God’s number is 152.
• Rubik’s 15. Slide-puzzle Rubik’s variant with rotating elements.
• Picture sliding puzzle. Instead of numbers, the tiles form an image when correctly assembled.
• The blind 15 Puzzle. Solve without seeing intermediate states.

FAQ

• Q: Why is half of all shuffles unsolvable? A: Each tile slide is a transposition of two cells. Solvable positions are those reachable from the goal by an even number of transpositions. Random shuffles split 50/50.
• Q: What’s God’s number? A: 80 — the maximum minimum solution length for any solvable position.
• Q: Why is it called “15 Puzzle”? A: 15 numbered tiles + 1 blank = 16 cells in the 4×4 grid.
• Q: Can I solve any position in 80 moves? A: No — most positions need 50-70 moves. Only 17 specific arrangements require the full 80.

For other sliding/puzzle games, try Sliding Puzzle, Tower of Hanoi, Lights Out, or Sudoku.