N-拼图游戏的可解性

所谓的N-拼图 (N-puzzle) 是一种流传很久的智力游戏,是谁发明已无法考证。1865年Embossing公司发售了这款游戏的一个版本,使得其风靡一时。常见版本的有 8 块和 15 块的两种,非常类似游戏“华容道”。以 15 块的拼图为例,玩家需要通过移动一个方形容器中的各个小方块,将一副打乱的拼图恢复成初始形态(如下图)。
15-puzzle

标有数字的拼图没什么意思,也有打乱图片的版本。像QQ三国里有段时间就有(腾讯把这个游戏叫做华容道,但其实不是),考古了一张图片:
QQ三国的“华容道”

显而易见,如果不把容器中的方块拿出来,而是随机地在容器中通过上下左右移动小方块来打乱顺序,拼图总是可以恢复的,因为每一步的上下的移动操作都是可逆的。但假设我们可以把方形容器中的小方块倒出来,再打乱顺序放进去,那么此时的拼图是否总可以恢复呢,是否又有办法来判断它能否恢复原状呢?

观察最简单的 2×2 的拼图,很容易发现 2×2 的时候就有不能恢复的情况,所以N-拼图并不总是可解的。
不可解的

事实上对于任意的 \(m \times n (m \ge n \ge 2)\) 拼图,恰有一半的情况是可解的。

设 \(U = \{1, 2, \ldots, m\}\times\{1, 2, \ldots, n\}\).

\(p = (a, b), q = (c, d) \in U\)的曼哈顿距离定义为 \(d(p,q)=|a-c|+|b-d|\).

设 \(s: U \rightarrow U\) 是一个双射,它可以记录游戏的状态,例如 \(s(p)=q\) 可以表示 \(p\) 位置被 \(q\) 方块占据。交换转置 \(r: U \rightarrow U\) 也是一个双射,它交换两个位置的方块,使得其余的方块位置不变。一个有效的游戏操作步是对满足 \(d(p, B) = 1\) 的方块 \(p\) 和空白块 \(B\) 实施交换。操作后的游戏状态即为 \(r \circ s\).

可解的一个必要条件

先考虑空白块位于右下角的初始情况,注意到最终状态的空白块也在最右下角。而空白块只能上下左右移动,空白块每向上移动一次后来就要向下移动一次回到原来的行,所以空白块上下移动的次数是偶数次,同理左右移动的次数也是偶数次,总共的转置次数也就是偶数次。所以初始的排列必须是偶排列。更一般化一些,就是:
如果一个初始游戏状态(排列)为 \(s\) 的 \(m \times n (m \ge n \ge 2)\) 拼图可解,那么必然有 \(s\) 的奇偶性和 \(d(B, (m, n))\) 相同。

注:奇排列是交换奇数次的排列,逆序对为奇数,偶排列是交换偶数次的排列,逆序对为偶数。

充分性

上述的必要条件也是充分的。可以先证明空白块位于右下角的情况。首先考虑 2 × 2 的情形,这时这样的偶排列一共有 3 种,每一种都是可解的。
2乘2的情况

接下来考虑 m × n 的情形,假设我们是一行一行地拼的,并且已经拼完了前 \(i – 1\) 行和第 \(i\) 行的前 \(j – 1\) 个元素, 现在我们想要在不打乱已经排好的元素的情况下将 \((i,j)\ (i \le m – 2, j \le n – 1)\) 移动到位置 \((i, j)\).

这总是可行的,由于它不是一行的最后一个元素,也不是倒数两排的元素,所以我们总可以找到一个至少两格宽的不包括已排好的元素的L型或者矩形的区域同时包括了空白元素和要排的元素,然后把空白块移到要排的元素旁边,逐步地折叠式地把这块元素移到正确的的位置。
移动到指定位置

对于每行的最后一个元素,如果已经恰好排在位置上那么就不用管它,如果不在位置,那么我们把它先放到正确位置的下面,再将空白块放到它的下面,然后在 3 × 2 的区域中依次运用进行操作:下下右上左上右下下左上,如图所示。
flowchart

当只剩下最后两行没有完成时,再把容器横过来(顺时针转 90°),接着运用上面的方法,直到剩下最右下角一块 2 × 2 的小区域。把空白块移动到最右下方,观察到空白块的位置没有变,因此这时我们完成了偶数次变换,最初的状态也是偶排列,所以最后的 2 × 2 的区域是一个偶排列,而 2 × 2 的所有三种偶排列都是可解的,问题解决。

另外对于空白块不在最右下角的情况,将空白块先移到右下角会使用 \(d(B, (m, n))\) 次操作,排列就会变成一个偶排列,问题转化为上面的情况。

6 thoughts on “N-拼图游戏的可解性

  1. 膜拜图论大神,有点意思

  2. 你还真是空 诶

  3. 高端大气~

Leave a Reply

Your email address will not be published. Required fields are marked *