数学建模：数字华容道¶
本页面把 1.2 的全部工具用到一个具体游戏上：数字华容道（八数码）中"只差一步"的局面为什么无解？ 这类问题的价值不在游戏本身，而在于它示范了一件事——如何把现实问题翻译成数学问题，也就是数学建模。
用到的核心工具只有一个：排列的奇偶性。
游戏规则与问题¶
九宫格中放着 \(1\) 到 \(8\) 八个数字，剩下一个格子是空的。每次操作只允许把空格相邻的某个数字滑进空格（等价于空格与这个数字互换位置）。
问题：从左边的目标状态出发，能否到达右边"只把 \(7\) 与 \(8\) 互换"的状态？
想一想
先不要算，只凭感觉判断：能不能做到？如果做不到，是什么阻止了我们？
第一步：把游戏翻译成排列¶
游戏里的元素是"方格"，数学里的元素是"数"。翻译的方法是按行读数：
建模的关键一步
把九个格子按行从上到下、每行从左到右读一遍，跳过空格，得到一串数字。因为空格被跳过，这串数字正好由 \(1\) 到 \(8\) 各出现一次组成，即 \(1, 2, \dots, 8\) 的一个 \(8\) 阶排列。
具体地，把状态写成 \(3 \times 3\) 的表格
（其中一格是空格），则对应的排列为按行依次读取非空格内容所得的 \(8\) 个数字。于是：
| 状态 | 按行读出的排列 | 逆序数 | 奇偶性 |
|---|---|---|---|
| 目标状态 | \(1\,2\,3\,4\,5\,6\,7\,8\) | \(0\) | 偶排列 |
| 只互换 \(7\) 与 \(8\) | \(1\,2\,3\,4\,5\,6\,8\,7\) | \(1\) | 奇排列 |
这一步把"版面状态"变成了"排列"，游戏操作就变成了对排列的操作。
第二步：找出不变量¶
现在看两种滑动分别对排列做了什么。
命题（两种滑动对排列的作用）
设某个状态对应的排列是 \(j_1 j_2 \cdots j_8\)。
- 横向滑动（空格与左右相邻的数字互换）：排列完全不变；
- 纵向滑动（空格与上下相邻的数字互换）：排列恰好改变两次对换，因此奇偶性不变。
证明
1. 横向滑动。 空格与左右相邻的数字交换，两种状态中非空格数字的读取顺序没有变化：被移动的数字原来在第几行的第几个非空位置，移动后仍在同一行的同一个非空位置（因为空格不出现在读取结果里，横向滑动相当于空格在"同一个读取序列的空档"里左右移动）。所以排列不变。
更具体地看一个例子。状态
按行读出的是 \(1\,2\,3\,4\,5\,7\,8\,6\)。把空格左边的 \(5\) 向右滑入空格：
读出的仍是 \(1\,2\,3\,4\,5\,7\,8\,6\)，确实没变。
2. 纵向滑动。 设某数字从第 \(r\) 行滑到第 \(r+1\) 行（或反过来），它在读取序列中的位置发生了变化。设它在原来那行是这一行的第 \(c\) 个非空位置（\(c = 1, 2, 3\)）。
- 这一行在它后面还有 \(3 - c\) 个非空位置，滑动后这些位置的数字被"读"在它前面了；
- 下一行在它前面有 \(c - 1\) 个非空位置，滑动后这些位置的数字被"读"在它后面了。
于是这个数字在读取序列中恰好跨过了
个数字。交换一个数字与它相邻位置上的数字就是一次相邻对换，故纵向滑动对排列的作用恰好是 \(2\) 次相邻对换（也可以说：跨越 \(2\) 个数字相当于 \(2\) 次对换）。
由对换改变奇偶性，偶数次对换使奇偶性不变。
为什么恰好是 \(2\) 次
答案藏在"每行有 \(3\) 个格子"里：一个数字跨行时，跨过的数字个数是"本行在它后面的个数"加"下一行在它前面的个数"，两者相加恰好是一行的格子数减一，即 \(3 - 1 = 2\)。这个结论只对 \(3\) 阶（每行 \(3\) 格）成立；换成 \(4 \times 4\) 就要改成 \(4 - 1 = 3\) 次，奇偶性会改变——所以 \(4 \times 4\) 的情形不能照搬这个论证，见下面的超纲说明。
综合两条：无论怎么滑，排列的奇偶性始终不变。它是这个游戏的一个不变量。
第三步：比较奇偶性¶
由第一步的表格：
- 目标状态 \(1\,2\,3\,4\,5\,6\,7\,8\) 的逆序数为 \(0\)，是偶排列；
- 只互换 \(7\) 与 \(8\) 的状态 \(1\,2\,3\,4\,5\,6\,8\,7\) 的逆序数为 \(1\)（只有 \(8, 7\) 这一对是逆序），是奇排列。
由第二步，从目标状态出发经过任意多次滑动，得到的永远是偶排列，而那个只差一步的状态是奇排列。因此
结论
数字华容道中，从目标状态出发，不可能到达"只把 \(7\) 与 \(8\) 互换"的状态。
理由是一句话：滑动不改变排列的奇偶性，而这两个状态的奇偶性不同。
顺带回答一个自然的问题：既然奇偶性是不变量，那从目标状态出发到底能到达哪些状态？\(3 \times 3\) 的答案很干净：恰好是所有对应偶排列的状态——空格停在哪一格并不影响这个判据。换成 \(4 \times 4\)（每行 \(4\) 格，宽为偶数）就不一样了，空格所在的行也要参与进来，见下面的超纲说明。就本题而言，已经足够判定无解。
推广与延伸¶
超纲（可跳过）
一般 \(m \times m\) 拼图与空格行的作用。 上面的论证只用了"\(8\) 个数字的排列"，它之所以够用，是因为 \(3 \times 3\) 时纵向滑动恰好是 \(2\) 次对换（不变）。
\(4 \times 4\)（十五数码）时纵向滑动是 \(3\) 次对换，会改变数字排列的奇偶性，上述论证失效。正确的判据要把空格所在的行也算进去：把数字排列的逆序数与空格所在行号（自下往上数）相加，这个和是奇数还是偶数在所有滑动下都不变。这说明"奇偶性"作为不变量依然可用，但必须换一个更细致的量。
这类"用不变量判定可达性"的思想在数学中很常见。更一般地，\(n\) 阶排列构成的集合对"复合"运算构成对称群 \(S_n\)，偶排列构成它的子群（交错群 \(A_n\)），而"可达性"问题变成了群作用下的轨道问题。这属于抽象代数的内容，本课程不展开。
数学建模的意义¶
回头看，这个例子做了三件事：
- 翻译：把"格子的滑动"翻译成"排列上的一次次对换"；
- 提炼不变量：发现"排列的奇偶性"在所有操作下不变；
- 用不变量下判断：两个状态的这个量不同，于是不可达。
课堂上老师的总结是：现实中的问题往往"看起来很乱、不好下手"，但转化成数学问题之后常常并不难。反过来，学过的理论（这里是排列的奇偶性）要主动去用——用不上，往往是因为没有先做"翻译"这一步。
课堂追问：为什么是"两次对换"而不是"一次"
有同学认为"把 \(8\) 往右滑、再把 \(5\) 往下滑"就是一次对换。老师纠正说：单独看某个数字的移动容易数错，正确做法是看读取序列的变化。
以图 1 的目标状态为例，把 \(6\) 向下滑入空格：
读取序列从 \(1\,2\,3\,4\,5\,6\,7\,8\) 变成 \(1\,2\,3\,4\,5\,7\,8\,6\)：\(6\) 在序列中从第 \(6\) 位跑到最后一位，跨过了 \(7, 8\) 两个数字，相当于 \(2\) 次对换。这正是命题中"跨过 \(2\) 个数字"的实际含义。
参见¶
- 对换与奇偶排列：本页用到的唯一工具
- 奇排列与偶排列的个数：上一页，奇偶性的计数结论
- 逆序与逆序数：计算小规模排列奇偶性的方法
- 1.3 \(n\) 阶行列式：奇偶性在行列式定义中的正式用途
- 首页：全站记号约定