数字推盘(数字华容道)的可解性

数字推盘游戏 - 维基百科

固定一个空位时的情形

在一个 中，固定空位的位置并设定一个初始状态，则 个方块的状态可表示为一个置换（初始状态即为恒等函数）。称一个游戏状态合法，是指该状态可由初始状态进行若干次操作获得（当然最终的空位位置和原来是一样的）。

我们将证明，游戏状态合法当且仅当该状态为偶置换。

对于一个合法的游戏状态，考虑从初始状态进行若干次操作的过程。

按照游戏规则，可进行的操作都可以分解为几个基本操作的组合，而基本操作就是空位和上下左右某一块的对换。

我们只关注空位的轨迹，水平方向上的对换不影响空位的纵坐标，竖直方向上的对换使空位的纵坐标。最终空位位置必须和初始状态相同，因此竖直方向上的对换必为偶数次。

同理，水平方向上的对换也为偶数次，因此该状态是偶数次对换的复合，即为偶置换。

易证任何偶置换可以分解为若干 的复合。只需证明用基本操作能实现 （不含空位） 即可，此时 不改变状态的合法性。

引理1： 正方形中三个非空位块的 不改变合法性。

记空位为 。

对于含有空位的 正方形中三个非空块的置换，注意到 另一种 同理。

对于不含空位的 正方形中任意三个块的置换，记这三个块为 ，记不动的块为 。

  1. 不在盘的四角。

    总能找到一系列基本操作（它们是对换） 其中 固定 ，并且 首先依次做 的操作，此时 已经在正方形中，因此按照前面的结论，此时复合 不改变合法性。 于是 不改变合法性，而由于 固定 ，于是该操作正是 。 同理。

  2. 恰在盘的四角。

    注意到 ，其中 和 由1中的结论知不改变合法性，故 不改变合法性， 同理。

引理2：连续三个水平（竖直）的非空位块的 不改变合法性。

对于三个水平相接或竖直相接的非空位块，至少在一个不在角落的 的矩形中。如果矩形中没有空位，按先长边后短边的顺序标号为 ，有 ，即该三块的 不改变合法性。如果矩形中有空位，只需一次对换 即可移出，再作所需置换 ，两者不相交，此时作 ，结果正是所需的 即 ，于是得到了同样的结论。

接下来证明不含空位的 不改变合法性。

记盘中 个非空位位置从左到右从上到下依次为 ，要置换的三个块为 。

首先要把 移动至 （这里假定 没有空位，如果有则改为移动至，考虑对称性，这里只讨论），由引理2这是显然可行的。记该操作为 ，则 。

给出操作 ，该操作能分解为基本操作，且它等于

可解性

将右下角的格染成白色，然后将其他格染成黑色或白色使得黑白不相邻（实际上就是按横坐标+纵坐标的奇偶性分类）。注意到把空位从黑色格移到右下角需要奇数次对换，从白色格移到右下角需要偶数次对换。

设定还原状态为初始状态。由前面的结论知： 是可解的，当且仅当，空位在白色块且方块为偶置换，或空位在黑色块且方块为奇置换。

我们完成了可解性的讨论，并实际上给出了一种该游戏的玩法（虽然并不方便）：按照证明中的步骤不停地做三块轮换即可。引理2确实是很有用的，比如在 中，你可用引理2的操作来解决最后一行。