OI-wiki 十五拼图（N-Puzzle）全解：问题定义、可解性判定与 A* 启发式搜索

OI-wiki 十五拼图N-Puzzle全解问题定义、可解性判定与 A* 启发式搜索【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki十五拼图15-puzzle是 OI-wiki 中讲解启发式搜索与 A* 算法最优性的经典建模案例。本文基于 docs/misc/15-puzzle.md 展开系统梳理 N-Puzzle 的规则与命名、可解性的数学判定、寻找最优解的算法框架并结合仓库中的 A* 搜索 文档及其参考实现 astar_1.cpp说明可采纳启发式函数为何能保证最优性。读完本文你将掌握如何判定任意 15 拼图局面是否可复原、如何为 N-Puzzle 设计 A* 启发式函数以及这些结论背后的群论与图搜索原理。一、什么是 15 拼图15 拼图英文15-puzzle又名 Gem Puzzle、Boss Puzzle、Game of 15、Mystic Square 等是一个滑块类游戏sliding puzzle。滑块方盘的长宽均为 $4\times 4$ 个方块其中 15 个位置放序号打乱的方块剩下一个为空位。与空位同行或同列的方块可以通过水平或垂直滑动来移动拼图的目标是按编号顺序排列方块。滑块游戏是一类在平面上滑动方块以组成特定排列的智力游戏。常见的滑块游戏包括数字拼图、华容道和塞车时间。其中 15 拼图是最古老的滑块类游戏发明者是 Noyes Chapman该游戏风靡于 1880 年代。与 tour 类的解谜游戏不同滑块游戏禁止任何一个方块离开盘面这一特性将其与重新排列类的解谜游戏区分开来。15 拼图常见的别称为n-拼图其中数字 $n$ 指方盘中的方块总数不同尺寸变体亦使用类似命名名称方盘尺寸方块总数说明8 拼图8-puzzle$3\times 3$8即经典「八数码」问题15 拼图15-puzzle$4\times 4$15本文主体n×m 拼图$n\times m$$n\times m - 1$滑动方盘的扩展问题注意命名上的歧义15 拼图有时也被称为16 拼图此处的 16 指的是方块容量即空位 15 个方块占满的格子总数。15 拼图的扩展问题有时也包括了 $n \times m$ 的滑动方盘。二、问题定义给定一个 $4\times 4$ 的方盘其中 15 个方块随意排列需要将它们按照序号排列成上图中所示的目标样子。移动规则为每次只能交换空方块和其相邻一个方块的位置。常见问题可以归纳为三类求最少步数找到可解决此问题的最少移动步数即最优解统计错位方块计算错位方位的个数常作为启发式函数或评价指标可解性判定判断给定局面是否能通过合法移动到达最终的有序排列。这三类问题中第 1、3 类与图搜索和置换群理论直接相关第 2 类则与启发式设计紧密相连下文分别展开。三、可解性判定一个局面能否复原并非所有打乱的 15 拼图局面都能复原。以 4×4 方盘为例15 个方块共有 $15!$ 种排列方式但其中恰好只有一半是可达的——这正是 docs/misc/15-puzzle.md 中「可解性证明」一节的结论。3.1 数学证明简史Johnson Story1879证明了如果 $m$ 和 $n$ 都至少为 2则奇偶性结论适用于大小为 $m\times n$ 的棋盘通过从 $mn2$ 开始对 $m$ 和 $n$ 进行归纳可以证明所有偶数排列都是可解的Archer1999给出了另一个证明其思路基于通过汉密尔顿路径Hamiltonian path定义等价类即沿着一条覆盖所有格子的汉密尔顿路径把盘面展开成一条链再分析链上的置换性质。3.2 实用判定条件逆序数 空位行号从可解性证明可以直接导出一个实用的判定算法。将盘面按逐行优先row-major的顺序读成序列跳过空位统计其中的逆序对个数 $I$并记空位所在行从下往上数1 开始为 $r$则有当列数宽度为奇数时局面可解当且仅当逆序数 $I$ 为偶数当列数宽度为偶数时局面可解当且仅当 $I r$ 为奇数等价地$I$ 与 $r$ 的奇偶性不同。为什么需要同时考察空位行号每一次移动本质上是将空位与相邻方块交换。水平移动不改变序列的逆序数奇偶性垂直移动跨越了 $n-1$ 个方块$n$ 为列数会使逆序数奇偶性翻转同时空位所在行号奇偶性也翻转。二者奇偶性翻转的次数总是同步的因此 $I r$对偶数宽度这类组合量才是移动下的不变量。这便是 15 拼图只有一半排列可达的直观原因。以 15 拼图4×4宽度为偶数的标准目标态为例按行优先读出序列为 $1,2,\dots,15$逆序数 $I 0$偶数空位在第 4 行、从下往上数为第 1 行$r 1$奇数$I r 1$ 为奇数满足可解条件。逆序对概念及其计数方法在仓库中有完整实现材料逆序数 章节提供了参考实现归并排序 章节说明了用归并排序在 $O(n\log n)$ 时间内统计逆序对的方法也可使用树状数组求解。四、算法从任意解到最优解4.1 复杂度边界求解容易最优解困难寻找数字滑盘游戏的一个解相对容易——例如可以按行、按列逐层归位采用构造性的还原策略即可。但寻找最优解是一个NP 困难问题。已知的最优解长度上界为15 拼图的最优解至多有 80 步而 8 拼图的最优解至多有 31 步这些界来自 Korf 等研究者对解空间的系统性搜索参见原文档引用的文献。4.2 将拼图建模为图搜索问题N-Puzzle 的状态空间天然是一个图每个局面是一个结点一步合法移动空位与相邻方块交换对应一条边。因此广度优先搜索BFS逐层扩展天然保证找到的步数最少边权均为 1但状态空间极大15 拼图约有 $\frac{16!}{2}$ 个可达状态朴素 BFS 无法直接用于 15 拼图深度优先搜索DFS/ 迭代加深内存占用低但不保证最优常与启发式剪枝结合A* 搜索结合 $g$已走步数与启发式 $h$剩余步数估计进行最佳优先搜索是求解 8/15 拼图最优解的主流框架。4.3 可采纳启发式与 A* 的最优性A* 算法的核心公式为$$ f(x) g(x) h(x), $$其中 $g(x)$ 是从起点到结点 $x$ 的实际代价$h(x)$ 是对从 $x$ 到终点的剩余代价 $h^*(x)$ 的估计。其最优性依赖启发式函数的两个性质详见仓库的 A* 搜索 文档可采纳性admissible$0 \le h(x) \le h^(x)$即永远不会高估剩余的移动次数。满足此条件时 A一定能找到最优解一致性consistent$h(x) \le h(y) d(x,y)$三角形不等式。此时 A* 不会将已弹出队列的结点再次加入队列效率更高。对 15 拼图而言启发式函数 $h(n)$ 可以取原文档给出的三种选择放错的方块的数量每个方块错位就计数 1。由于一步移动只改变一个方块的位置错位数量每步至多减少 1因此该启发式可采纳所有放错的方块到各自目标位置的欧几里得距离之和方块每次只移动单位步长到目标的直线距离每步至多减少 1故总和可采纳所有放错的方块到各自目标位置的曼哈顿距离之和方块一次只移动一格其曼哈顿距离每步恰好变化 1总和每步至多减少 1因此可采纳且同时满足一致性。曼哈顿距离的定义与性质见 曼哈顿距离 章节。4.4 仓库中的 A* 参考实现在仓库的 八数码例题 中8 拼图3×3被作为 A* 的经典应用。其参考实现位于 astar_1.cpp关键设计可以直接迁移到 15 拼图状态表示matrix结构体存 3×3 棋盘重载运算符以支持set判重启发式函数h(matrix a)统计「不在目标位置且非空位」的方块个数即上述第 1 种可采纳启发式估价排序优先队列priority_queuenode按t h(a)排序node重载时比较t h每次弹出估价最小的状态转移生成定位空位0号点后枚举上下左右四个方向dx[4] {1,-1,0,0}, dy[4] {0,0,1,-1}用swap模拟「空位与相邻方块交换」并用set剪去重复状态——这与 15 拼图的移动规则完全一致只是棋盘从 3×3 扩为 4×4、启发式换为曼哈顿距离之和。该实现中h取错位方块数时A* 等价于对 BFS 的剪枝优化若换用曼哈顿距离之和更接近真实的 $h^$扩展的结点数会显著减少——这正是 docs/search/astar.md 中所说的「$h$ 越接近 $h^$算法搜索到的分支就越少」。此外当 $h \equiv 0$ 时 A* 退化为 Dijkstra 算法在边权为 1 时即 BFS。五、群论视角滑块游戏与交错群15 拼图不仅是一个搜索问题其状态集本身构成一个群。因为 15 块的数字推盘游戏组合可以由「3 循环」3-cycles产生所以可以证明 15 块的数字推盘游戏可以用交错群 $A_{15}$ 表示。事实上任何使用 $2k-1$ 块方块同面积正方形的数字滑盘游戏皆可以交错群 $A_{2k-1}$ 表示。这一结论与第三节的可解性判定互为印证交错群 $A_n$ 恰为 $n$ 个元素全部偶排列构成的群规模为 $n!/2$这与「15 拼图可达状态恰好占全部排列的一半」完全一致也为「任何两块方块不能交换而其余保持不变即无法仅产生一次对换」提供了代数解释。六、练习与拓展阅读练习题N PuzzleHackerRank将 8 拼图推广到任意 n×n 的 N-Puzzle综合考察可解性判定与搜索实现A. Amity AssessmentCodeforces 645A基于 2×2 滑盘的判定类问题适合验证群论与奇偶性直觉Sliding PuzzleLeetCode以 2×3 棋盘为载体的最短路径搜索题可直接套用 BFS/A* 框架POJ 1077 - EightPOJ经典「八数码」题目是 A* 曼哈顿距离的入门练手题输入输出格式规范、评测数据经典。参考资料15 puzzleWikipedia 词条拼图历史、变体与可解性判定的权威综述jrdnjacobsonHow to Solve the 15 Puzzleinstructables面向操作的还原策略教程Korf, R. E.2000Recent Progress in the Design and Analysis of Admissible Heuristic FunctionsSARA 2000, LNCS 1864, pp. 45–55可采纳启发式函数设计与分析的权威文献也是 15 拼图最优解研究的关键参考N-Puzzle 在线演示tristanpenman.com/demos/n-puzzle可交互体验不同尺寸拼图的搜索与还原过程。小结15 拼图是启发式搜索建模的经典载体。在 OI 竞赛中围绕它可以拆解出三类核心能力——用逆序数 空位行号快速判定可解性、用 A* 可采纳启发式曼哈顿距离为优求解最短路径、用交错群理解状态空间的代数结构。上述所有概念与实现均可在 docs/misc/15-puzzle.md、A* 搜索、启发式搜索、曼哈顿距离 及 astar_1.cpp 中继续深入。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考