Backtracking
在程序设计中，有相当一类求一组解、或求全部解或求最优解的问题，例如八皇后问题，不是根据某种确定的计算法则，而时利用试探和回溯的搜索技术求解。
回溯法是设计递归过程的一种重要方法，它的求解过程实质上是一个先序遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的，二是隐含在遍历过程中。
回溯法实质上是一个先序遍历一棵“状态树”的过程
回溯法实质上是一个先序遍历一棵“状态树”的过程
回溯法实质上是一个先序遍历一棵“状态树”的过程
(重复三遍，此话说的太妙了！)
很多问题用回溯和试探求解时，描述求解过程的状态树不是一棵满的多叉树。因为在试探过程中，当处的状态和问题所求解产生矛盾时，不再继续试探下去，这时出现的叶子结点就不是问题的解的终结状态。这类问题的求解过程可看成是在约束条件下进行先序(根)遍历，并在遍历过程中剪去那些不满足条件的分支。
下面举一个4皇后问题的例子(八皇后问题的简化)
求4皇后问题的所有合法布局
上图展示了求解过程中棋盘状态的变化情况。这是一棵四叉树，树上每个结点表示一个局部布局或一个完整布局。
根结点表示棋盘的初始状态：棋盘上无任何棋子。
每个(皇后)棋子都有4个可选择的位置，但在任何时刻，棋盘的合法布局都应该满足3个约束条件(任何两个棋子都不占据棋盘上的同一行、或者同一列、或者同一对角线)。
求所有合法布局的过程(即为在上述约束条件下，先根遍历该状态树的过程)。
下面是遍历中访问结点的操作：
- 判别棋盘上是否已得到一个完整的布局(棋盘上是否已经摆上4颗棋子)，若是，则输出布局；
- 否则依次先根遍历满足约束条件的各棵子树，即首先判断该子树根的布局是否合法，如果合法，则先根遍历该子树，否则减去该子树分支。
下面是伪码算法：
void Trial(int i, int n) {
// 进入本函数时，在n*n棋盘上，前i-1行已经放置了布局合法的i-1个棋子
// 现从第i行开始继续为后续棋子选择合法位置
// 当i>n时，求得一个合法布局，并输出
if(i > n) 输出棋盘当前布局;
else for(j = 1; j <= n; ++j) {
在第i行第j列放置一枚棋子;
if(当前布局合法) Trial(i + 1, n);
移走第i行第j列的棋子;
}
}
上面伪代码可作为回溯算法求解的一般模式，类似问题还有骑士游历、迷宫问题、选最优问题等等。