数字华容道（15 Puzzle Game）：解存在问题的研究

15 Puzzle解的研究

这个游戏是在一个 $4\times 4$ 的棋盘上进行的。在这个棋盘上，有 $15$ 个编号为 $1$ 至 $15$ 的棋子。有一个格子是空的（用 $0$ 表示）。你需要通过反复将其中一个块移到空位上，将棋盘复原为下面的形式。

$$\begin{array}{cccc}1& 2& 3& 4\\ 5& 6& 7& 8\\ 9& 10& 11& 12\\ 13& 14& 15& 0\end{array}$$

该游戏 15 Puzzle 由 Noyes Chapman 于 1880 年发明。

解的存在

让我们考虑这个问题：给定棋盘上的一个位置，确定是否存在一系列的移动来复原棋盘。

假设我们在棋盘上有一些位置：

$$\begin{array}{cccc}{a}_1& a_2& a_3& a_4\\ a_5& a_6& a_7& a_8\\ a_9& a_{10}& a_{11}& a_{12}\\ a_{13}& a_{14}& a_{15}& a_{16}\end{array}$$

其中一个元素等于 0 并表示某一格为空，即 $a_z=0$ 。

让我们考虑以下情况：

$$a_1{a}_2...a_{z-1}{a}_{z+1}...a_{15}{a}_{16}$$

即对应于棋盘上没有零元素的位置的数字排列

设 $N$ 为该情况的反转数（即 $i<j$ ，但 $a_i>a_j$ 的此类元素 $a_i$ 和 $a_j$的数量）。

假设 $K$ 是空元素所在行的索引， $K=（z-1）÷4+1$。

那么，当 $N+K$ 为偶数时，解存在。

---

实现

上面的算法可以用下面的程序代码来说明：

int a[16];
for (int i=0; i<16; ++i)
    cin >> a[i];

int inv = 0;
for (int i=0; i<16; ++i)
    if (a[i])
        for (int j=0; j<i; ++j)
            if (a[j] > a[i])
                ++inv;
for (int i=0; i<16; ++i)
    if (a[i] == 0)
        inv += 1 + i / 4;

puts ((inv & 1) ? "No Solution" : "Solution Exists");

---

证明

1879 年约翰逊证明，如果 $N+K$ 是奇数，则解不存在，同年 Story 证明了所有情况下， $N+K$ 为偶数时，有解。然而，所有这些证明都相当复杂。

1999 年，Archer 提出了一个更简单的证明（您可以在此处下载他的文章）。