Why some sliding puzzles are unsolvable: parity explained
Count inversions correctly, include the gap row on even-width boards, and understand why swapping just two tiles can make a sliding puzzle impossible.
Updated 2026-11-13
For the standard goal, an odd-width sliding puzzle is solvable exactly when its inversion count is even. For an even-width board, the inversion count plus the gap's row counted from the bottom must be odd.
Fix the goal before applying the test
These rules assume ascending row order and the gap at bottom right. A different target arrangement requires comparing against that target. They also assume a square board with one gap and moves that swap it with an orthogonally adjacent tile.
Parity means whether an integer is even or odd. The test does not estimate how hard a board is. It determines whether the starting arrangement and the target are in the same reachable class. A board may be solvable but difficult, or almost visually correct but impossible.
Count inversions without the gap
Read the board left to right, top to bottom, and leave out the gap. An inversion is a pair in which the earlier tile has a larger number than the later tile. Count every such pair, including pairs whose tiles were on different rows.
For the sequence one, three, two, four, the only inversion is three before two. For three, one, two, four, there are two: three before one and three before two. You count out-of-order pairs, not misplaced tiles and not just adjacent descents.
A reliable manual method is to take each tile in turn and count the smaller numbers to its right. Add those counts. Ignoring the blank is essential because the invariant below concerns the relative order of numbered tiles.
Why odd width preserves inversion parity
A horizontal move swaps the gap with a neighbour. Once the gap is omitted from the reading sequence, no numbered tiles change their relative order. The inversion count therefore stays unchanged.
For a vertical move on a board of width n, the moved tile crosses n minus one numbered tiles in reading order. Each crossed pair reverses its ordering, so inversion parity changes exactly when n minus one is odd. If n is odd, n minus one is even: vertical moves preserve inversion parity too.
The standard goal has no inversions, an even count. An odd-width board with odd inversion count therefore cannot reach it. Conversely, for the ordinary square sliding puzzle, the even-inversion class is reachable; parity gives a complete solvability criterion, not merely a necessary obstacle.
Why even width needs the gap row
When n is even, n minus one is odd, so a vertical move flips inversion parity. That same vertical move shifts the gap by one row and flips the parity of its row counted from the bottom. Both quantities flip together, so their sum keeps the same parity.
Horizontal moves change neither quantity. At the standard goal, the inversion count is zero and the gap is in bottom row one. Their sum is odd. Thus a starting even-width board must have an odd sum to be solvable.
| Width | Gap row from bottom | Required inversion parity |
|---|---|---|
| Odd | Any row | Even |
| Even | Odd row | Even |
| Even | Even row | Odd |
Work through an impossible near-goal
Take the solved eight-tile board and exchange seven and eight while leaving everything else untouched. The reading sequence now has exactly one inversion: eight before seven. The width is odd, so this board is unsolvable.
On the fifteen-tile board, exchange fourteen and fifteen in the solved layout. The inversion count is one and the gap is still in bottom row one. Their sum is even, so this board is also unsolvable. Looking close to the goal does not override the invariant.
What legal play can and cannot change
Legal moves never carry a board out of its solvability class. If you scramble the goal using only legal slides, the resulting board is solvable because reversing those moves returns to the goal. Poor planning can create a frustrating position, but it cannot turn that board mathematically impossible.
If your final local area looks wrong, first reconsider the constraints imposed by your solving method. A prematurely protected tile may need to move again. Do not confuse failure of one local plan with failure of the full board's parity test.
Where to play
YIGE / 一格华容道 provides solvable number sliding boards on HarmonyOS, from 3×3 through 6×6. Campaign hints can help with an unfamiliar route. Parity is especially useful when examining a manually arranged puzzle rather than a board reached by legal scrambling.