Leetcode 51 - N皇后
# 1. 题目
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入:4
输出:[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
解释:4 皇后问题存在两个不同的解法。
提示:皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
# 2. 思路
# 3. 代码
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
board_ = vector<string>(n, string(n,'.'));
col_used_ = vector<bool>(n, false);
diag1_ = vector<bool>(2*n -1, false);
diag2_ = vector<bool>(2*n -1, false);
dfsSearch(n, 0);
return res_;
}
private:
vector<vector<string>> res_;
vector<string> board_;
// false为可以用,true为已占用
vector<bool> col_used_;
vector<bool> diag1_;
vector<bool> diag2_;
bool isAvailable(int x, int y, int n){
return !col_used_[y] && !diag1_[x + y] && !diag2_[x - y + n - 1];
}
void putQueen(bool is_put, int x, int y, int n){
board_[x][y] = is_put ? 'Q' : '.';
col_used_[y] = is_put;
diag1_[x+y] = is_put;
diag2_[x-y+n-1] = is_put;
}
void dfsSearch(int n , int raw_num){
if(raw_num == n){
res_.push_back(board_);
return;
}
for(int i = 0; i<n; ++i){
if(isAvailable(raw_num, i, n)){
putQueen(true, raw_num, i, n);
dfsSearch(n, raw_num+1);
putQueen(false, raw_num, i, n);
}
}
}
};
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
41
42
43
44
45
46
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
41
42
43
44
45
46
提交结果:
// Author: Huahua
// Runtime: 3 ms
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
sols_.clear();
board_ = vector<string>(n, string(n, '.'));
cols_ = vector<int>(n, 0);
diag1_ = vector<int>(2 * n - 1, 0);
diag2_ = vector<int>(2 * n - 1, 0);
nqueens(n, 0);
return sols_;
}
private:
vector<string> board_;
vector<int> cols_;
vector<int> diag1_;
vector<int> diag2_;
vector<vector<string>> sols_;
bool available(int x, int y, int n) {
return !cols_[x]
&& !diag1_[x + y]
&& !diag2_[x - y + n - 1];
}
void updateBoard(int x, int y, int n, bool is_put) {
cols_[x] = is_put;
diag1_[x + y] = is_put;
diag2_[x - y + n - 1] = is_put;
board_[y][x] = is_put ? 'Q' : '.';
}
// Try to put the queen on y-th row
void nqueens(const int n, const int y) {
if (y == n) {
// found one solution, add to the ans set
sols_.push_back(board_);
return;
}
// Try every column
for (int x = 0; x < n; ++x) {
if (!available(x, y, n)) continue;
updateBoard(x, y, n, true);
nqueens(n, y + 1);
updateBoard(x, y, n, false);
}
}
};
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
41
42
43
44
45
46
47
48
49
50
51
52
53
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
41
42
43
44
45
46
47
48
49
50
51
52
53
# 其他
编辑 (opens new window)
上次更新: 2023/03/02, 12:43:17