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

Author Avatar
Ivan Chen 4月 10, 2021
  • 在其它设备中阅读本文章

数字推盘游戏 - 维基百科

固定一个空位时的情形

在一个 $(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的操作来解决最后一行。

本文采用知识共享 署名-相同方式共享 4.0 国际许可协议(CC BY-SA 4.0)进行许可。
本文链接: https://idkidknow.com/2021/04/10/数字推盘-数字华容道-的可解性/