题目重点：把滑块合法移动建图；小局面 BFS 精确，完整 4×4 用可采纳启发式的 A*/IDA*，先判不可达。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 4×4 有数字 1..15 与一个空格 0，目标为按行 1..15、右下角 0；一步只交换空格与其上下左右邻格。
- 输入必须恰是 0..15 的一个排列；不可达返回 -1。若原题的‘合法状态’是任意不同目标，奇偶规则与启发式需按该目标调整。
- 只返回最少移动次数，不输出动作序列；要输出路径需存 parent 或在 IDA* 路径栈中记录移动。
解题路线
- 将每个排列当节点、一次合法空格交换当无权边，问题是到目标的最短路径。若给的是极浅状态，BFS 首次到达目标即最短；双向 BFS 从两端扩张可降浅层状态数。
- 先检查奇偶可达性：对标准 4×4 目标，去掉 0 后的逆序数与空格自底向上的行号之和为奇数才可达；交换两块数字而不动空格必翻可达性。
- 完整 15-puzzle 用 Manhattan 距离 h=每块到目标格的行列差绝对值之和，它每次合法移动最多减少 1，因此不高估剩余步数；A* 按 f=g+h 出队首次得到目标时是最短路径。
- A* 的 open/visited 内存最坏可指数增长；IDA* 以 f 阈值迭代加深，保存当前路径、反向移动剪枝和可选 pattern database，可减内存但可能重复展开。
- 面试先说明可达性和规模，问是要展示 BFS 思路、处理浅状态，还是要在一般 4×4 上可执行；不能无条件承诺普通 BFS 能跑完。
手动走一遍
目标局面只把空格左边的 15 与 0 交换一次，最少 1 步。若在目标上把 14 与 15 互换而空格位置不变，逆序奇偶翻转，无法通过合法移动达到目标，返回 -1；穷举 BFS 不应在此输入无限搜索。
规模与取舍
状态总数为 16!/2 个可达排列，完整 BFS 时间与内存最坏同数量级；A*/IDA* 实际展开依启发式强度而变，最坏仍指数。单次 Manhattan 计算 O(16)，若增量更新可 O(1)；IDA* 路径空间与解深度成正比。
易错点与追问
容易失分的边界
- 把 4×4 全状态 BFS 说成可轻松遍历。
- 不做可达性判断就在无解局面耗尽搜索。
- 把包含空格的逆序数直接套用标准奇偶公式。
- 用会高估剩余步数的启发式却仍宣称 A* 保证最短。
- ‘合法状态’目标没定义就给唯一答案。
继续深挖
- 如何输出最短动作序列？
- 双向 BFS 适用于多深的局面，内存如何估？
- pattern database 为什么保持可采纳，怎样处理重叠模式？
- 目标排列不是标准升序时奇偶规则如何转写？
