数字推盘游戏 - 维基百科

固定一个空位时的情形

在一个 $(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$，于是得到了同样的结论。$\quad \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的操作来解决最后一行。