题面
题解
首先不考虑斜向，根据全排列的性质，1 ~ n 的全排列，以序数为行号，数值为列号就能穷举出不斜向攻击下的 N 皇后摆放情况。所以我们只需要穷举全排列，然后判断每个排列是否可行，复杂度为
代码
51:
// https://leetcode-cn.com/problems/n-queens/
const int maxn = 15;
class Solution {
public:
bool chosen[maxn];
int res[maxn];
vector<vector<string>> ans;
string get_string(int pos, int n) {
string s = "";
for (int i = 1; i < pos; i ++)
s += ".";
s += "Q";
for (int i = pos + 1; i <= n; i ++)
s += ".";
return s;
}
void next_permutation(int x, int n) {
if (x == n + 1) {
// judge
for (int i = 1; i < n; i ++)
for (int j = i + 1; j <= n; j ++)
if (res[i] + j - i == res[j] || res[i] + i - j == res[j])
return;
// output
vector<string> ret = vector<string>();
for (int i = 1; i <= n; i ++)
ret.push_back(get_string(res[i], n));
ans.push_back(ret);
}
for (int i = 1; i <= n; i ++) {
if (chosen[i]) continue;
chosen[i] = true;
res[x] = i;
next_permutation(x + 1, n);
chosen[i] = false;
}
}
vector<vector<string>> solveNQueens(int n) {
next_permutation(1, n);
return ans;
}
};C
52:
// https://leetcode-cn.com/problems/n-queens-ii/
const int maxn = 15;
class Solution {
public:
bool chosen[maxn];
int res[maxn];
int ans = 0;
void next_permutation(int x, int n) {
if (x == n + 1) {
// judge
for (int i = 1; i < n; i ++)
for (int j = i + 1; j <= n; j ++)
if (res[i] + j - i == res[j] || res[i] + i - j == res[j])
return;
ans ++;
}
for (int i = 1; i <= n; i ++) {
if (chosen[i]) continue;
chosen[i] = true;
res[x] = i;
next_permutation(x + 1, n);
chosen[i] = false;
}
}
int totalNQueens(int n) {
next_permutation(1, n);
return ans;
}
};C
