求解八皇后问题

Love The Way You Lie 2023-09-24 14:27 57阅读 0赞

[八皇后问题][Link 1]，是回溯算法的典型案例。

![aa79c8d2efcb4470bf497ee70fec8521.png][]

相比对于大家来说八皇后问题已经知道他的基本要求了，这里再给大家详细阐述一下

（1）列：规定每一列放一个皇后，不会造成列上的冲突；

（2）行：规定每一行放一个皇后，不会造成行上的冲突；

（3）对角线：对角线有两个方向，正对角线和反对角线，每一条正对角线和反对角线只能放一个皇后，不会造成冲突；  
这里主要用的是深度优先搜索

深度优先算法：

深度优先搜索算法 （英语： Depth-First-Search ， DFS ）是一种用于遍历或搜索 树 或 图 的 算法 。. 这个算法会尽可能深的搜索树的分支。. 当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。. 这一过程一直进行到已发现从源节点可达的所有节点为止。. 如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，这种算法不会根据图的结构等信息调整执行策略

基于深度优先搜索，对于八皇后问题，主要代码思想为

当这一列，对应对角线上与反对角线上都没有皇后，则可以在这个位置放皇后

随后标记这一列，对角线，反对角线，表示下一次搜索时不应在这一列，对角线，反对角线放皇后

当问题有解后，则需要恢复原状，重新进行搜索

for(int i=0;i<n;i++){
            if(!col[i] && !dg[u+i] && !udg[n-u+i]){
                g[u][i]='Q';
                col[i]=dg[u+i]=udg[n-u+i]=true;
                dfs(u+1);
                col[i]=dg[u+i]=udg[n-u+i]=false;
                g[u][i]='.';
            }
        }

完整代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N=20;
    int n,t;
    char g[N][N];
    bool col[N],dg[N],udg[N];//分别为列，正对角线，反对角线
    void dfs(int u){
        if(u==n){//如果递归到最后一层，也就代表有一个可行性方案，进行输出
            for(int i=0;i<n;i++) cout<<g[i]<<endl;
            puts("");
            t++;
            return;
        }
        for(int i=0;i<n;i++){
            if(!col[i] && !dg[u+i] && !udg[n-u+i]){当这一列，对应对角线上与反对角线上都没有皇后
                g[u][i]='Q';//则可以在这个位置放皇后，皇后用Q来表示
                col[i]=dg[u+i]=udg[n-u+i]=true;
                dfs(u+1);//递归到下一层
                //搜寻完一个解后，就要会恢复现场，进行下一次寻找
                col[i]=dg[u+i]=udg[n-u+i]=false;//恢复现场
                g[u][i]='.';//其余地方用.来表示
            }
        }
    }
    int main(){
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                g[i][j]='.';
            }
        }
        dfs(0);
        cout<<t;//输出总共有几个解
        return 0;
    }

这里的代码是不用关心行上的冲突的，因为row在加1；

这里关于精准找到对角线和反对角线上的点有一个小技巧：上面写到对(i+j)、(i-j)的位置标记为占领状态，对于数组下标来说，肯定都是正的，i-j有可能时负的，所以要加一个偏移量n，这样就不会有负数的存在了。

[Link 1]: https://so.csdn.net/so/search?q=%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98&spm=1001.2101.3001.7020
[aa79c8d2efcb4470bf497ee70fec8521.png]: https://img-blog.csdnimg.cn/aa79c8d2efcb4470bf497ee70fec8521.png