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

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

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

---

1. 棋盘状态可视化

我们将空格表示为 ⬛。

初始状态

a	b	c
d	e	f
g	h	⬛

目标状态

a	b	c
d	e	f
h	g	⬛

---

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

2.1 逆序对定义

对于一个排列，如果一对元素 满足 在 之前且 ，则称之为一个逆序对。

• 状态 A 的序列：
  • 逆序对数：（偶排列）
• 状态 B 的序列： * 逆序对：仅有 一对，因为字母序 。
  • 逆序对数：（奇排列）

2.2 移动规则的奇偶变换

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

proof: Obvious

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

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

从而逆序对是不变量

2.3 完成证明

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

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