n皇后问题
#include<iostream>
using namespace std;
constexpr int N = 15;
int col[N], dg[2*N], udg[2*N], path[N];
int n, cnt;
void dfs(int x)
{
if(x > n) // 说明某个遍历已经完毕
{
++cnt;
if(cnt <= 3) // 根据题目的输出条件 只输出前三个
{
for(int i = 1; i <= n; ++i)
cout << path[i] << " ";
cout << endl;
}
return;
}
for(int i = 1; i <= n; ++i) // 遍历列
{
if(col[i] == 0 && dg[x - i + n] == 0 && udg[x + i] == 0) // col表示的列判断, dg表示的是反对角线, udg表示的是对角线判断
{
col[i] = dg[x - i + n] = udg[x + i] = 1; // 标记所在列, 所在对角线和反对角线
path[x] = i; // 存入这层的列数
dfs(x+1);
col[i] = dg[x - i + n] = udg[x + i] = 0; //恢复现场
path[x] = 0;
}
}
return;
}
auto main() -> int
{
cin >> n;
dfs(1);
cout << cnt << endl;
}
这里所用的算法为暴搜
采用dfs
列数的判断简单, 但是对角线写判断条件