Loyd–Johnson 15-puzzle parity invariant

Step 1 (horizontal slides). When the blank slides left or right within the same row, no numbered tile changes its position in the row-major listing of the $15$ tiles, and the blank stays in row $r(s)$. Thus $\Delta N = 0$ and $\Delta r = 0$, so $N(s) + r(s)$ is unchanged.

Step 2 (vertical slides). When the blank slides up or down, the tile $t$ moving into the blank's old square shifts by $3$ positions in the row-major sequence of the $15$ numbered tiles. Crossing each of those $3$ tiles flips whether $(t, u)$ is an inversion, changing $N(s)$ by $+1$ or $-1$ per tile. The total change is $\Delta N \in \{-3, -1, +1, +3\}$, which is always odd. At the same time $\Delta r \in \{-1, +1\}$ is also odd, so $\Delta(N + r)$ is even.

Step 3 (swapping 14 and 15). Swapping tiles $14$ and $15$ with the blank fixed at row $r = 4$ changes $N(s)$ by $+1$ (from $0$ to $1$) while $\Delta r = 0$. Hence $(N + r) \bmod 2$ differs between the start state ($1 + 4 \equiv 1 \pmod 2$) and the solved state ($0 + 4 \equiv 0 \pmod 2$), proving no sequence of legal slides can reach the solved state.