示例：
输入：4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
分析
N皇后是经典的回溯问题，就是每一步都尝试，每一步都看当前位置是否符合规则，下面我们直接看代码吧。
代码
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
used.resize(n, vector<bool>(n, false));
backtrace(used, 0);
return ret;
}
vector<vector<bool>> used;
vector<vector<string>> ret;
void backtrace(vector<vector<bool>> &used, int row) {
if (row == used.size()) {
PushString(used);
return;
}
int col = used[0].size();
for (int i = 0; i < col; ++i) {
if (IsValid(used, row, i)) {
used[row][i] = true;
backtrace(used, row + 1);
used[row][i] = false;
}
}
}
void PushString(vector<vector<bool>> &used) {
vector<string> vec;
for (auto &v : used) {
string tem;
tem.resize(v.size(), '.');
for (int i = 0; i < v.size(); ++i) {
if (v[i]) tem[i] = 'Q';
}
vec.push_back(tem);
}
ret.push_back(vec);
}
bool IsValid(vector<vector<bool>> &used, int i, int j) {
int row = used.size();
int col = used[0].size();
for (int ii = 0; ii < i; ++ii) {
if (used[ii][j]) return false;
}
for (int jj = 0; jj < j; ++jj) {
if (used[i][jj]) return false;
}
for (int ii = i - 1, jj = j - 1; ii >= 0 && jj >= 0; ii--, jj--) {
if (used[ii][jj]) return false;
}
for (int ii = i - 1, jj = j + 1; ii >= 0 && jj < col; ii--, jj++) {
if (used[ii][jj]) return false;
}
return true;
}
};代码精进之路
代码精进之路，我们一起成长！
