搜索（3）

例 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 是可以的。如果可行那么我们就递归决策下一个数字