N皇后问题-DFS回溯解法

文章目录

搜索经典题目,两年前一直没有想清楚的问题,今天终于想明白了。下面:N皇后问题的DFS回溯解法。

n皇后问题:一个n×n的棋盘,在棋盘上摆n个皇后,满足任意两个皇后不能在同一行、同一列或同一斜线上的方案有多少种?

这道题的解题关键有两点:
1.回溯;
2.判断行列是否重合以及是否存在斜线问题。

原先做这道题的时候我只想着用一个二维数组去模拟整个棋盘,然鹅忽略了一点,这道题本来可以用一维数组进行解决。
举个栗子

1
2
int queue[105];
queue[0]=1;

这样也就表示第0行第一列放上了queen,这列可以把queue置为全局变量,直接把所有值初始化为0。
从第0行开始遍历,每次dfs都进行dfs(s+1),s表示开始遍历的行数,如果放置queen的数量=n-1(从0开始计数),则说明这一种放置方案成立。

关于对角线上的判断,这里只需要判断当前需要放的第i个皇后是否和前面放置的第i-1个皇后形成对角线即可,如下图所示。
这张图完整的解释了queen[n]-queen[i]=n-i是怎么来的。

上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
int vec[maxn];
int n,ans=0;

bool check(int s)
{
for(int i=0; i<s; i++)
{
if(vec[i]==vec[s] || fabs(vec[i]-vec[s])==fabs(s-i))
return false;
}
return true;
}

void dfs(int s)
{
for(int i=0; i<n; i++)
{
vec[s]=i;
if(check(s))// 检查该点是否可以放queen
{
if(s==n-1) ans+=1;// 已经放好8个皇后,答案数+1
else dfs(s+1);// 继续遍历下一行
}
}
}

int main()
{
cin>>n;
dfs(0);
cout<<ans<<endl;
return 0;
}