Can this sliding puzzle be solved? Count before you slide.
Diagnose a hand-arranged 4 × 4 puzzle with an inversion count, two contrasting boards, and a self-check.
You finish most of a sliding puzzle, but 14 and 15 are in each other’s places. Is there a clever loop that will fix them? If every other tile is correct and the gap is in the bottom-right corner, the answer is no. That arrangement cannot reach the usual goal through legal slides.
This lesson gives you a way to check a hand-arranged board before spending time on it. Tile Shift itself creates puzzles through legal slides from the goal, so its new boards already have a solution. The diagrams below are paper exercises; they are not extra boards you can load into the game.
Fix the goal and the rules first
Use a 4 × 4 grid with each number 1–15 appearing exactly once and one empty square, shown as a dot. A move slides one horizontally or vertically adjacent tile into that gap. The target is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ·
Check for a repeated or missing number before doing any arithmetic. The test below assumes this exact goal and ordinary adjacent slides. It does not apply unchanged to a different target order, a board with repeated values, or a game that lets tiles jump.
Count pairs that are out of order
Read the board across each row, starting at the top, and leave the gap out of your list. An inversion is a pair in which the earlier number is larger than the later number. For a short list such as 3, 1, 2, the inversions are 3 before 1 and 3 before 2: two pairs.
For a reliable count, take each number in turn and count the smaller numbers later in the list. Add those counts. Do not count only neighboring pairs: a larger number can form inversions with several distant numbers. Do not put a zero into the list for the gap.
Call the total I. Then find R, the gap’s row counted from the bottom: bottom row = 1, next row up = 2, then 3, then 4. For this 4 × 4 goal, the board is solvable exactly when I + R is odd. An even sum means no legal slide sequence can finish it. [1]
Board A: almost finished, but impossible
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 ·
The list is in increasing order except for 15 before 14. There is exactly one inversion, so I = 1. The gap is on the bottom row, so R = 1. Their sum is 2, which is even. Moving the gap around may change where the mistake appears, but it cannot make this board reach the goal.
If you built this physical puzzle by lifting pieces out, exchanging 14 and 15 again repairs the starting arrangement. Lifting and exchanging pieces is not a legal solving move. It is a correction to the setup. A digital game with ordinary slide controls cannot perform that exchange.
Board B: three inversions, but one move from finished
1 2 3 4 5 6 7 8 9 10 11 · 13 14 15 12
Removing the gap gives a list ending in 11, 13, 14, 15, 12. The inverted pairs are 13 before 12, 14 before 12, and 15 before 12. Thus I = 3. The gap is in the second row from the bottom, so R = 2. The sum is 5, which is odd.
You can verify the result without trusting the formula: slide tile 12 upward into the gap. The board is now the goal. This is why “an odd inversion count means impossible” is the wrong shortcut for a 4 × 4 board. You must include the gap’s row.
Why a legal move cannot change the verdict
Here, parity just means whether a number is odd or even. Consider the numbered list with the gap removed. A horizontal slide does not change the order of any numbered pair, and the gap stays in the same row. The parity of I + R stays the same.
A vertical slide moves a tile past three other numbered tiles in that list. Each crossed pair switches between being inverted and being ordered. Three such switches change the parity of I, even though the count need not increase by exactly three. The gap also moves one row, changing the parity of R. Both parts change parity together, so their sum keeps its parity.
The goal has I = 0 and R = 1, an odd sum. An even-sum board cannot reach it because no legal move changes that odd/even verdict. This explains the rejection test. The full solvability result also establishes that an odd-sum board can reach this goal; the invariant argument alone does not prove that second direction. [1]
Self-check: classify two boards
For each board, count every inverted pair, locate the gap’s row from the bottom, and decide whether the sum is odd or even. If a board is solvable, can you find a short route to the goal?
Board C
1 2 3 4 5 6 7 8 9 10 · 11 13 14 15 12
Board D
1 2 3 4 5 6 7 8 9 10 12 · 13 14 15 11
Show the counts and answers
C: the gap does not belong to the numbered list. The inverted pairs are 13–12, 14–12, and 15–12. I = 3, R = 2, and the sum is 5: solvable. Slide 11 left into the gap, then 12 upward. These two legal slides reach the goal.
D: the inverted pairs are 12–11, 13–11, 14–11, and 15–11. I = 4, R = 2, and the sum is 6: impossible under these rules. The same gap row as Board B does not give the same verdict; the numbered order matters too.
Use the answer for the right purpose
A solvability check tells you whether a route exists. It does not tell you the next slide, the shortest solution, or how difficult the board will feel. Boards B and C have short solutions that we can demonstrate directly; a different odd-sum board may need much more planning.
For a hand-arranged puzzle that fails, check the copied layout and your counts before restarting. For a Tile Shift board that feels stuck, you can keep working on a route: its generator preserves solvability. Retry this board restores the same start, while New puzzle gives you a different challenge.
Technical reference
[1] Princeton University, COS 226, “Slider Puzzle,” Fall 2018, section “Detecting unsolvable boards.” That explanation numbers the gap’s row from the top starting at zero. On a four-row board, its row index and our bottom-based R add to 4, so they have the same parity. The worked boards and counting exercises above were constructed and checked for this lesson.