题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
Example 1:
输入：n = 4 输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[”..Q.”,”Q…”,”…Q”,”.Q..”]] 解释：如上图所示，4 皇后问题存在两个不同的解法
Example 2:
输入：n = 1 输出：[[“Q”]]
Constraints:
- 1 <= n <= 9
- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
解题思路
- 回溯思路
- 使用列，左，右斜对角线来表示是否有值
- 相应的模版：
backtrack(当前进度): if 当前进度 == 最终进度： 结果集.加入(进度状态） else: for 下一节点 in 当前进度下可以到达的节点: if 节点 满足 限制状态： 修改进度状态为下一节点 修改限制状态为下一节点 backtrack(下一节点) 修改限制状态回当前进度 修改进度状态回当前进度 //最后这两行改回就是所谓的“回溯”
C++代码
class Solution {
int n;
vector<string> board;
vector<bool> col, ldig, rdig;
vector<vector<string>> res;
public:
vector<vector<string>> solveNQueens(int n) {
this -> n = n;
string temp = "";
for(int i = 0; i < n; i++){
temp += ".";
}
board = vector<string>(n, temp);
col = vector<bool>(n ,false);
ldig = vector<bool>(2 * n - 1, false);
rdig = vector<bool>(2 * n - 1, false);
backtrack(0);
return res;
}
void backtrack(int i){
if(i == n){
res.push_back(board);
}else{
for(int j = 0; j < n; j++){
if(!col[j] && !ldig[n - 1 - i + j] && !rdig[2 * n - 2 - i - j]){
board[i][j] = 'Q';
col[j] = true;
ldig[n - 1 - i + j] = true;
rdig[2 * n - 2 - i - j] = true;
backtrack(i + 1);
col[j] = false;
ldig[n - 1 - i + j] = false;
rdig[2 * n - 2 - i - j] = false;
board[i][j] = '.';
}
}
}
}
};
