PKU上面的1077是经典题目——八数码，在《人工智能》这门课中是重点的研究对象，引领前面几章的内容，可见其在搜索方面的典型性。

已知：3*3的格子，以及每个格子的数字（1~8和一个'x'，两两不同），每次只能够移动x那个格子，并且只能往左右上下四个方向移动
目标：某种状态，在该题中为
            1 2 3
            4 5 6
            7 8 x
未知（所求）：如何从给出的一个状态，经过一系列的移动，到达目标状态

解决问题从提出问题开始：
1.已知和未知有啥关系？
答：目标状态是由已知状态一步步移到的。
2.是否一定存在解呢？
答：从题目得知，有时候会得不到解（当仅仅只有两个数字不在原来的位置上时无解）。
3是否在以前遇到过类似的问题？
答：象棋上马的走法，从一个点到达目的点的搜索过程，因此考虑可以用类似的方法来寻找答案，也就是搜索。
4.除了搜索还有其他方法可以解决这个问题么？
答：暂时没有人发现，
5.如何搜索？
答：从起始位置开始，向四个方向尝试，一旦往一个方向尝试了，则要防止呆会又往原来的位置尝试的问题，于是除了一开始外，其他的每次最多只能往3个方向的尝试。
6.如何判断当前状态是否已经是目标状态？
答：每行每列都和目标状态的比较。

好，我于是很快的写出来一个DFS的程序（DFS不需要额外的空间，不需要记住状态到达哪里，比BFS容易写）
运行后，发现出错，通过用断点调试了一会后，处理了几个小错误后，遇到一个问题：
7.我的程序总是得不出结果。
答：因为DFS的话，你必须要确定他会到达一个终点就回溯，问题就出在我的程序不会出现无路可走的情况，因为他不会判断当前状态是否已经是之前走过的，所以会一步循环走下去，甚至明明一步就能到达目的地，他还是要走无限远的路，直到程序被迫跳出。
8.如何处理这个问题？
答：既然是因为递归的无限深度，那我们就给他一个深度极限，当到达这个深度时，就返回。接下来的问题是：
9.这个深度该是多少？
答：一个深度就代表一步，八数码的问题最多需要走多少步就一定能够到达目标呢？（注意，是一定），如果这个深度开太小了，有可能找不到解，如果这个深度开太大了，又会让程序不断递归下去。所以需要自己试验。

我先设了个100，发现可以得出结果，但是那个步数也就是100步左右（因为DFS找到的路径不是最短的，而是最靠近某一个方向的），和sample output的19步不同啊，于是我改成19步，结果出来的答案也是19步，只是和给出的不同，为了验证我的答案也是正确的，我撕了一张纸，在上面写了个八数码，并且按照我给出的步骤去走，最终确实到达目标了，可见我的算法是正确的。

10.求的不是最短步骤，能行么？
答：再次检查题目，发现并没有要求最短路径，并且题目显示是Special Judge，可见应该可以。

最终提交时，我把深度定为500（因为定为1000时我自己的程序崩溃了），居然一次性过了，花费的空间是208K，时间是 875MS，再看一个师弟的提交，空间是9816K，时间是438MS，可见DFS和BFS的区别。


然后我又分别试了下将深度改为200，350，结果都是TLE，证明一个问题：

有时候花费较长的时间一次性找到一个解，比花费较短的时间而多次找不到解，要来得快。