（C语言)八皇后题解——深度优先搜索算法

我大一上听老师提过这道题，最近有幸在在洛谷看到这道题，恰好自己刚学DFS（深度优先搜索算法），尝试做了一下。

题意：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？

这道题应该是深度优先搜索算法（DFS)的典型案例.

所谓DFS，本质上就是通过满足一定条件的深入搜索从而穷举出所有的可能答案。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.。
例如，对于以下的一个无向图，

假设我们要找出从A出发有几条路径可以到达H。这时候就需要从A发起深度优先搜索，先依次访问与A相邻的结点(A->B、A->C、A->D)，然后分别从B、C、D出发（单向）分别访问与其相邻的结点。若出发的某一个点的前方已经没有其他结点或相邻结点不符合要求或找到符合题意的解，则回溯到当前节点的上一个结点，本次搜索结束。

在上图中，在B、C、D的前方各只有一个节点(B->E、C->F、D->G)。因为E前方已没有路径，即不符合要求，则回溯到E的上一个结点B；又因为B没有其他相邻结点，则又回溯到B的上一个结点A（初始出发点）。然后沿A->C路径搜索，发现符合题意，又回溯到A。最后再沿A->D路径搜索……

结合上述描述，不知读者是否发现八皇后问题的（其中一种）解决思路与深度优先搜索算法如出一辙。

题意要求从第一行开始到第八行，逐行放置一个皇后，并且各皇后之间的相对位置符合一定要求（任意两个皇后都不能处于同一行、同一列或同一斜线上）。但问题是第一行有八列，（在不考虑后续情况时）在每一列放置皇后都有可能满足题意。所以我们必须从第一行的第一列开始，穷举出所有可能的情况，并筛选出符合题意的答案。

以下我仅以其中一种情况来叙述主要思路。
刚开始我在第一行第一列放置一个皇后。由题意，此后其主次对角线与该列都不能再放置皇后。

如下图（红色代表禁区，黑色为皇后），

接下来我应该在第二行放置皇后。但因为第二行的一二列不能放置皇后，所以只能从第三列开始放置（在不知道后续情况时，第二行从第三列开始，每一列都有可能满足题意）。于是我在第三列放置皇后。

第二个皇后产生的禁区为橙色。

有人或许会问，为什么不把第三行第三列的红色禁区也标为橙色禁区？这个问题我稍后解答。

如同前面操作，接下来应该在第三行第五列放置皇后（在不知道后续情况时，第三行从第五列开始，每一列都有可能满足题意）。

粉色为新产生的禁区，黑色为皇后。

接下来应该在第四行第七列放置皇后（在不知道后续情况时，第四行的2、7、8列都有可能满足题意）。（这里其实应该先讨论在第二列放置皇后的情况，但因为我写到这里时没注意到第二列，所以就先讨论了第七列）

绿色为新产生的禁区，黑色为皇后。

接下来应该在第五行放置皇后。如图我们不难发现，第五行只有2、4两列可放置皇后。显然我们应该先尝试第2列的情况。

蓝色为新产生的禁区，黑色为皇后。

接下来应该在第六行放置皇后。如图我们不难发现，第6行只有第4列可放置皇后。

紫色为新产生的禁区，黑色为皇后。
接下来应该在第7行放置皇后。如图我们不难发现，第7行只有第6列可放置皇后。
如图不难发现，第8行全为禁区，无法放置皇后（该条路径已走不通），不符题意，所以我们应该回溯到上一步（也就是还未放置第七行皇后时）。

回溯时应该撤销当前皇后产生的禁区

。如下图，

因为第七行也没有其它列（分支）可以放，所以又要回溯到上一步（还未放置第6行皇后时）。如下图，
因为第六行除了第四列也没有其它列（分支）可以放，所以又要回溯到上一步（还未放置第5行皇后时）。因为第5行有第二列和第四列两个分支，而第二列的情况我们已讨论过，所以只需讨论第四列的情况.
蓝色为新产生的禁区。
由上图，显然第六行与第七行无法放置皇后，所以第五行的两条路径都不通，应该回溯到还未放置第4行皇后时。因为第4行有第2、7、8列三个分支，而第七列的情况我们已讨论过，所以就先讨论第2列的情况.
如下图，绿色为新禁区

由上图，显然第五行有第4、8列两个分支，但第六行无法放置皇后，所以第四行第二列这条路径也行不通，又应回溯到还未放置第4行皇后时，尝试该行最后一个分支（第8列）

以后的步骤我不再详细展示，你应该已经了解大致的思路：

