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

数字推盘游戏 - 维基百科

固定一个空位时的情形

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

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


\(\Rightarrow:\)

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

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

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

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

\(\Leftarrow:\)

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

引理1 \(2\times 2\) 正方形中三个非空位块的 \(3\operatorname{-}\text{cycle}\) 不改变合法性。

记空位为 \(0.\)

对于含有空位的\(2\times 2\) 正方形中三个非空块的置换,注意到 \((3\ 0)(1\ 3)(2\ 1)(0\ 2)=(1\ 2\ 3)(0),\) 另一种 \(3\operatorname{-}\text{cycle}\) 同理。

对于不含空位的 \(2\times 2\) 正方形中任意三个块的置换,记这三个块为 \(1,2,3,\) 记不动的块为 \(4.\)

  1. \(4\) 不在盘的四角。

    总能找到一系列基本操作(它们是对换)\(\alpha_1,\alpha_2,\dots,\alpha_t,\) 其中 \(\alpha_i(1\le i \le t)\) 固定 \(1,2,3,\) 并且 \(\alpha_t\alpha_{t-1}\dots\alpha_1(0)=4.\) 首先依次做 \(\alpha_1,\alpha_2,\dots,\alpha_t\) 的操作,此时 \(0\) 已经在正方形中,因此按照前面的结论,此时复合 \((1\ 2\ 3)\) 不改变合法性。 于是\(\alpha_1^{-1}\alpha_2^{-1}\dots\alpha_t^{-1}(1\ 2\ 3)\alpha_t\alpha_{t-1}\dots\alpha_1\) 不改变合法性,而由于 \(\alpha_i(1\le i \le t)\) 固定 \(1,2,3,\) 于是该操作正是 \((1\ 2\ 3).\) \((1\ 3\ 2)\) 同理。

  2. \(4\) 恰在盘的四角。

    注意到 \((1\ 4\ 3)(1\ 2\ 4)=(1\ 2\ 3),\) 其中\((1\ 4\ 3)\)\((1\ 2\ 4)\) 由1中的结论知不改变合法性,故 \((1\ 2\ 3)\) 不改变合法性,\((1\ 3\ 2)\) 同理。\(\Box\)

引理2 连续三个水平(竖直)的非空位块的 \(3\operatorname{-}\text{cycle}\) 不改变合法性。

对于三个水平相接或竖直相接的非空位块,至少在一个不在角落的 \(2\times 3\) 的矩形中。如果矩形中没有空位,按先长边后短边的顺序标号为 \(1,2,3,4,5,6,\)\((2\ 5\ 3)(1\ 5\ 2)=(1\ 3\ 2),\) 即该三块的 \(3\operatorname{-}\text{cycle}\) 不改变合法性。如果矩形中有空位,只需一次对换 \(\alpha\) 即可移出,再作所需置换 \(\beta,\) 两者不相交,此时作 \(\alpha^{-1}\beta\alpha,\) 结果正是所需的 \(3\operatorname{-}\text{cycle}\)\(\beta,\) 于是得到了同样的结论。\(\Box\)

接下来证明不含空位的 \(3\operatorname{-}\text{cycle}\) 不改变合法性。

记盘中 \((n^2-1)\) 个非空位位置从左到右从上到下依次为 \(1,2,3,\dots,n^2-1,\) 要置换的三个块为 \(a,b,c.\)

首先要把 \(a,b,c\) 移动至 \(1,2,n+1\)(这里假定 \(1,2,n+1\) 没有空位,如果有则改为移动至\(n^2-n,n^2-1,n^2,\) 考虑对称性,这里只讨论\(1,2,n+1\)),由引理2这是显然可行的。记该操作为 \(\alpha,\)\(\alpha(a)=1,\alpha(b)=2,\alpha(c)=n+1.\)

给出操作 \(\alpha^{-1}(1\quad 2\quad n+1)\alpha,\) 该操作能分解为基本操作,且它等于 \((\alpha^{-1}(1)\quad \alpha^{-1}(2)\quad \alpha^{-1}(n+1))=(a\ b\ c). \quad \Box\)

可解性

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

设定还原状态为初始状态。由前面的结论知:\((n^2-1)\text{-puzzle}\) 是可解的,当且仅当,空位在白色块且方块为偶置换,或空位在黑色块且方块为奇置换。


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