How to Solve a Sliding Puzzle (and Why Half of Them Can’t Be Solved)
The surprising mathematics behind sliding tile puzzles: permutation parity, the 1880s 15-puzzle craze, and how to tell whether a position is solvable.
Take a 4 × 4 sliding puzzle, pop out two neighbouring tiles, say 14 and 15, and swap them. Now try to solve it. You can slide tiles for the rest of your life and you'll never get them back in order. It's not hard; it's impossible. And exactly half of all the ways you could put the tiles back in the frame have the same problem.
This guide explains why, using one simple idea from mathematics called parity, and tells the story of how this puzzle drove people a little crazy in the 1880s.
The 15 puzzle craze
The 4 × 4 sliding puzzle, with fifteen numbered tiles and one gap, appeared in the United States in the 1870s and became a sensation around 1880. It's usually credited to a New York postmaster named Noyes Chapman. Newspapers of the time described people playing it obsessively, and there were stories of employers banning it from offices.
Part of the excitement came from challenges like the one above: start with the tiles in order except for 14 and 15, which are swapped, and restore the correct order. Rewards were offered for a solution. Nobody could claim them, because, as two mathematicians published in 1879, that position can't be solved.
Parity: odd and even swaps
Imagine any arrangement of the numbers 1 to 15 in a row. You could sort it into order by repeatedly swapping two numbers at a time. There are many different ways to do the sorting, but here's a remarkable fact: for any given arrangement, the number of swaps you need is always odd or always even, no matter which method you use. Mathematicians call an arrangement even or odd accordingly.
The famous "14-15 swapped" position is just one swap away from being solved, so it's an odd arrangement. And as we'll see, a sliding puzzle with the gap in the corner can only ever reach even arrangements.
What one slide does
Think of the gap as a sixteenth tile, the "blank." Every time you slide a tile into the gap, you're really swapping that tile with the blank. So each move is exactly one swap, and each move flips the parity of the arrangement from even to odd or back again.
Now watch the blank itself. Colour the board like a chessboard. Every move shifts the blank to a neighbouring square, so it always changes colour. If the blank starts in the bottom-right corner and finishes there too, it must have made an even number of moves, because it needs to come back to the same colour.
Put the two facts together:
- Any sequence of moves that returns the blank to its corner contains an even number of moves.
- An even number of swaps always produces an even arrangement.
So starting from the solved puzzle, you can only ever reach even arrangements with the blank in the corner. The 14-15 position is odd, so it's unreachable. Since half of all arrangements are odd, half of all positions are impossible.
The reverse is also true, though the proof is longer: every even arrangement can be solved. So parity is the whole story.
How to check any position
You can test whether a 4 × 4 position is solvable by hand:
- Write the tile numbers in reading order (left to right, top to bottom), skipping the gap.
- Count the inversions: the number of pairs where a bigger number comes before a smaller one. For example, in 2, 1, 3 there's one inversion (2 before 1).
- Note which row the gap is in, counting from the bottom (bottom row = 1).
- For a 4-wide board, the position is solvable if the inversions are even and the gap's row is odd, or the inversions are odd and the gap's row is even.
For boards with an odd width, like 3 × 3 or 5 × 5, the rule is simpler: the position is solvable exactly when the number of inversions is even, wherever the gap is.
Why our puzzle is always solvable
When you press Shuffle in our Sliding Puzzle, the game doesn't place tiles at random. It starts from the solved position and makes hundreds of random legal slides, exactly as if someone were scrambling a real puzzle in their hands. Because every scramble move can be reversed, every shuffled board is guaranteed to have a solution.
How hard can it get?
Computers have since examined every reachable position. For the 3 × 3 puzzle, no position needs more than 31 moves to solve. For the 4 × 4, the hardest positions need 80 single-tile moves. Finding the shortest solution for a given position is a genuinely hard problem for computers, and it's been used for decades as a test case for search algorithms in artificial intelligence.
For humans, though, the goal is simpler: solve it at all, then solve it faster. If you'd like a step-by-step method, the game page explains the row-by-row approach that works on any size.