回溯法（英语：backtracking）是暴力搜索法中的一种。 对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。 <br> 在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。） <br> 回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况： 找到一个可能存在的正确的答案 在尝试了所有可能的分步方法后宣告该问题没有答案 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。 <br> 算法架构： <br> 非递归回溯框架 ``` int a[n],i; 初始化数组a[]; i = 1; while (i>0(有路可走) and (未达到目标)) // 还未回溯到头 { if(i > n){ 搜索到一个解，输出； } else { // 处理第i个元素 a[i]第一个可能的值； while(a[i]在不满足约束条件且在搜索空间内){ a[i]下一个可能的值； } if(a[i]在搜索空间内){ 标识占用的资源； i = i+1; // 扩展下一个结点 } else { 清理所占的状态空间； // 回溯 i = i –1; } } } ``` 递归的算法框架 ``` int a[n]; try(int i) { if(i>n) { 输出结果; } else { for(j = 下界; j <= 上界; j=j+1) { // 枚举i所有可能的路径 if(fun(j)){ // 满足限界函数和约束条件 a[i] = j; ... // 其他操作 try(i+1); 回溯前的清理工作（如a[i]置空值等）; } } } } ```