九宫格滑块拼图PYTHON算法 9格滑块拼图攻略78换位

九宫格拼图就是在3×3的格子上摆放8块拼图，空出1个格子，玩家要借助这1个空格上下左右滑动拼图，最终完成整幅图画

我们像下面这样将空格定为0，然后给8块拼图分别标上1到8号

1 3 0 4 2 5 7 8 6

1次操作可以将1块拼图移向空格，当8块拼图全部与下述位置吻合时完成游戏

1 2 3 4 5 6 7 8 0

现给定九宫格拼图的初始状态，请编写一个程序，求出完成该九宫格拼图最少需要移动多少次

输入： 输入表示拼图块或空格的3×3个整数。每3个整数占1行，总计3行，相邻数据间用空格隔开输出： 输出最少移动次数，占1行限制： 给定拼图必然有解。

搜索算法可以通过重复进行“状态迁移”来寻求拼图的解法，也就是说，我们可以利用搜索算法求解这类拼图问题。一般来说，搜索算法会生成一个从初始状态到最终状态（完成状态）的状态变化序列。而在九宫格拼图问题中，我们还需要从所有可能的序列中选择最短的一条

为避免重复生成相同的状态，大部分搜索算法的搜索空间都为树结构，树的结点表示状态，边表示状态迁移

九宫格拼图中，各拼图块和空格的位置就是“状态”，上下左右移动拼图块相当于“状态迁移”。要想有效管理各个状态（拼图格局）的生成情况，需要应用散列法或二叉搜索树

像九宫格拼图这种状态总数不多的问题，我们完全可以用深度优先搜索或广度优先搜索来求解

这里的深度优先搜索与图的深度优先搜索原理相同（参见：深度优先搜索 | DFS | Depth First Search | C/C++实现），从初始状态出发，尽可能地进行状态迁移，直至抵达最终状态为止。不过，一旦搜索遇到类似于下面这样的情况，就中断当前搜索并返回上一状态：

当前状态无法再进行状态迁移时 状态迁移生成了曾经生成过的状态时 根据问题的性质可断定继续搜索无法找到答案时

说白了就是进行回溯。这种打断搜索的处理还可以形象地称为剪枝 有限制的深度优先搜索称为深度受限搜索。该算法会在搜索深度（树的深度）达到某个既定值limit时中断搜索。也就是说，如果能根据问题的性质限制搜索深度，我们就能进一步提高搜索的效率

单纯的深度优先搜索算法具有下列特征： 求出来的不一定是最短解 可能因为部分无用的搜索导致复杂度上升 如果不进行剪枝，在最坏情况下（无解等情况）会变成穷举搜索

这里的广度优先搜索与图的广度优先搜索原理相同（参见：广度优先搜索 | BFS | Breadth First Search | C/C++实现），算法会尽可能广地进行状态迁移

从当前状态出发，进行所有有可能的状态迁移并得到新状态。为能够系统地进行搜索，我们需要将状态迁移后生成的新状态添加至队列，同时从队列开头的状态进一步进行状态迁移，使得搜索不断展开。为防止生成已有状态，我们还需要将已生成状态记录在内存中

广度优先搜索需要占用大量内存，但只要问题有解，就可以相对简单地搜索到初始状态最终状态的最短路径