1. 在当前行的非禁区位置放置皇后；
2. 显然，新放置的皇后会产生新的禁区，将禁区进行标记；
3. 若当前行已是最后一行，说明本轮搜索已找到可行解，记录该解，本轮搜索结束，撤销本行皇后产生的新禁区，回溯到上一行（即上一个结点），探访该行的其他分支（如果有的话）；
4. 若当前行不是最后一行，则继续探寻下一行的分支（这里的分支指非禁区）。如果下一行没有非禁区，说明此路径不通，本轮搜索结束，撤销本行皇后产生的新禁区，回溯到上一行（即上一个结点），探访该行的其他分支（如果有的话）。

以下是该思路等同的代码：

#include <stdio.h>
#include <stdlib.h>

//此次将标记对角线的方法大大优化
int n=0,sum=0;//n为棋盘的边长,sum为解的个数
int result[14]={0},check[3][28]={0};//check[1]与check[2]用于标记点位正负对角线

int DFS(int row)//row代表第几行
{
    int j;
    if(row==n+1)//到达边界
    {
        sum++;
        if(sum<=3)//输出前三列结果
        {
            for(j=1;j<=n;j++)
            {
                printf("%d ",result[j]);
            }
            printf("\n");
        }
        return 0;//成功返回即找到可行解
    }
    for(j=1;j<=n;j++)//逐列遍历
    {
        if(!check[0][j]&&!check[1][row+j]&&!check[2][row-j+n])//该格可以放置棋子
        {
            result[row]=j;//录入结果
            check[0][j]=1;//标记该皇后所在的列
            check[1][row+j]=1;//标记次对角线
            check[2][row-j+n]=1;//标记主对角线
            //沿该路径深入搜索
            DFS(row+1);//使用递归
            //复位即撤销禁区
            check[0][j]=0;
            check[1][row+j]=0;
            check[2][row-j+n]=0;
        }
    }
    return 1;
}

int main()
{
    scanf("%d",&n);//输入棋盘边长
    DFS(1);//从第一行开始搜索
    printf("%d\n",sum);
    return 0;
}

上述代码也是我在洛谷做此题的AC代码。这里附上该题链接：[USACO1.5]八皇后 Checker Challenge。

代码解释

if(row==n+1)//到达边界
    {
        sum++;
        if(sum<=3)//输出前三列结果
        {
            for(j=1;j<=n;j++)
            {
                printf("%d ",result[j]);
            }
            printf("\n");
        }
        return 0;//成功返回即找到可行解
    }

这一段是边界判断。因为此题的棋盘边长为输入的n，当row(棋盘的行)==n+1,说明从第1行到第n行的皇后放置完毕，且为合法解。于是用于记录合法解总数的sum++。函数返回。

for(j=1;j<=n;j++)//逐列遍历
    {
        if(!check[0][j]&&!check[1][row+j]&&!check[2][row-j+n])//该格可以放置棋子
        {
            result[row]=j;//录入结果
            check[0][j]=1;//标记该皇后所在的列
            check[1][row+j]=1;//标记次对角线
            check[2][row-j+n]=1;//标记主对角线
            //沿该路径深入搜索
            DFS(row+1);//使用递归
            //复位即撤销禁区
            check[0][j]=0;
            check[1][row+j]=0;
            check[2][row-j+n]=0;
        }
    }

这一段是对逐条路径深入搜索。
!check[0][j]说明当前列没有放置过皇后，!check[1][row+j]说明当前棋格的次对角线没有皇后，!check[2][row-j+n]说明当前棋格的主对角线没有皇后。三者同时满足则当前行的当前列可放置皇后。

我再解释一下之前的那个问题

题意已经告诉我们，当我们在某一行放置皇后时，是不能与已放置的皇后产生位置冲突。假设把第三行第三列也标记为橙色

若在第二行第三列的皇后最终导致不符合题意，按照回溯原则，此时应将二行三列的皇后与其产生的橙色禁区撤销
(3,3)已为非禁区
然后探访第二行的其他分支（4、5、6、7、8）。当选择在二行五列放置皇后时，
因为第三行第三列棋格已成为非禁区，显然当我在这里放置皇后后，该皇后与第一行的皇后在同一对角线上，违背题意。（如下图）

事实上，不妨这样理解，因为当我们在某一行放置皇后时，是不能与已放置的皇后产生位置冲突，所以先放置的皇后的优先级高于后放置的皇后的优先级，因此后放置的皇后是没有“权力”改动先放置皇后的禁区的。

不当之处，敬请斧正……