AcWing | 【DFS】n-皇后问题

男娘i 2022-12-20 11:23 142阅读 0赞

**题目内容：**

> n-皇后问题是指将 n 个皇后放在 n∗n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输出所有的满足条件的棋子摆法。

![在这里插入图片描述][20201112080042796.png_pic_center]  
**输入格式**

> 共一行，包含整数n。

**输出格式**

> 每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。
> 
> 其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。
> 
> 每个方案输出完成后，输出一个空行。
> 
> 输出方案的顺序任意，只要不重复且没有遗漏即可。

**数据范围**

> 1≤n≤9

**输入样例：**

**输出样例：**

.Q..
    ...Q
    Q...
    ..Q.
    
    ..Q.
    Q...
    ...Q
    .Q..

--------------------

**思路**

*  按全排列的思路，注意要剪枝

#include<iostream>
    using namespace std;
    const int N=20;
    int n;
    char g[N][N];//用来存路径
    bool row[N],col[N],dg[N],udg[N];//行数以及对角线
    void dfs(int x,int y,int s){ 
        if(y==n)y=0,x++;//每行搜到最后一个数就接到下一行
        if(x==n){ //枚举到最后一行了
            if(s==n){ //如果皇后的个数等于n，说明找到了一组解
                for(int i=0;i<n;i++)puts(g[i]);
                puts("");
            }
            return;
        }
        //枚举当前格子的两种选择
        //不放皇后 直接往后走
        dfs(x,y+1,s);
    
        //放皇后
        if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){ //横竖两条对角线都没有被占
            g[x][y]='Q';
            row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
            dfs(x,y+1,s+1);
            row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;
            g[x][y]='.';
        }
    }
    int main(){ 
        cin>>n;
        for(int i=0;i<n;i++){ 
            for(int j=0;j<n;j++){ 
                g[i][j]='.';//初始化
            }
        }
        dfs(0,0,0);
        return 0;
    }

*  已经分析出来每行只可能存在一个皇后

#include<iostream>
    using namespace std;
    const int N=20;
    int n;
    char g[N][N];//用来存路径
    bool col[N],dg[N],udg[N];//行数以及对角线
    void dfs(int u){ 
        if(u==n){ //如果已经全部遍历完了 就直接输出路径即可，u相当于树的层数
            for(int i=0;i<n;i++)puts(g[i]);
            puts(" ");
            return;
        }
        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]='.';
            }
        }
    }
    int main(){ 
        cin>>n;
        for(int i=0;i<n;i++){ 
            for(int j=0;j<n;j++){ 
                g[i][j]='.';//初始化
            }
        }
        dfs(0);
        return 0;
    }

[20201112080042796.png_pic_center]: /images/20221120/628a78c3b68c4ee79267f70d0ad22b5b.png