蓝桥杯备考：DFS问题之八皇后问题
这道题 n*n的棋盘，我们每行摆放一个棋子，我们的剪枝策略就是如果放置某一行的棋子的时候，该棋子列上已经有棋子了或者对角线上已经有棋子的时候，我们就要剪掉他，
怎么判断对角线上有没有存在的元素了呢？我们可以开一个2*N大小的数组，把y-x和y+x的值存起来，代表每条对角线，y-x代表主对角线，但是有可能是负数，所以我们就统一是y-x+n来存储
副对角线用x+y存
代码：
#include <iostream>
#include <vector>
using namespace std;
const int N = 50;
bool col[N],row[N],st1[N],st2[N];
int n;
int cnt;
vector <int> ret;
void dfs(int y)
{
if(y > n)
{
cnt++;
if(cnt <= 3)
{
for(auto e : ret)
{
cout << e << " ";
}
cout << endl;
}
return;
}
for(int x = 1;x<=n;x++)
{
if(col[x] || st1[y-x+n] || st2[x+y])continue;
ret.push_back(x);
col[x] = st2[x+y] = st1[y-x+n] = true;
dfs(y+1);
ret.pop_back();
col[x] = st2[x+y] = st1[y-x+n] = false;
}
}
int main()
{
cin >> n;
dfs(1);
cout << cnt << endl;
}