奇数码问题初探

最近在算法竞赛进阶指南上看到了奇数码问题，但是没讲证明。恰好最近刻上老师讲了证明，简单记录一下证明过程。证明过程需要用到映射和基本的群论知识，如果你不了解，建议先学习一下这些前置知识。本文中的复合运算符 \(\circ\) 有时会省略。

题目简介

奇数码问题是一个经典的群论问题。也许你听说过数字华容道或 \(15\) 拼图问题，那就是它最常见的变体， \(4\times4\) 的奇数码问题。将这个问题扩展到 \(n\times n\) 的情况就是我们要研究的奇数码问题。在这篇文章，我们主要研究它的可解性问题。

可解性

赏金

1896 年，美国著名棋手SamLoyd 曾经悬赏1000 美金，来看看有没有人可以解出这个问题：\[ \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&11&12\\ \hline 13&15&14&\\ \hline \end{array} \]其中只有 \(14\) 和 \(15\) 是进行交换的。我们将稍后来解决这个问题。你可以自己玩玩看，看看你能不你拿到这1000美元

对换，置换与轮换

在解决这个问题前，我们先引入几个概念。

• 置换，又叫排列，指的是在集合 \(S\) 中的双射 \(f:S \mapsto S\)。例如，对于 \(S=\{1,2,3\}\)，定义 \(f(1)=3,f(2)=2,f(3)=1\)，\(f\) 就是一个置换。实际上，如果用 \(f(x)\) 替换 \(x\)，会发现其实集合里面每个数都出现了，只是顺序可能不同。就像这样\[\displaylines{1&2&3\\ \downarrow&\downarrow&\downarrow\\3&2&1}\]刚刚这种表示也可以用来记录一个置换。即\[f=\begin{pmatrix}1&2&3\\ \downarrow&\downarrow&\downarrow\\3&2&1\end{pmatrix}\]特别的，对于 \(f(x)=x\) 这种映射也是置换，成为恒同变换或者叫恒同置换，记作 \(\rm{id}\)。
  
• 对换，顾名思义，就是只有两个元素进行了交换，其他元素不变。形式化的，\(f:S\mapsto S\) 是对换是指存在 \(x,y\in S,f(x)=y,f(y)=x\)，并且对于其他元素 \(z\in S,f(z)=z\)，我们可以用 \(f=(x,y)\) 来表示这是一个交换 \(x,y\) 的对换。假设 \(S=\{1,2,3,4\}\)，我们可以用 \(f=(2,3)\) 来表示一个对换，它的涵义就等于\[f=\begin{pmatrix}1&2&3&4\\ \downarrow&\downarrow&\downarrow&\downarrow\\1&3&2&4\end{pmatrix}\]
• 轮换，就是指几个元素轮流交换。形式化的，就是对于若干的元素\(x_1,x_2,\cdots,x_n\)，\[f(x)=\begin{cases}x_{i+1}&{\rm if} \space x=x_i,i\in[1,n-1]\\x_1 &{\rm if}\space x=x_n \\x&{\rm if}\space x\not=x_i,u\in[1,n]\end{cases}\]我们用 \(f=(x_1,x_2,\cdots,x_n)\) 来表示这个轮换。举个例子，假设 \(S=\{1,2,3,4\}\)，\(f(1,3,4)\) 就是指这个置换 \[f=\begin{pmatrix}1&2&3&4\\ \downarrow&\downarrow&\downarrow&\downarrow\\4&2&1&3\end{pmatrix}\] 其中有一些结论并不是本文的重点，在下文会直接使用，建议先了解一下相关知识。

可解性判定

我们先来讨论 \(4\times4\) 的情况。方便起见，我们将所有的空格都移动到右下角。我们将这十五的格子首尾相连，形成一排。将 \(1\sim 15\) 计入集合 \(S\) 中。 我们定义 \(f(x,y)\) 是将第 \(x\) 个和第 \(y\) 个进行交换，轮换也类似的定义。

奇变换与偶变换

我们建立一个初始状态（\(1\sim 15\) 排列好的情况）到现在状态的映射（空格也算进去，记作 \(0\)）。我们发现这恰好是一个置换，我们求解这个问题其实就是就这个置换的逆。 首先，恒同变换 \(\rm id\) 是偶变换。
考虑我们有什么操作可以进行，由于最终空格一定要回到原处，因此一来一回有两次路径，共有偶数次上下或左右对换，因此这个置换是偶置换就是可解的必要条件。但是开头的谜题指交换了 \(14\) 和 \(15\)，是奇变换，因此不可解。但是偶置换是充分条件吗？

轮换

不同与前一章的建模方法，这次的映射不算空格，只有 \(15\) 个元素。我们来证明凡是偶置换都可以解。将这个置换记作 \(g\)。由于空格始终都没有动，因此将空格去掉也是偶变换。

考虑在这个问题之中到底有什么操作可以进行。首先，对于这样的四个格子，可以让空格转一圈来使三个元素进行轮换。\[\begin{array}{|c|c|} \hline 11&12\\ \hline 14&\\ \hline \end{array}\rightarrow \begin{array}{|c|c|} \hline 11&\\ \hline 14&12\\ \hline \end{array}\rightarrow \begin{array}{|c|c|} \hline &11\\ \hline 14&12\\ \hline \end{array}\rightarrow \begin{array}{|c|c|} \hline 14&11\\ \hline &12\\ \hline \end{array}\rightarrow \begin{array}{|c|c|} \hline 14&11\\ \hline 12&\\ \hline \end{array}\]可以进行任意次轮换。

