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

数字推盘游戏 - 维基百科

固定一个空位时的情形

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

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


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

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

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

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

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

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

记空位为

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

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

  1. 不在盘的四角。

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

  2. 恰在盘的四角。

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

引理2:连续三个水平(竖直)的非空位块的 不改变合法性。

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

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

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

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

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

可解性

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

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


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