对八数码游戏，回溯应发生在以下三种情况：
　　①新生成的状态在通向初始状态的路径上已出现过；
　　②从初始状态开始，应用的规则数目达到所规定的数目之后还未找到目标状态（这一组规则的数目实际上就是搜索深度范围所规定的）；
　　③对当前状态，再没有可应用的规则。
　　图1.7表示出回溯策略应用于八数码游戏时的一部分搜索图。其中圆圈中的数字表示回溯的种类。
　　这里规定的搜索深度范围到第六层，即用了6条规则后还未找到目标就要回溯到上一层。显然路长在6以内的所有路径都会被搜索到，因此对这个问题，一定能找到解。然而对一般情况，深度设置太浅时，有可能找不到解，设置太深有可能导致回溯次数激增，因而应根据实际情况来规定搜索范围，先设置适中的深度搜索，失败时再逐步加深。
回溯过程是一种可试探的方法，从形式上看不论是否存在对选择规则有用的知识，都可以采用这种策略。即如果没有有用的知识来引导规则选取，那么规则可按任意方式（固定排序或随机）选取；如果有好的选择规则的知识可用，那么用这种知识来引导规则选取，就会减少盲目性，降低回溯次数，甚至不回溯就能找到解，总之一般来说有利于提高效率。此外由于引入回溯机理，可以避免陷入局部极大值的情况，继续寻找其他达到目标的路径。
（3）图搜索方式：如果把问题求解过程用图或树的这种结构来描述，即图中的每一个节点代表问题的状态，节点间的弧代表应用的规则，那么问题的求解空间就可由隐含图来描述。图搜索方式就是用某种策略选择应用规则，并把状态变化过程用图结构记录下来，一直到得出解为止，也就是从隐含图中搜索出含有解路径的子图来。

图1.8八数码问题的搜索树

　　图1.8表示出一种图搜索策略求解八数码问题时所得到的搜索树。可以看出这是一种穷举的方式，对每一个状态可应用的所有规则都要去试，并把结果记录下来。这样，求得一条解路径要搜索到较大的求解空间。当然，如果利用一些与问题有关的知识来引导规则的选择，有可能搜索较小的空间就能找到解，这些问题将在第二章研究具体图搜索算法时再进一步讨论。
　　以上简单介绍了三种控制方式，可以看出不可撤回方式相当于沿着单独的一条路向下延伸搜索下去；回溯方式则不保留完整的搜索树结构，只记住当前工作的一条路径，回溯就是对这条路径进行修正；图搜索方式则记下完整的搜索树。对一个要求解的具体问题，有可能用不同的方式都能求得解，至于选用哪种方式更适宜，往往还需要根据其他一些实际的要求考虑决定。