使用A*算法求解8数码问题时，如何避免选取旧步数棋盘？

• 先明确关键前提：队列里的每一个棋盘状态，都是从初始状态通过合法移动一步步生成的。只有合法移动得到的相邻棋盘才会被加入队列，所以所有队列中的状态本身都是合法且可达的，不存在“不合法”的状态。
• 你担心的“从当前处理的棋盘移动到旧相邻棋盘不合法”是个误解——A*每次取出优先级最低的状态时，并不是从当前刚处理的棋盘“移动”过去，而是直接处理这个状态本身。这个旧状态能进入队列，本身就证明它是通过合法路径来的，只是可能之前有更优的路径先被处理了。
• 至于你从没遇到这种情况，核心原因是曼哈顿距离作为启发函数是可采纳的（不会高估到目标的剩余步数）。当某个状态第一次被从队列中取出时，我们就已经找到了到达它的最短路径。队列里如果还有这个状态的旧版本（路径步数更多），它的优先级（步数+曼哈顿距离）肯定比已取出的版本高，永远不会成为优先级最低的候选，自然不会被选中处理。

内容的提问来源于stack exchange，提问作者Ivica