Backtracking (Depth First Search)
Table of Contents
1. 回溯法
回溯法（Backtracking）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯算法本质上是一种“穷举法”，很容易想到，没有什么先进思想在里面（《算法导论》一书中没有对其的介绍）。不过， 由于回溯法在搜索过程中不断略过某些显然不合适的情况（称为剪枝），所以搜索的空间大大小于一般的穷举法。 回溯法的缺点：一般来说回溯法的复杂度比较高，当问题规模非常大时，不宜采用回溯法。
当回溯法用于树型结构的问题时，又可称为深度优先搜索(Depth first search)。
回溯法一般采用的是递归实现。回溯法也可以采用迭代实现，可参考《计算机算法设计与分析(第 3 版, 王晓东编)》，第 5 章
2. 回溯法实例：N 皇后问题
问题描述：在一个 \(N \times N\) 的国际象棋棋盘上放置 \(N\) 个皇后，且任何 2 个皇后不能放在同一行或同一列或同一斜行上。问有多少种放法？并输出所有的正确放法。
2.1. 问题分析
分析：这个问题可通过一个一个尝试来解决。
如何测试皇后会受到攻击？设两个皇后位置为(i,j)、(m,n)，则有：
“i != m”，可表示不在同一行；
“j != n”，可表示不在同一列；
“|i + j| != |m + n|”，可表示不在斜率为 1 的斜线上；
“|i - j| != |m - n|”，可表示不在斜率为-1 的斜线上。
如何表示皇后？用二维数组显然可以，使用一维数组更好，把皇后位置存储为一个 n 维数组 a[n]， 数组中第 i 个元素的值代表第 i 行的皇后的列的位置 ，这样便可以把问题的空间规模进行压缩。
2.2. 编程实现
下面是 N 皇后问题的一个解法。
// 该程序是一个解N皇后问题的算法（采用递归解决）
#include <stdio.h>
#define N 8 //这里是解决8皇后问题
int solution[N]; //其中solution[i]表示第i行的皇后所在的列值，仅保存最近一次尝试的方案
int solution_count; //记录正确放置方案的总数
/* 测试第row行皇后的放置是否成功，前面的行（0到row-1行）已经放置好了皇后 */
bool is_valid(int row) {
for (int i = 0; i < row; i++) { // i代表行，测试第row行的皇后和前面已经放好的row-1行是否会攻击
if (solution[row] == solution[i]) { // 在同一列上
return false;
}
if (row-solution[row] == i-solution[i]) { // 在\方向斜线上
return false;
}
if (row+solution[row] == i+solution[i]) { // 在/方向斜线上
return false;
}
}
return true;
}
/* 前面的 row-1 行都已放置好了，开始放第 row 行 */
void backtrack(int row) {
int k;
if (row > N-1) { //终止条件，意味着找到了一个可行解。测试条件也可为row==N
solution_count++;
/* 找到解后，循环打印八皇后棋局（下标转换成从1开始） */
for(k=0 ; k<N ; k++) printf("(%d,%d) ",k+1, solution[k]+1);
printf("\n");
} else {
for(int i=0 ; i<N ; i++ ) { //对第row行的皇后进行每一列进行放置尝试。
solution[row] = i; //放置第row行的皇后，即把其列其设为i。
if(is_valid(row)) { //测试放置的第row行皇后会不会有攻击。
backtrack(row + 1); //继续放置下一行的皇后。
} //省略的else分支，是“剪枝”步骤。
}
}
}
void queens() {
backtrack(0); //从第一行（数组下标为0）开始尝试放置皇后
}
int main(void) {
queens();
printf("Total Solutions: %d\n", solution_count);
return 0;
}
用上面程序解决 4 皇后问题（把 N 设置为 4），可得到下面的输出：
(1,2) (2,4) (3,1) (4,3) (1,3) (2,1) (3,4) (4,2) Total Solutions: 2