然后，我们可以通过将空格移到任意一个位置，在像上面一样进行轮换，接着原路返回，就可以在任意位置实现像这样的三轮换了。\[\begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&11&12\\ \hline 13&15&14&\\ \hline \end{array} \rightarrow \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&&7\\ \hline 9&10&11&8\\ \hline 13&15&14&12\\ \hline \end{array} \rightarrow \begin{array}{|c|c|c|c|} \hline 1&6&2&4\\ \hline 5&3&&7\\ \hline 9&10&11&8\\ \hline 13&15&14&12\\ \hline \end{array} \rightarrow \begin{array}{|c|c|c|c|} \hline 1&6&2&4\\ \hline 5&3&7&8\\ \hline 9&10&11&12\\ \hline 13&15&14&\\ \hline \end{array} \]因此所有像这样的轮换都可以进行。

那么，我们只要使用轮换来实现对换的效果就可以了。实现的方法如下：

• 对于四个不同的元素 \(a,b,c,d\)，\((a,b)(c,d)=(a,b)(b,c)(b,c)(c,d)=(a,b,c)(b,c,d)\)
  
• 对于三个不同的元素 \(a,b,c\)，\((a,b)(b,c)=(a,b,c)\)
  由于 \(g\) 为偶，因此 \(g\) 的逆也为偶。因此，我们只要思考如何实现任何三个元素的轮换就可以了。

这也是可以实现的。首先，我们需要了解置换对轮换的共轭是什么样的。假设 \(g\) 是置换。\[g(x_1,\cdots,x_n)g^{-1}=(g(x_1),\cdots,g(x_n))\]这是因为只有 \(g^{-1}g(x_i)=x_i\)，而 \(x_i\) 会被轮换改变，因此只有 \(g(x_i)\) 这些元素会被轮换改变，其他的数并不会被轮换改变，之后进行的 \(g\) 可以和 \(g^{-1}\) 抵消，因此就相当于 \(g(x_i)\) 这些元素进行轮换。在这里不严格进行证明了，可以多模拟几遍感受一下。

我们先来讨论 \((i,12,15),i\in \{1,2,\cdots,11,13,14\}\) （没有 \(12\) 和 \(15\)）这样的轮换。一定存在置换 \(f:S\mapsto S\) 满足 \(f(11)=i,f(15)=15,f(12)=12\)，其他元素我们不关心。此时 \(f(11,12,15)f^{-1}=(f(11),f(12),f(15))=(i,12,15)\)

接下来考虑 \((i,j,15),i\not = j\space \text{AND}\space i,j=\in \{1,2,\cdots,11,13,14\}\)。\[\displaylines{(i,j,15) &= (j,15,i)\\ &=(j,15)(15,12)(12,15)(15,i)\\&=(j,15,12)(12,15,i)}\]对于 \((i,j,12)\) 的情况同理。

最后，就是任意三个元素 \(i,j,k\) 的轮换 \((i,j,k)\) 了。\[\displaylines{(i,j,k)&=(i,j)(j,k)\\&=(i,j)(j,15)(15,j)(j,k)\\&=(i,j,15)(15,j,k)}\]至此，任何三轮换就都可以进行了。因此，偶置换总是可解的。

扩展

\(n\times n\)

上面的两种方法很容易扩展到 \(n\times n\) 的情况。实际上，从 \(4\times4\) 扩展到 \(n\times n\) 只需要改变集合 \(S\) 的大小和轮换部分的数值。集合 \(S\) 的大小实际与证明过程并无关系，因此只要将 \(12\) 和 \(15\) 替换成 \(n^2-n\) 和 \(n^2-1\) 即可。

逆序对

考虑轮换方法。首先我们考虑只是用临项交换来将解决问题。所需要的置换次数其实就是序列的逆序对个数。由于这种只用临项交换的方法和其它使用对换的方法都是 \(g\) 的逆，因此它们的奇偶性相同。所以一个状态是否可解就只需要看逆序对的奇偶性就可以了。

空格

如果空格不在最右下角怎么办？考虑将空格移到右下角的过程。我们已经知道可解性和逆序对的关系了，因此我们只要注意逆序对个数就可以了。左右移动空格并不会改变逆序对个数，而像下移动空格会使逆序对发生变化。由于一个数和空格交换，到了 \(n-1\) 个数之前。这就相当与这个数与前一个数交换 \(n-1\) 次的结果。因为每个数都各不相同，因此每次交换必定对逆序对产生 \(\pm1\) 的变化。由于我们只关心奇偶性，因此我们只关心这些 \(\pm1\) 加起来之后对奇偶性产生的影响，也就是模 \(2\) 的结果。而 \(-1\equiv 1\pmod 2\)，所以它对逆序对奇偶性产生的影响就是 \((n-1)\times 1 \equiv n-1 \pmod 2\)。

换句话将，这个操作对逆序对产生的影响和这 \(n-1\) 个数的大小无关，只和 \(n-1\) 的奇偶性有关！因此，我们只要将原序列的逆序对个数求出，在加上需要移动的行数乘上 \(n-1\)，就可以进行判定了。

任意两个状态是否可达

实际上，通过上面两种方法我们可以了解到，任意两个状态分别记作 \(f,g\)，只要可以通过偶数次对换相互抵达，那么这两个状态在奇数码问题中就可以相互抵达。当然，需要先将空格移动到最右下角。当然，由于两个状态都需要加上行数乘上 \(n-1\)，我们只需要计算行数差在乘上 \(n-1\) 就可以得到影响了。

\(n\times m\)

这个问题的推广实际上也不是很难，只需要将上面两个问题的 \(n-1\) 替换位 \(m-1\) 即可，因为只有这两项和列数有关。