求解八皇后问题-蒲公英云

求解八皇后问题

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

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

（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;
}