例2 八皇后问题
八皇后问题用一句话来描述，就是：找到所有在8*8的国际象棋棋盘上放置8枚皇后棋子并且满足任意两枚皇后不会互相攻击的方案。我们先来看一下国际象棋的棋盘：
棋盘是由8×8等于64个方格组成。棋子是放在方格中的，而不是像中国象棋或者围棋那样放在横线和纵线的交叉点上。上图中的棋子就是皇后，如果有其他棋子与皇后在同一行、同一列或者同一对角线（包含两个方向的对角线）上，都会被皇后攻击到。也就是上图中黑点表示出的位置
8皇后的要求是在棋盘上放置8枚皇后，并且互相不能攻击到。因为要求不能攻击到就意味着每一行和每一列都至多有一枚皇后，所以在棋盘上放置8枚皇后已经是皇后数量的上限。下面这张图展示了8皇后问题的一个解：
八皇后是这样一类的问题的典型：我们要解决一个问题，需要若干个步骤。每一个步骤都需要我们从若干个决策或者说是方向中选择一个来执行。一个步骤的选择结果会影响之后的步骤能做哪些决策。经过若干步骤之后，我们会到达一个终结状态。终结状态可能是成功解决了问题，那么我们发现了问题的一个解；也可能是没有解决问题，但是后面无路可走了，那么说明说我们之前做的决策有错误
深度优先搜索可以用来遍历所有选择，找到所有的终结状态，从而找到所有的解。在此基础上，我们就能轻松回答两类问题：(1)一共有多少可行解；(2)哪个是最优解？
具体到8皇后问题。我们第一步要做出的决策就是第一行的皇后放在哪个格子，有8种选择。第一步确定之后，第二步要决策第二行的皇后放在哪个格子，第二步能做的选择会受第一步的限制。第二步确定之后，我们又要做决策，选择第三行皇后的位置……
有可能在某一步时，我们发现这一行所有格子都不能放皇后。这时我们就是到了一个红色的无解或者说是非法、失败的状态。幸运的话我们最终完成了第8步，放置了8枚皇后，这时我们就是找到了一个绿色的合法的解
8皇后问题比较简单，我们就直接上代码了：
#include <iostream>
using namespace std;
int ans = 0;
int a[8];
bool attack(int x0,int y0,int x1,int y1)
{
if(x0 == x1 || y0 == y1)
return true;
if(x0 + y0 == x1 + y1 || x0 - y0 == x1 - y1)
return true;
return false;
}
void dfs(int x)
{
if(x == 8)
{
ans++;
return;
}
for(int i = 0;i < 8;i++)
{
bool ok = true;
for(int j = 0;j < x;j++)
{
if(attack(j,a[j],x,i))
{
ok = false;
break;
}
}
if(ok)
{
a[x] = i;
dfs(x + 1);
}
}
}
int main()
{
dfs(0);
cout << ans << endl;
return 0;
}上面的代码假设8行8列的棋盘是从0开始编号的。ans统计一共有多少组解。数组a[]保存每一行的皇后的位置，具体来讲第i行的皇后在第a[i]列。第5~12行attack函数是判断两个分别位于(x0, y0)和(x1, y1)的皇后是不是能互相攻击到，能攻击到返回true，否则返回false
第13-37行是DFS的过程。参数x表示我们现在要做的决策是第x行(从0开始)的皇后放在哪个位置。对于8皇后来说，顺利放下8个皇后就是找到一个解。所以第11-14行是如果x等于8，也就是第0~7行都放下了皇后，那么就给ans累加1。否则，x还没到8的话，我们就要做决策皇后放在第几列。当然我们用i循环就枚举0-7列，然后判断这一列能不能放下皇后，判断的依据是这个皇后不能攻击到之前的（第0~x-1行的）任一个皇后。j循环就是在判断之前的皇后
第23~26行就是如果能放在第i列，那么我们就令a[x]=i记下来位置，然后递归决策下一行皇后的位置
例3 题目链接：hihoCoder1054
这道题有一个重要的条件：从数字A滑动到数字B时，线段上不能有尚未经过的点。比如如果数字2还没有经过，那么从1直接滑动到3是不可以的
我们需要想一下如何用程序实现这个限制条件。一个比较简单的方法是用一个二维数组f来记录从i滑动到j需要先经过哪个数字。例如f1=2表示从1滑动到3需要先经过2；特别的fi=0表示从i到j没有限制。这个f数组是这样的，其余的f值是0：
f[1][3] = f[3][1] = 2;
f[1][7] = f[7][1] = 4;
f[1][9] = f[9][1] = f[2][8] = f[8][2] = f[4][6] = f[6][4] = f[3][7] = f[7][3] = 5;
f[3][9] = f[9][3] = 6;
f[7][9] = f[9][7] = 8;然后就是深度优先搜索的过程。套用我们之前的模型，我们第一步要决策折线的第一个点是几，第二步要决策第二个点是几，…… 只要我们决策到第4个点之后，并且折线覆盖了全部n条看到的折线段，那么就找到了一个解
DFS的伪代码如下，x表示当前决策的是第几个点，pre代表上一个(第x-1个)点是几
DFS(x,pre)
{
If x > 4 AND 当前折线包含全部n段被看到的折线段
Ans++
For i = 1...9
If !visited[i] && (f[pre][i] == 0 || visited[f[pre][i])
{
Visited[i] = true
DFS(x + 1,i)
visited[i] = false
}
}其中“当前折线包含全部n段被看到的折线段”我们需要单独写一个函数来判断。fpre==0 || visitedf[pre] 这里是在判断从pre滑动到i是不是可行。可行的条件是或者pre到i没有限制，即fpre=0；或者限制的点已经访问过了，即visitedf[pre]
#include <iostream>
using namespace std;
bool saw[10][10],visited[10];
int f[10][10] = {0},a[10],t,n,x,y,ans;
int cover_saw(int num){
int cnt = 0;
for(int i = 2;i <= num;i++)
if(saw[a[i]][a[i - 1]])
cnt++;
return cnt;
}
void dfs(int x,int pre)
{
if(x > 4 && cover_saw(x - 1) >= n)
ans++;
for(int i = 1;i <= 9;i++)
{
if(!visited[i] && (f[pre][i] == 0 || visited[f[pre][i]]))
{
visited[i] = true;
a[x] = i;
dfs(x + 1,i);
visited[i] = false;
}
}
}
int main()
{
f[1][3] = f[3][1] = 2;
f[1][7] = f[7][1] = 4;
f[1][9] = f[9][1] = f[2][8] = f[8][2] = f[4][6] = f[6][4] = f[3][7] = f[7][3] = 5;
f[3][9] = f[9][3] = 6;
f[7][9] = f[9][7] = 8;
cin >> t;
while(t--)
{
cin >> n;
for(int i = 0;i < 10;i++)
{
visited[i] = false;
for(int j = 0;j < 10;j++)
saw[i][j] = false;
}
for(int i = 0;i < n;i++)
{
cin >> x >> y;
saw[x][y] = saw[y][x] = true;
}
ans = 0;
dfs(1,0);
cout << ans << endl;
}
return 0;
}二维数组saw[][]中保存的是小Hi看到哪两个点是直接相连的。比如看到2-3相连，那么saw2和saw3的值就都等于true。f[][]数组是前面提到的用来记录滑动限制条件的数组。visited[]用来记录在深搜过程中哪些数字已经被用掉了，也就是已经是折线一部分了。a[]记录的是折线序列，第一个点是a[1]，第二个点是a[2]， ……以此类推
第5~11行的cover_saw函数就是伪代码中计算是否“当前折线包含全部n段被看到的折线段”的函数。具体来说cover_saw返回的整数是当前折线a[1]-a[2]-a[3]-…-a[num] 包含了几段被看到的折线段。它的计算逻辑也比较直观，就是枚举折线上的每一段a[i-1]-a[i]，看是不是saw[a[i-1]][a[i]]的值是true。值是true表示a[i-1]-a[i]这一段是被看到的折线段
第12~22行是DFS函数，基本和伪代码一致。函数一开始第14行判断是合法的解。只要折线上有至少4个点，并且覆盖全部n条看到的折线段，那么就找到一个解，累加ans
之后第12~26行就是要决策折线上第x个点是哪个数字。从1到9枚举可能的数字i，然后我们要判断这个决策可行：首先i没有用过，其次从pre直接滑动到i是可以的。如果可行那么我们就递归决策下一个数字
