本文最后更新于：2 年前
前言
本题是Eight Queens的衍生题
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
本题将Eight Queens扩展为N Queens
朴素回溯法
我们会优先想到朴素的回溯算法思路，对于N个皇后，我们可以在N * 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include "bits/stdc++.h"
using namespace std;
class Solution {
vector<vector<string>> ans;
int line;
int directions[8][2] = {{0, 1},
{-1, 1},
{-1, 0},
{-1, -1},
{0, -1},
{1, -1},
{1, 0},
{1, 1}};
private:
bool canAttack(vector<string> queen, int i, int j) {
for (int k = 0; k < 8; ++k) {
int ni = i + directions[k][0], nj = j + directions[k][1];
while (ni >= 0 && ni < line && nj >= 0 && nj < line) {
if (queen[ni][nj] == 'Q') return true;
else {
ni += directions[k][0];
nj += directions[k][1];
}
}
}
return false;
}
bool check(vector<string> solve) {
for (int i = 0; i < line; ++i) {
for (int j = 0; j < line; ++j) {
if (solve[i][j] == 'Q') {
if (canAttack(solve, i, j)) return false;
}
}
}
return true;
}
public:
void backTrack(vector<string>& board, int lin) {
if (lin == line) {
if (check(board)) ans.push_back(board);
return;
}
for (int i = 0; i < line; ++i) {
board[lin][i] = 'Q';
backTrack(board, lin + 1);
board[lin][i] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
line = n;
vector<string> board;
for (int i = 0; i < n; ++i) {
string l;
l.append(n, '.');
board.push_back(l);
}
backTrack(board, 0);
return ans;
}
};
|
朴素回溯法可以得到当N < 8时的答案
当N >= 8时，仅仅拿N == 8来说，此方法的计算量会达到8^8^ = 16,777,216 ≈ 10 ^8^
此数据量过大，会导致Time Limit Exceeded
运行结果如下
基于朴素回溯法的优化
在上面的方案中，我们对任意一种摆法都进行了判断，甚至于最明显不可行的方案都进行了判断
这里使用N == 4举例
Q = Queen, B = Board
[Q,B,B,B]
[Q,B,B,B]
[Q,B,B,B]
[Q,B,B,B]
类似于这样明显错误的我们都进行了判断。
基于此的优化方法，便是直接寻找可以放置皇后的地方
我们知道：
皇后可以攻击同一行，同一列，同一主对角线，同一副对角线上的任意一个棋子
我们寻找皇后位置时，可以基于这个思路大大减少计算量(这里定义为“竖列横行”)
由于我们是一行一行放置皇后，对于列，我们只需要一个used数组来判断同一列上是否有皇后
对于主对角线上的元素，任意两个在同一主对角线上的元素相减之差相等
- 举个例子(1, 1), (3, 3)位于同一主对角线上，二者相减之差均为0
对于副对角线上的元素，任意两个在同一副对角线上的元素相加之和相等
- 举个例子(1, 5), (3, 3)位于同一副对角线上，二者相加之和均为6
在回溯方法中，我们可以直接传入一个空棋盘，在上方放置皇后即可，这里利用了C++中字符串可变的性质
运行结果如下
参考代码
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include "bits/stdc++.h"
using namespace std;
class Solution {
vector<vector<string>> ans;
set<int> diag1, diag2;
vector<bool> used;
int line;
public:
void backTrack(vector<string> &board, int lin) {
if (lin == line) {
ans.push_back(board);
return;
}
for (int i = 0; i < line; ++i) {
if (used[i]) continue;
used[i] = true;
int d1 = lin - i, d2 = lin + i;
if (diag1.count(d1) == 1 || diag2.count(d2) == 1) {
used[i] = false;
continue;
}
diag1.insert(d1);
diag2.insert(d2);
board[lin][i] = 'Q';
backTrack(board, lin + 1);
board[lin][i] = '.';
diag2.erase(d2);
diag1.erase(d1);
used[i] = false;
}
}
vector<vector<string>> solveNQueens(int n) {
line = n;
for (int i = 0; i < n; ++i) {
used.push_back(false);
}
vector<string> board;
for (int i = 0; i < n; ++i) {
string l;
l.append(n, '.');
board.push_back(l);
}
backTrack(board, 0);
return ans;
}
};
|
时间复杂度: O(N!)， 其中N为皇后数量
空间复杂度: O(N)，其中 N 是皇后数量。
相关趣题
最后分享一道写这篇题解时联想到的趣题
来自于CodeForces Round #799 (Div 4) Problem - C
题意解读
在棋盘上，我们用**#标注了教皇**可攻击的格子，请根据此，输出教皇所在的位置
思路分析
由于棋盘大小固定为8，我们只需暴力搜索
$$
1 \leq i, j \leq 7
$$
当grid[i][j]的左上，右上，左下，右下均为**#时返回该位置[i, j]**
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t, n;
cin >> t;
for (int i = 0; i < t; ++i) {
vector<string> grid(8);
for (int j = 0; j < 8; ++j) {
cin >> grid[j];
}
for (int j = 1; j < 8; ++j) {
for (int k = 1; k < 8; ++k) {
if (grid[j][k] == '#' && grid[j - 1][k - 1] == '#' && grid[j - 1][k + 1] == '#' && grid[j + 1][k - 1] == '#' && grid[j + 1][k + 1] == '#') {
cout << j + 1 << ' ' << k + 1 << endl;
}
}
}
}
}
|