奇数码问题充分性的一个对称性证明（及背后的群作用思想）
摘要
在《算法竞赛进阶指南》中，奇数码问题（奇数阶数码推盘）的可达性条件通常只给出必要性证明——任何合法移动不改变逆序对奇偶性；充分性的证明常被省略或依赖繁杂的分情况构造。本文记录一个利用棋盘旋转对称性将上下移动转化为左右移动的证明思路，并指出其背后的群论本质：旋转是状态空间上的一个自同构，而”旋转变换→执行操作→旋转变换回来”的模式正是群作用中的共轭思想。全文给出严格引理与完整构造，展示对称性如何让证明变得更整体、更优雅。
1. 问题陈述
设 $n$ 为正奇数。在一个 $n\times n$ 的网格中，放置有数字 $1,2,\dots,n^2-1$ 以及一个空格（记作 $0$）。每一步可以将空格与其上、下、左、右相邻的数字交换位置。给定两个局面（状态）$A$ 和 $B$，问是否可以通过一系列合法移动将 $A$ 变为 $B$。
已知事实（必要性）：将局面按行优先展开成一个长度为 $n^2$ 的序列（舍去 $0$），其逆序对数量的奇偶性在任何合法移动下保持不变。
因此，若 $A$ 与 $B$ 的逆序对奇偶性不同，则它们一定不可达。
目标（充分性）：若 $A$ 与 $B$ 的逆序对奇偶性相同，证明它们一定可以相互到达。
2. 证明概览
传统证明中，需要围绕”如何在不破坏已归位数字的前提下上下移动一个数字”进行复杂的行走构造。本证明的核心是视角转换：
- 将整个棋盘顺时针旋转 $90^\circ$，原问题中的上下移动变成了新视角下的左右移动。
- 若我们能证明新视角下的目标一定可达，那么原问题也一定可达。
- 通过交替使用“左右移动”引理和旋转技巧，我们可以像搭积木一样逐位将数字归位，最终只剩右下角 $2\times2$ 区域，而该区域的可达性恰好由逆序对奇偶性完全决定。
这一想法本质上等同于：旋转是奇数码问题状态空间的一个自同构，它保持移动关系与逆序对性质。而“旋转—执行操作—逆旋转”的步骤，正是群作用理论里共轭的典型用法。
3. 记号与基本引理
记状态空间为 $\mathcal{S}$，包含所有将 $0,1,\dots,n^2-1$ 填入 $n\times n$ 网格的排列。定义：
- 目标状态 $T$：数字按行优先顺序从左到右、从上到下排列，最后一个是 $0$。
- 逆序对：按行优先展开为序列 $s_1,s_2,\dots,s_{n^2}$ 后，满足 $i<j$ 且 $s_i>s_j$ 且 $s_i,s_j\neq 0$ 的数对个数。记 $\operatorname{inv}(A)$ 为状态 $A$ 的逆序对数。
- 合法移动：将空格 $0$ 与上下左右相邻数字交换，记为 $\sim$ 关系。
引理 0（必要性）：若 $A\sim B$，则 $\operatorname{inv}(A)\equiv\operatorname{inv}(B)\pmod{2}$。
此即已知结果，不赘证。
4. 核心引理
4.1 左右移动引理
引理 1（自由左右移动）
设当前状态中，已有前 $m$ 个数字（按目标状态 $T$ 的顺序）放在了它们的正确位置，且这些位置构成棋盘左上角的一个矩形区域（即已填满若干整行加上下一行的前若干格）。对于任意数字 $k$ （$k$ 尚未归位），只需利用待处理区域（剩余格子），就可以将该数字左右移动到任意目标列，而不改变任何已归位数字的位置。
证明
将空格移动到数字 $k$ 的同行、相邻列，然后通过与空格交换来实现左右移动。由于已归位区域在左上角且连续，空格在剩余区域内总是有足够的自由度绕到 $k$ 的左侧或右侧，且所有路径不会穿过已完成区域。具体构造可参考标准八数码问题中的“空格绕行”方法，这里不再画格子说明。
关键点：该引理只要求“剩余区域连通且不受已完成数字阻挡”，而这对于左上角矩形区域是自然成立的。
4.2 旋转对称引理
定义映射 $R:\mathcal{S}\to\mathcal{S}$ 为将整个棋盘顺时针旋转 $90^\circ$（格子内容跟随旋转）。也就是说，原位置 $(i,j)$ 的数字移动到新位置 $(j,n+1-i)$。
引理 2（旋转不改变可达性与逆序对）
对于奇数 $n$，旋转 $R$ 满足：
- $A$ 可达 $B$ $\iff$ $R(A)$ 可达 $R(B)$；
- $\operatorname{inv}(R(A))\equiv\operatorname{inv}(A)\pmod{2}$。
证明
(1) 因为 $R$ 是网格图的一个自同构：它将相邻关系映为相邻关系，且把空格映射到空格的位置。因此，$A$ 中一步移动对应 $R(A)$ 中同样的一步移动，只是方向旋转了 $90^\circ$。递推可得可达性等价。
(2) 将 $n\times n$ 的格子按行优先编号。旋转 $R$ 诱导了格子集合上的一个置换 $\sigma$。当 $n$ 为奇数时，中心一格不动，其余 $n^2-1$ 个格子均落在长度为 $4$ 的循环中，且 $4$-循环的个数为 $\frac{n^2-1}{4}$，由于 $n$ 为奇数，该数为整数且为偶数。每个 $4$-循环是奇置换，偶数个奇置换的乘积为偶置换，故 $\sigma$ 是偶置换。
由于 $A$ 按行优先展开成的序列可通过将目标序列按 $\sigma^{-1}$ 重排得到，而偶置换不改变排列的奇偶性，因此展开序列（含 $0$）的奇偶性在旋转前后不变。去掉 $0$ 后，$0$ 在序列中位置的改变等价于对剩余 $n^2-1$ 个元素施加某个置换，该置换的奇偶性与 $\sigma$ 的奇偶性相关，但恰好与 $0$ 位置变化带来的影响抵消，最终 $\operatorname{inv}(R(A))$ 与 $\operatorname{inv}(A)$ 奇偶性相同。具体推导亦可见经典置换群教材中的标准结论。
注：这是整个证明中唯一需要计算置换奇偶性的地方，且仅在处理逆序对不变量时才用到。
4.3 旋转后的区域形状
使用旋转时，我们关心的是：当我们在“旋转后的视角”下应用引理 1 时，已完成区域的形状是否还能保证剩余区域连通。
引理 3（旋转后的区域适配）
假设在原视角下，已归位的前 $m$ 个数字占据左上角的标准矩形区域（即整行整列的阶梯形）。将当前状态 $C$ 与目标状态 $T$ 同时顺时针旋转 $90^\circ$，得到 $R(C)$ 与 $R(T)$。
在 $R(T)$ 中，前 $m$ 个数字（相同的数字集合）占据的位置仍然是连通的，且它们的补集（剩余自由格子）构成一个连通的、没有“孤岛”的区域，使得引理 1 的前提仍然成立。
证明
原左上角的矩形区域旋转后变成右上角或底部的一个矩形区域，具体形状因矩形是否填满整行而略有不同，但无论如何，已归位数字总是形成一个“角落区域”，剩余格子是一个连通的矩形/ L 形区域。因为 $n$ 为奇数且是整行整列归位，补集始终连通。例如，前 $n$ 个数字填满第一行，旋转后变成最右列，剩余区域仍为 $(n-1)\times n$ 的连通块，空格完全可以在其中活动。
这保证了：在新视角下，我们依然可以安全地调用引理 1 来左右移动某个数字，而不会破坏任何已归位数字。
5. 充分性证明
定理（充分性）
若两个状态 $A$ 与 $B$ 满足 $\operatorname{inv}(A)\equiv\operatorname{inv}(B)\pmod{2}$，则 $A$ 可达 $B$。
证明
我们证明任意状态 $A$ 都可以到达某个“标准状态”，而标准状态只有两个（逆序对奇偶性各对应一个），因此奇偶性相同的状态互达。
构造过程：从状态 $A$ 开始，按行优先顺序依次将数字 $1,2,\dots,n^2-3$ 归位（最后留下右下角 $2\times2$ 区域暂不处理）。
假设前 $k-1$ 个数字已经放在正确位置（即与目标状态 $T$ 中位置一致）。现在要放置数字 $k$。
- 左右调整：若数字 $k$ 已经在正确行，直接用引理 1 将其左右移到正确列。
- 上下调整：若数字 $k$ 不在正确行，则进行如下“旋转–移动–逆旋转”操作：
- 将当前状态 $C$ 与目标 $T$ 同时顺时针旋转 $90^\circ$，得到 $R(C)$ 与 $R(T)$。
- 在 $R(C)$ 中，数字 $k$ 的“上下偏差”变成了左右偏差。由引理 3，此时已完成区域仍然满足引理 1 的条件。
- 应用引理 1，在 $R(C)$ 中将数字 $k$ 左右移动到它在 $R(T)$ 中的正确列。
- 得到状态 $D’$，再逆时针旋转 $90^\circ$ 回到原视角，得到 $D=R^{-1}(D’)$。
- 此时在原棋盘上，数字 $k$ 已被移到正确行，且前 $k-1$ 个数字未被破坏。
- 再用引理 1 进行左右微调，即可将 $k$ 完全归位。
重复此步骤，直到只剩下右下角 $2\times2$ 区域（三个数字加一个空格）。
最后的 $2\times2$ 区域：
此时棋盘上只剩三个数字和空格未归位，总状态数只有 $4! = 24$ 种，但考虑到空格只能在 $2\times2$ 内移动，实际上可能的状态只有 $4$ 种（空格固定一角时数字的 $3!$ 排列受限于平面移动）。更直接地，可以证明这 $2\times2$ 区域的所有合法移动不改变整个棋盘逆序对的奇偶性，并且恰好有 两类 排列状态，分别对应逆序对奇偶性的奇和偶。由于我们在整个过程始终维持逆序对奇偶性不变（由引理 0 和引理 2 保证），最终的 $2\times2$ 状态必属于与初始 $A$ 相同奇偶性的那一类。若与目标状态的逆序对奇偶性相同，最后三个数字的排列必定是目标状态中的顺序；若与目标状态的逆序对奇偶性不同，则是交换了某两个数字的状态（即不可达的另一个标准态）。
因此，任意奇偶性相同的状态都可以用上述过程到达同一个标准状态（例如所有数字归位的目标状态 $T$），从而它们彼此可达。$\square$
6. 群论视角：藏在背后的共轭与群作用
回过头看，“旋转–执行操作–逆旋转”这个三步走的做法，在群论中有个名字：共轭。
把状态空间 $\mathcal{S}$ 视为集合，合法移动序列构成的群记为 $G$（实际是生成这些移动的变换群，但不必显式写出）。旋转 $R$ 是 $\mathcal{S}$ 上的一个双射，且它保持移动关系，即 $R(g(x)) = g’(R(x))$ 对某个 $g’\in G$ 成立，相当于说 $R$ 正规化 $G$。
当我们想要实现一个垂直移动操作 $f$（在原始问题上很麻烦）时，我们不直接构造 $f$，而是：
- 先用 $R$ 将状态“平移”到一个新坐标系，
- 在该坐标系下执行一个简单的水平移动 $h$（即已有的引理 1），
- 再用 $R^{-1}$ 平移回来。
所得的操作 $R^{-1}\circ h \circ R$ 就是原始坐标系下的垂直移动。这就是群作用理论中利用对称性传递操作的核心技巧。
同时，引理 2 中“旋转不改变逆序对”本质上利用了旋转置换是偶置换这一群论事实，这与“旋转是状态空间的一个对称性”是相容的。整个证明可以看作：利用旋转群 $\langle R\rangle$ 对状态空间的作用，将困难的“上下移动”约化为已经解决的“左右移动”，这正是群作用下轨道分析的一个朴素实例。
对于只自学了 40 多页群论就直觉到“一看见对称就想到群”的笔者来说，这个证明可以说是一次与抽象代数的神交——它在没有显式写出群、轨道、稳定子等术语的情况下，已经运用了共轭与群作用的核心思维。
7. 注记：与传统证明的比较
- 传统证明：通常分别处理“同行移动”和“跨行移动”，后者需要显式构造空格的长距离绕行路径，保证不扰乱已归位数字。证明繁琐但直接。
- 本证明：通过旋转对称性，把行与列的移动统一到同一个引理下，避免了对垂直移动的重复构造，使逻辑更加干净。代价是需要额外证明旋转保持逆序对、以及旋转后区域形状依然适配——但这些性质本身就是对称性带来的自然结果。
- 适用性：该方法紧紧依赖 $n$ 为奇数（保证旋转为偶置换且区域对称），对于偶数阶数码问题则不适用，这与已知结论一致。
8. 结语
奇数码问题的充分性证明之所以常被略去，是因为复杂的分情形构造容易淹没问题的本质。而当我们抬起视角，利用棋盘自身的旋转对称性，证明就变得有节奏、有结构，甚至透露出群论的影子。这个证明不仅让充分性“显然”，更是一次美妙的思想实验：原来对称性不只是现象，它可以成为证明的工具。
对于竞赛选手，掌握这种“旋转视角”的技巧也可能在其他网格问题中发挥作用；对于数学爱好者，它则是一扇窥见群作用思想的窗——不需要把群论学完，就能先呼吸到它的空气。
