If you have ever spent thirty minutes on a 15 puzzle that just will not finish — every move you make eventually leads to two tiles swapped at the end — there is a chance the puzzle is mathematically unsolvable. Exactly half of all 15-puzzle arrangements are. A poorly written app can generate one of these by accident.
This article is the practical check. The full mathematical justification lives in the parity theorem; this one keeps things plain.
The 30-second check
Look at the tiles in reading order — left to right across each row, top to bottom — ignoring the blank.
For every pair of tiles, count how many times a larger number appears before a smaller number. That count is the inversion number.
Then note which row the blank cell is in, counting from the bottom (the bottom row is 1, the row above it is 2, then 3, then 4 at the top).
Add the inversion number and the blank's row from the bottom. If the result is odd, the puzzle is solvable. If even, it is not.
That's it. That is the entire check.
A worked example
Suppose your board looks like this:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Reading order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
Count inversions. We need to find every pair where a larger number appears before a smaller number. Going through: 15 appears before 14, and that's the only inversion. So inversion count = 1.
The blank is in the bottom row → row 1 from the bottom.
Sum: 1 + 1 = 2. Even. This board is unsolvable.
This is, in fact, Sam Loyd's 1880 prize puzzle. The man offered $1000 to anyone who could solve it. The puzzle was unsolvable; he kept his money.
Another example
Suppose your board looks like this:
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Reading order: 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Count inversions:
- 5 before 1 → 1 inversion (5 > 1, and 5 comes first)
- 5 before 3 → 1 inversion
- 5 before 4 → 1 inversion
- 5 before 2 → 1 inversion
- 3 before 2 → 1 inversion
- 4 before 2 → 1 inversion
Total inversions: 6.
The blank is in the bottom row → row 1.
Sum: 6 + 1 = 7. Odd. This board is solvable.
Note that 6 + 1 = 7 is odd because 6 is even and we add an odd number — no, wait. 6 + 1 = 7, which is odd. Solvable.
Why this works (briefly)
A legal slide either moves a tile horizontally (no change in inversions, no change in blank's row) or vertically (changes inversions by an odd number, changes blank's row by 1).
In either case, the sum of inversions + blank's row stays even-or-odd in the same way it started. So this sum is an invariant — a property of the puzzle that legal moves cannot change.
The goal state (1‑2‑3‑...‑15 with the blank at bottom-right) has 0 inversions and the blank in row 1 from the bottom. Sum: 1, odd. So any solvable puzzle has odd sum. Any puzzle with even sum cannot reach the goal.
For the full proof with all the cases worked out, see the parity theorem page.
What about 8 puzzles (3×3)?
The check is simpler for the 3×3:
- Count inversions in reading order.
- If even, solvable.
- If odd, unsolvable.
You don't need to track the blank's row for the 3×3, because the puzzle's symmetry makes the row dependence redundant.
(For 5×5 — same rule as 3×3. For 6×6 — same rule as 4×4. The rule is "blank's row matters when N is even".)
What to do if your app generates unsolvable puzzles
This should never happen. A well-written app uses one of two methods to avoid it:
Generate by walking backwards from the goal. Start with the goal state, apply random valid moves, and use the resulting state as the starting position. Every position generated this way is solvable by construction.
Generate randomly, then test with parity. Shuffle the tiles uniformly at random; compute the parity check; if even, swap any two tiles to fix it. The resulting position is guaranteed solvable.
If you encounter an unsolvable puzzle in an app, that app is broken. Report the bug, switch apps. Slide Puzzle uses the walking-backwards-from-goal method and cannot produce unsolvable starting positions.
What to do if you suspect your own physical puzzle is unsolvable
Two things:
- Run the check. Inversions plus blank's row. If even, the physical pieces were assembled incorrectly. Pop one tile out, swap it with an adjacent tile, and the puzzle is solvable.
- If even after a swap the puzzle still resists you — the resistance is your strategy, not the puzzle.
The parity check takes about thirty seconds. Doing it before sinking another hour into a stuck board is a reasonable use of those seconds.