The maths of sliding puzzles: why some boards cannot be solved
The sliding puzzle is one of the most classic toys in the world. It became famous in the late 19th century as the “15 Puzzle”: fifteen numbered tiles in a 4×4 frame with one gap. A challenge circulated offering a prize to anyone who could put it in order when tiles 14 and 15 started swapped. Countless people tried and nobody succeeded, because it is mathematically impossible.
The secret: inversions
Write the numbers on the tiles in reading order, left to right and top to bottom (ignoring the gap), and count the pairs where a bigger number comes before a smaller one. Each such pair is an inversion.
- A solved board has 0 inversions.
- Swapping only 14 and 15 creates exactly 1.
What a move changes
- A horizontal move does not change the reading order at all, so the inversion count stays the same.
- A vertical move makes one tile jump over several others, which changes the count.
On boards of odd width (such as 3×3) a vertical move always jumps over two tiles, so the count changes by an even number. The parity of the inversion count never changes: a 3×3 board with an odd count can never get back to 0.
On boards of even width (such as 4×4) the row of the gap must be counted too, but the principle is the same: some quantity keeps its parity whatever you do. That is why the legendary 14-15 puzzle can never be solved.
Half of all arrangements are impossible
A striking consequence: if you pop the tiles out and put them back at random, there is a fifty-fifty chance the board cannot be solved at all.
How Vdopa guarantees a solution
Vdopa’s sliding puzzles are never placed at random. Each one starts from the finished picture and is shuffled by real, legal moves, as if someone slid the pieces by hand, so every board can always return to the picture. Our solver also re-checks the parity and computes the minimum number of moves, so each board’s difficulty fits its floor of the mansion.
Using this in the game
You never need to count inversions while playing, but knowing that every board is definitely solvable gives you the confidence to use a systematic strategy: top row first, then the left column, until the board shrinks. The step-by-step method is in the sliding tiles guide.