n-皇后问题

n−皇后问题是指将 n 个皇后放在 n×n的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n,请你输出所有的满足条件的棋子摆法。

输入格式

共一行,包含整数 n。

输出格式

每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例:

4

输出样例:

.Q..
…Q
Q…
..Q.

..Q.
Q…
…Q
.Q..

#include<iostream>
using namespace std;
const int N=13*2;
char g[N][N];
int col[N],dg[N],udg[N];
int n;
void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                cout<<g[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    
    for(int i=1;i<=n;++i)
    {
        if(!col[i]&&!dg[i+u]&&!udg[i-u+n])
        {
            col[i]=1,dg[i+u]=1,udg[i-u+n]=1;
            g[u][i]='Q';
            dfs(u+1);
            col[i]=0,dg[i+u]=0,udg[i-u+n]=0;
            g[u][i]='.';
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            g[i][j]='.';
    dfs(1);
    return 0;
}