TECHNIQUE 4 OF 4
Reachability: test an arrangement before searching
Some four-by-four arrangements cannot be reached from the goal through legal slides. A counting invariant can identify them without trying every possible move sequence.
The rule and its limit
Read the numbered tiles left to right, top to bottom, ignoring the blank. An inversion is a pair in which the earlier tile has the larger number. Add the inversion count to the blank's row number counted from the bottom, where the bottom row is 1. For this four-by-four goal, a position is reachable exactly when that sum is odd.
A common mistake
Using inversion parity alone forgets the blank's row. Also, failing this test says the supplied arrangement is unreachable; it does not say that an actual legal scramble generated by the game became unsolvable through legal play.
PLAYABLE EXAMPLE 1
Check the odd invariant
Calculate inversions while ignoring the blank. Add the blank’s row counted from the bottom. Is this position reachable from the target? Then solve it.
Loading playable study…
Select a tile beside the blank. Coordinates label every square; rows start at the top.
Keyboard: Tab to an enabled control, then press Enter or Space. The study starts from the diagram shown; reload can restore your own saved moves.
Try the task before inspecting the answer.
Compare the starting moves
The shortest finish takes 6 moves. There are 9 inversions and the blank is in row 4 from the bottom. Their sum 13 is odd, matching the target’s parity. Swapping two numbered tiles while keeping the blank fixed would make this sum even and that altered board impossible. The distance comes from a complete breadth-first search outward from the target through 12 moves; it is not a general shortest-solution claim for arbitrary arcade shuffles.
| First move | Immediate effect | Checked consequence |
|---|---|---|
| Tile 1 (R2C1) | Blank moves to R2C1; Manhattan total becomes 5. | Exact remaining distance: 5 moves. Starts a shortest finish. |
| Tile 2 (R1C2) | Blank moves to R1C2; Manhattan total becomes 7. | Exact remaining distance: 7 moves. Adds work compared with a shortest finish. |
PLAYABLE EXAMPLE 2
Parity survives a longer route
Calculate inversions while ignoring the blank. Add the blank’s row counted from the bottom. Is this position reachable from the target? Then solve it.
Loading playable study…
Select a tile beside the blank. Coordinates label every square; rows start at the top.
Keyboard: Tab to an enabled control, then press Enter or Space. The study starts from the diagram shown; reload can restore your own saved moves.
Try the task before inspecting the answer.
Compare the starting moves
The shortest finish takes 10 moves. There are 14 inversions and the blank is in row 1 from the bottom. Their sum 15 is odd, matching the target’s parity. Swapping two numbered tiles while keeping the blank fixed would make this sum even and that altered board impossible. The distance comes from a complete breadth-first search outward from the target through 12 moves; it is not a general shortest-solution claim for arbitrary arcade shuffles.
| First move | Immediate effect | Checked consequence |
|---|---|---|
| Tile 14 (R3C2) | Blank moves to R3C2; Manhattan total becomes 7. | Exact remaining distance: 9 moves. Starts a shortest finish. |
| Tile 13 (R4C1) | Blank moves to R4C1; Manhattan total becomes 9. | Exact remaining distance: 11 moves. Adds work compared with a shortest finish. |
| Tile 11 (R4C3) | Blank moves to R4C3; Manhattan total becomes 9. | Exact remaining distance: 11 moves. Adds work compared with a shortest finish. |
An odd inversion count is not automatically impossible
The rows are 1,2,3,4 / 5,6,7,8 / 9,10,11,blank / 13,14,15,12. The blank is R3C4.
The tempting move
Declare the board impossible because there are three inversions: 13, 14 and 15 each appear before 12.
Why it fails
The blank is on row 2 from the bottom. Three inversions plus that row number gives 5, an odd sum. In fact, selecting tile 12 at R4C4 solves the board immediately.
What you can conclude
Include both parts of the even-width parity test. Odd inversions alone do not establish impossibility.
Try the idea in another position
All rows match the goal except the bottom row, which reads 13, 15, 14, blank. Can legal slides solve it?
Check your reasoning
No. Ignoring the blank, the only inversion is 15 before 14. The blank is on row 1 from the bottom, so the sum is 1 + 1 = 2, which is even. Swapping those two tiles by hand created an unreachable arrangement.