回溯法：在递归构造中，生成和检查的过程可以有机结合起来，从而减少不必要的枚举。把问题分解为若干个步骤求解时，如果当前步骤没有合法选择，则函数将返回上一级的递归调用，该现象称为回溯法。所以递归枚举通常被称为回溯。
8皇后问题：在8*8的棋盘上放置了8个皇后，使得他们互不攻击，每个皇后的攻击范围为同行，同列和同对角线。要求找出共有多少种放法。
分析：最简单的思路是枚举“64个格子的子集”，使得子集中恰有8个格子满足条件。但是枚举64个格子有2^64，显然是个糟糕的模型。第二种思路是“从64个格子中选8个，然后判断是否满足条件“，根据组合数可知这个方案达到10^9数量级，比第一种方案好，但是也不够好。下面用回溯法来解决。用c[x]表示第x行
的皇后的列号，于是问题转变为了8!=40320生成全排列问题。下面给出了回溯法解决8皇后问题的代码：
int c[maxn];
int ans;
void dfs(int curr,int n){ //n皇后问题
if (curr ==n){ ans++;return; }
int i, j;
for (i = 0; i <n; i++){
c[curr] = i; //尝试吧curr行的皇后放在第i列
for (j = 0; j< curr; j++){
//检查是否与已经放置的皇后冲突
if (c[curr]== c[j] || c[curr] - curr == c[j] - j || c[curr] + curr == c[j] + j)break;
}
//j==i说明上述循环没有提前终止，放在i列是合理的
if (j == curr) dfs(curr + 1,n);
}
}
可以继续提高程序效率。用vis[3][]来标记当前皇后所在的列和对角线是否有其他皇后的攻击，测试了一下，时间大约比上面代码快3倍多int vis[3][maxn];
int vis[3][maxn];
void dfs(int curr,int n){
if (curr == n){ ans++; return; }
for (int i = 0; i < n; i++){
if (!vis[0][i] && !vis[1][curr + i] && !vis[2][curr - i + n]){
vis[0][i] = vis[1][curr + i] = vis[2][curr - i + n] = 1; //标记为放
c[curr] = i; //无需打印的话可以不使用数组c
dfs(curr + 1, n);
vis[0][i] = vis[1][curr + i] = vis[2][curr - i + n] = 0; //撤销标记
}
}
}