0%

leetcode 52 N皇后题解

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路:首先考虑暴力求解,从\(n^2\)个位置中选择n个位置,那么将需要枚举\(C_{n*n}^n\)次,当n=8时就是54502232次枚举,如果n更大,那么就炸了。所以要换个思路,考虑每行只能放一个皇后,每列只能放一个皇后,如果把n列皇后所在的行号依次写出,那么就是1-n的一个排列。于是只需要枚举1-n的所有排列,查看每个排列对应得放置方案是否合法,当n=8时,只需要40320次枚举。遍历每两个皇后,判断他们是否在一条对角线上(不在同一行和同一列是显然得),若不是则为一种情况,加入ans中。实现如下:

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
37
38
39
40
class Solution {
public:
int P[10],hashTable[10]={false},m;
vector<vector<string>>ans;
void generateP(int index){
if(index == m+1){
bool flag = true;
for(int i = 1; i<=m;i++){
for(int j=i+1;j<=m;j++){
if(abs(i-j)==abs(P[i]-P[j])){
flag = false;
return ;
}
}
}
vector<string>t;
if(flag){
string r = "";
for(int i=0;i<m;i++)r+=".";
for(int i=0;i<m;i++)t.push_back(r);
for(int i=1;i<=m;i++)t[P[i]-1][i-1]='Q';
ans.push_back(t);
return ;
}
}
for(int x=1;x<=m;x++){
if(hashTable[x]==false){
P[index]=x;
hashTable[x]=true;
generateP(index+1);
hashTable[x]=false;
}
}
}
vector<vector<string>> solveNQueens(int n) {
m=n;
generateP(1);
return ans;
}
};

事实上,通过思考可以发现,当已经放置了一部分皇后之后,可能剩余得皇后无论怎样都不可能合法,此时就没必要往下递归了,直接返回上层即可,这样可以减少很多计算量,例如35141,当放置了前3个皇后,可以发现剩下两个皇后无论怎么放都会产生冲突,就没必要继续递归了。
回溯算法如下:

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
37
38
class Solution {
public:
int P[10],hashTable[10]={false},m;
vector<vector<string>>ans;
void generateP(int index){
vector<string>t;
if(index == m+1){
string r;
for(int i=0;i<m;i++)r+=".";
for(int i=0;i<m;i++)t.push_back(r);
for(int i=1;i<=m;i++)t[P[i]-1][i-1]='Q';
ans.push_back(t);
return ;
}
for(int x=1;x<=m;x++){
if(hashTable[x]==false){
bool flag = true;
for(int pre =1;pre<index;pre++){
if(abs(index-pre)==abs(x-P[pre])){
flag = false;
break;
}
}
if(flag){
P[index]=x;
hashTable[x]=true;
generateP(index+1);
hashTable[x]=false;
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
m=n;
generateP(1);
return ans;
}
};