15-puzzle

15-puzzle

天命奇御是好玩。

但，我感觉我的一大收获就是学会了拼图，或者说是「数字华容道」，又或者说是「15-puzzle」。

数字华容道这种小游戏在很多游戏里面都有涉及，印象中最早在游戏里面接触是「洛克王国」。

以前玩数字华容道，都是凭感觉就过了。

这种感觉还是比较奇妙的，类似于给你 5 + 6，你就能「不思考」得出 11。

即使没通过直觉达到目标图形，你也能通过多次尝试就通过直觉试出来了。

包括在这个游戏中第一次大相国寺的拼图，我也是通过直觉就过去了。

但在第二次拼图，我却没通过去（感觉是玩太久了，当时直觉有点钝了 hh）。

于是我就想这种机制简单的游戏，不像推箱子，华容道这种复杂的游戏（这类游戏我直觉来说还是靠直觉尝试 + 脑内搜索），应该会有一种通解，于是就有了以下内容。

理论

首先扔下 OI WIKI（没想到这也有）。

OI WIKI 给出的有解性判断只是 15 的情况，扩展一下：

首先给出结论，对于 $m * n$ 的矩阵，将 $m * n - 1$ 个数字按行衔接的方式铺成一维数组，求得逆序对数，令为 $r$。

• 若 $m$ 为奇数，则**$r$ 为偶数有解，为奇数无解**

• 若 $m$ 为偶数

  • 若空白块位于奇数行（从上往下数）：$r$ 为奇数有解，否则无解
  • 若空白块位于偶数行（从上往下数）：$r$ 为偶数有解，否则无解

以上的必要性根据空白块的移动所造成的逆序对奇偶变化，很容易得证。

充分性在此暂且不谈。

同样值得注意的是，求最优解是一个 NP-Hard 问题。

实操

说完理论的部分，那对于一个这样的问题，如何能通过实操得到一个确定性的通解呢？

首先考虑最简单的 $3 * 3$ 情况……很好，你学会了。

其次考虑高阶的情况，我们考虑如何将高阶转换成低阶。

步骤如下：

1. 首先将 $m * n$ 模型转换成 $t * t$ 模型，其中 $t$ 为 $\min(m, n)$；
2. 划分 $t - 3$ 个阶段，第 $i$ 个阶段，拼好第 $i$ 行和第 $i$ 列。注意到，这种操作可以在不影响之前阶段的情况下完成；
3. 最后未完成的是一个 $3 * 3$ 的一个模型，同样可以在不影响已完成的部分的基础上完成。

当然，以上说的比较抽象，详情可见知乎回答。

最主要还是要学会有种「让步」的感觉的 trick，就能一招鲜。

总结

这种小游戏的理论和实操研究都还是挺有趣的。