奇数码问题初探

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

题目简介

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

可解性

赏金

1896 年，美国著名棋手SamLoyd 曾经悬赏1000 美金，来看看有没有人可以解出这个问题：其中只有 和 是进行交换的。我们将稍后来解决这个问题。你可以自己玩玩看，看看你能不你拿到这1000美元

对换，置换与轮换

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

• 置换，又叫排列，指的是在集合 中的双射 。例如，对于 ，定义 ， 就是一个置换。实际上，如果用 替换 ，会发现其实集合里面每个数都出现了，只是顺序可能不同。就像这样刚刚这种表示也可以用来记录一个置换。即特别的，对于 这种映射也是置换，成为恒同变换或者叫恒同置换，记作 。
  
• 对换，顾名思义，就是只有两个元素进行了交换，其他元素不变。形式化的， 是对换是指存在 ，并且对于其他元素 ，我们可以用 来表示这是一个交换 的对换。假设 ，我们可以用 来表示一个对换，它的涵义就等于
• 轮换，就是指几个元素轮流交换。形式化的，就是对于若干的元素，我们用 来表示这个轮换。举个例子，假设 ， 就是指这个置换 其中有一些结论并不是本文的重点，在下文会直接使用，建议先了解一下相关知识。

可解性判定

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

奇变换与偶变换

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

轮换

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

考虑在这个问题之中到底有什么操作可以进行。首先，对于这样的四个格子，可以让空格转一圈来使三个元素进行轮换。可以进行任意次轮换。

然后，我们可以通过将空格移到任意一个位置，在像上面一样进行轮换，接着原路返回，就可以在任意位置实现像这样的三轮换了。因此所有像这样的轮换都可以进行。

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

• 对于四个不同的元素 ，
  
• 对于三个不同的元素 ，
  由于 为偶，因此 的逆也为偶。因此，我们只要思考如何实现任何三个元素的轮换就可以了。

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

我们先来讨论 （没有 和 ）这样的轮换。一定存在置换 满足 ，其他元素我们不关心。原因是覆盖 和 的轮换只包含右下角的那个三轮换，因此你只要不进行右下角的轮换， 和 就不会改变。而只利用其余位置的三轮换将除了 的任意数码移动到 的方法是容易构造的，因为可以利用三轮换将一个数码向上/向右移动（请注意我们不需要保证其余数码在原来的位置）。

此时 。

对于 和 的情况只需要在一开始在右下角做即次三轮换即可。

接下来考虑 。对于 和 的情况同理。

最后，就是任意三个元素 的轮换 了。至此，任何三轮换就都可以进行了。因此，偶置换总是可解的。

扩展

上面的两种方法很容易扩展到 的情况。实际上，从 扩展到 只需要改变集合 的大小和轮换部分的数值。集合 的大小实际与证明过程并无关系，因此只要将 和 替换成 和 即可。

逆序对

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

空格

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

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

任意两个状态是否可达

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

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