How to Solve the 15 Puzzle: A Row-by-Row Method
A reliable method for any sliding puzzle: solve the top rows, park the last two tiles of each row as a pair, then finish the bottom two rows column by column.
· 6 min read
In 1880 newspapers across the United States printed a sliding puzzle with the 14 and 15 swapped and offered cash to anyone who could put them back in order. Nobody collected, because nobody could: a year earlier, two mathematicians had proved that exactly half of all arrangements of the 15 puzzle can never be solved. The other half can all be solved by one method that needs no luck and no memorised move lists, only a few patterns. This guide walks through that method on a 4 by 4 board and shows how it scales to any size.
You can follow along on the Fifteen Puzzle, which deals only solvable boards from 2 by 2 up to 12 by 12.
Why half the shuffles are impossible
Read the tiles left to right, top to bottom, ignoring the gap, and count inversions: pairs where a bigger number comes before a smaller one. The solved board has zero. Sam Loyd's famous 14-15 swap has exactly one.
Every slide moves one tile past the gap. A sideways slide changes nothing in reading order. A vertical slide moves a tile past the other tiles in its row, which on a 4-wide board changes the inversion count by an odd number and also moves the gap one row. Put together, the parity of (inversions + gap row counted from the bottom) never changes. With the gap in the bottom-right corner, that means:
| Board width | Gap position | Solvable when |
|---|---|---|
| Odd (3, 5, 7...) | Anywhere | Inversions are even |
| Even (4, 6, 8...) | Row r from the bottom | Inversions + r is odd |
| Any | Bottom-right corner | Inversions are even |
A single swap of two tiles flips the inversion parity, so it moves a board from the solvable half to the unsolvable half or back. William Johnson and William Story published the proof in 1879. Any puzzle app that shuffles by randomly placing tiles has to apply this test, or half its boards are impossible. The RedBison puzzle shuffles, counts inversions and swaps two tiles when the count is odd.
The method: rows first, then columns
The idea is to shrink the puzzle. Solve the top row, and the remaining board behaves like a 3-row puzzle. Solve the second row, and you are left with a 2 by 4 strip. Solve that strip one column at a time from the left. The same method works on a 3 by 3 (one row, then a 2 by 3 strip) and on a 12 by 12 (ten rows, then a 2 by 12 strip).
The only rule: once a tile is in its final place, avoid moving it, except during the short pair manoeuvres below, which put things back.
Step 1: the top row
Place 1 and 2 directly. To move a tile one square in some direction, bring the gap to the far side of the tile without disturbing solved tiles, then slide the tile into the gap. Repeat. Moving a tile one square to the right costs about five slides once the gap is next to it, because the gap has to walk around the tile.
Tiles 3 and 4 need a trick, because placing 3 and then 4 would push 3 out of the corner. Treat them as a pair:
- Put 4 in position 3 (the third square of the top row).
- Put 3 directly below it, in the second row.
- Bring the gap to the top-right corner (position 4).
- Slide 4 right, then 3 up. Both are now home.
If 3 lands in the corner while you are working, move it out at least two squares and redo the pair. Trying to wriggle it is how people lose ten minutes.
Step 2: the second row
Repeat exactly the same steps for 5, 6, 7 and 8: place 5 and 6 directly, then park 8 in the position of 7 with 7 underneath and rotate them in. You now have the top half solved and a 2 by 4 strip below: 9, 10, 11, 12 on top and 13, 14, 15 and the gap on the bottom.
Step 3: the last two rows, column by column
Now flip the idea by 90 degrees and solve columns from the left, again in pairs:
- Put 13 in position 9 (the left square of row three).
- Put 9 directly to its right, in position 10.
- Bring the gap to the bottom-left corner (position 13).
- Slide 13 down, then 9 left. The first column is done.
Do the same for 10 and 14 in the second column. You are left with a 2 by 2 square holding 11, 12 and 15 and the gap. Rotate the three tiles around the square until they read 11, 12 on top and 15 bottom left. If they line up in the wrong cyclic order no matter how you rotate, the board was unsolvable, which cannot happen with a correctly shuffled puzzle.
A worked opening
Suppose the shuffle puts 1 in the third row, second column, with the gap in the bottom-right corner. Tile 1 has to travel two rows up and one column left. Walk the gap along the bottom row and up the first column until it sits directly above 1, then slide 1 up. Walk the gap around 1 (not through it) to the square above it again and slide 1 up a second time. Finally bring the gap to the left of 1 and slide 1 left into the corner. Each step is the same loop: gap to the side 1 should move toward, slide, repeat. Counting on a real board, a tile that travels three squares usually costs 15 to 20 slides, and the whole first row 40 to 70.
Common mistakes
- Placing the last tile of a row directly. It always disturbs the tile before it. Use the pair park.
- Moving the gap through solved tiles. Route around them, even when it is longer.
- Solving rows to the bottom. The bottom two rows must be solved as columns; the row method has no room left.
- Panicking when a tile lands in the corner too early. Move it two squares away and redo the pair.
- Measuring yourself against computer solutions. Every solvable 4 by 4 position can be solved in at most 80 moves, but finding those solutions takes a computer search. A clean human solve with this method is 150 to 300 moves.
Bigger boards and better times
On 5 by 5 and above, use the same steps: rows from the top until two remain, then columns from the left. Each solved row or column turns the puzzle into a smaller one, so a 6 by 6 becomes a 4 by 4 after two rows and two columns. The 3 by 3 is a good place to drill the pair manoeuvres, because a mistake costs seconds rather than minutes.
Once the method is automatic, work on the move counter rather than the timer: shorter gap routes are where the savings are. Related puzzles worth a look are 2048 for planning chains and Sudoku for pure deduction, both covered in the browser games guide.
Start with a 3 by 3 tonight, solve it three times with the pair park, then move to 4 by 4. The method is the same; only the strip at the end gets longer.