Why half of all 15 puzzles are impossible

If you take a 15 puzzle apart and put the tiles back in random order, there is a fifty per cent chance the puzzle you just built cannot be solved — not by you, not by a computer, not ever. This is the most useful fact in sliding puzzles, and almost nobody playing one knows it. It is also why our solver will sometimes tell you a board is impossible instead of searching.

What a single slide actually does

In a 15 puzzle you never move a tile past another tile; you swap a tile with the single blank. Every legal move is exactly one swap. That means the whole puzzle is a question about swaps, and swaps have a property mathematicians call parity: any arrangement needs either an even or an odd number of swaps to reach the solved state, and which of the two it needs can never change.

The count that cannot change

Take your board and read the tiles in order, left to right and top to bottom, ignoring the blank. Count the pairs that are out of order — every pair where a larger number appears before a smaller one. That total is called the inversion count.

Sliding a tile sideways swaps two neighbours in that reading order and changes the inversion count by exactly one. Sliding a tile vertically jumps it over three tiles, changing the count by an odd number too. But a vertical move also moves the blank one row. So the inversion count's odd-or-even status and the blank's row always change together, and one specific combination of the two stays fixed forever.

The rule, for a 4×4 board

For the standard 15 puzzle: the board is solvable when the inversion count plus the row number of the blank, counting rows from the top starting at one, is odd. Check the solved board and you will see it satisfies this. If your board does not, no sequence of slides will ever reach the solved state.

This is why the physical puzzle can be made to look unbeatable by prising out two tiles and swapping them — a single swap flips the parity, and the puzzle becomes mathematically impossible rather than merely hard.

What this means for a solver

A solver that ignores parity will burn through millions of positions on an impossible board and then say it found nothing, which is indistinguishable from the solver being bad. Checking parity first takes microseconds and turns that into a definite answer. Our 15 puzzle solver runs the check before searching, so it can honestly tell you a board cannot be solved.

Does Escape Grid have the same rule?

No, and the reason is worth understanding. In a 15 puzzle every move is a swap with a blank, which is what makes the parity argument work. In Escape Grid, pieces are longer than one cell, slide multiple cells at a time and can never rotate. There is no clean invariant, so solvability has to be determined by actually searching the board — which is exactly what happens before a level ships. The upside for you is that every Escape Grid level is guaranteed solvable, which no shuffled 15 puzzle can promise.