Difficulty: 困难
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
1
2
3
| 输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
|
示例 2：
提示：
1 <= n <= 9- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
Solution
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
| class Solution {
public:
int n;
static const int N = 9;
bool col[N] = {}, dg[2*N] = {}, udg[2*N] = {};
vector<vector<string>> res;
vector<string> path;
vector<vector<string>> solveNQueens(int _n) {
n = _n;
path = vector<string> (n, string (n, '.'));
dfs(0);
return res;
}
void dfs(int u) {
if (u == n) {
res.push_back(path);
}
for (int i = 0; i < n; ++i) {
if (!col[i] && !dg[i - u + N] && !udg[i + u]) {
path[u][i] = 'Q';
col[i] = dg[i - u + N] = udg[i + u] = true;
dfs(u + 1);
col[i] = dg[i - u + N] = udg[i + u] = false;
path[u][i] = '.';
}
}
}
};
|
Difficulty: 困难
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
1
2
3
| 输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
|
示例 2：
提示：
1 <= n <= 9- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int n;
static const int N = 9;
bool col[N] = {}, dg[2 * N] = {}, udg[2 * N] = {};
int res;
int totalNQueens(int _n) {
n = _n;
return dfs(0);
}
int dfs(int u) {
if (u == n) return 1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!col[i] && !dg[i - u + N] && !udg[i + u]) {
col[i] = dg[i - u + N] = udg[i + u] = true;
cnt += dfs(u + 1);
col[i] = dg[i - u + N] = udg[i + u] = false;
}
}
return cnt;
}
};
|
