如果合法操作不会改变系统的某个变量，那么如果初始状态和末状态的不变量不同，就可以断言末状态无法到达。

3×3 华容道不可达性证明

[!ABSTRACT] 命题
在 $3 \times 3$ 的方格中，初始排列为 abcdefgh（空格在末尾），不可能通过合法的华容道/滑动拼图规则变成 abcdefhg（空格在末尾）。

1. 棋盘状态可视化

我们将空格表示为 ⬛。

初始状态 $S_{start}$

目标状态 $S_{target}$

2. 数学证明：逆序对与奇偶性

2.1 逆序对定义

对于一个排列，如果一对元素 $(x, y)$满足$x$在$y$之前且$x > y$，则称之为一个逆序对。

• 状态 A 的序列： $(a, b, c, d, e, f, g, h)$
  • 逆序对数：$N(A) = 0$（偶排列）
• 状态 B 的序列： $(a, b, c, d, e, f, h, g)$* 逆序对：仅有$(h, g)$一对，因为字母序$h > g$。
  • 逆序对数：$N(B) = 1$（奇排列）

2.2 移动规则的奇偶变换

进行行移动时，不会改变排列的逆序对

proof: Obvious

进行列移动时，逆序对奇偶性不变

proof：按从左到右从上到下编号可知，列移动将编号改变3，恰好越过两个字母，枚举可知这会把逆序对+2或-2或不变，故其奇偶性不变

从而逆序对是不变量

2.3 完成证明

两个状态逆序对分别为0和1，奇偶性不同，故不可互相到达。

严谨地，可以使用数学归纳法。假设进行了 $n$步操作，做一步操作已经证明了奇偶性不变。下面设进行$n=k-1$步后奇偶性不变。再走一步，同理可知奇偶性不变，从而$n=k$ 时奇偶性也与初始状态相同。故由归纳公理得知奇偶性为不变量。