15数码谜题的洛伊德—约翰逊奇偶不变量

第一步(水平滑动)。 当空格在同一行内左右滑动时,$15$ 个数字块按行优先顺序排列的次序完全不变,且空格仍处于第 $r(s)$ 行。因此 $\Delta N = 0$ 且 $\Delta r = 0$,$N(s) + r(s)$ 保持不变。

第二步(垂直滑动)。 当空格上下滑动时,移入空格原位置的数字块 $t$ 在 $15$ 个数字块的行优先序列中恰好移动 $3$ 个位置。跨过这 $3$ 个数字块中的每一个都会翻转数对 $(t, u)$ 的逆序关系,使 $N(s)$ 每次改变 $+1$ 或 $-1$。总变化量 $\Delta N \in \{-3, -1, +1, +3\}$ 必为奇数。与此同时 $\Delta r \in \{-1, +1\}$ 也是奇数,故 $\Delta(N + r)$ 为偶数。

第三步(交换14与15)。 在空格固定于第 $r = 4$ 行时仅交换数字块 $14$ 与 $15$,会使 $N(s)$ 增加 $+1$(从 $0$ 变为 $1$)而 $\Delta r = 0$。于是初始状态($1 + 4 \equiv 1 \pmod 2$)与复原状态($0 + 4 \equiv 0 \pmod 2$)的 $(N + r) \bmod 2$ 不同,证明任何合法滑动序列都无法到达复原状态。