AcWing 843. n-皇后问题
原题链接
中等
作者:
chenjiaqiy
,
2023-11-14 19:39:25
,
所有人可见
,
阅读 45
#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) //一个分支走到头
{
for (int i = 0; i < n; i ++ ) puts(g[i]); //分别输出分支的每一个数
cout << endl;
return; //返回上一层
}
for (int i = 0; i < n; i ++ ) //空位上可选择的数字为 1 ~ n;
{
if(!col[i] && !dg[u + i] && !udg[n - u + i]) //如果数字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; //回溯,取出i
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;
}