难度困难1668
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1
输出：[["Q"]]提示：
1 <= n <= 9
解题思路：回溯
我们之前写过多道回溯的题比如组合、子集、分割、排列等，但是和这道题不太一样的是，我们之前都是在一维的角度去看待这个回溯问题的，比如说组合问题的 [1, 2, 2] 等等，但是这道题很明显是一个二维问题，一个棋盘既有行又有列，这一下子让我们有点不知从何下手，但是其实我们分析一下还是可以发现，我们之前将的回溯的树形结构其实也是一个类似二维的情况，对于本题来说只不过是空间变成了二维而已！
这道题看起来更像是 dfs，但是其实大多数的 dfs 还是用的回溯的方法！所以我们可以用回溯来尝试解决一下！
⾸先来看⼀下皇后们的约束条件：
-
不能同⾏
-
不能同列
-
不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为⼀棵树，下⾯我⽤⼀个3 * 3 的棋牌，将搜索过程抽象为⼀颗树，如图：
可以发现我们以前对于一维空间来说，有一个树枝和树层的概念，其实也可以认为就是一个二维空间，而这道题只是将这个树枝和树层的概念实体化了，我们只需要在这个空间上面继续按回溯三部曲来做，是完全可以的！
那么只要我们⽤皇后们的约束条件，来回溯搜索这颗树，只要搜索到了树的叶⼦节点，说明就找到了皇后们的合理位置了。
- 递归函数参数
- 定义全局变量⼆维数组result来记录最终结果。n是棋盘的⼤⼩，然后⽤ row 来记录当前遍历到棋盘的第⼏层了。board 为当前棋盘的结果集。
- 递归函数终止条件
- 很明显，我们只有到棋盘最下沿也就是叶子节点的时候，我们才能得到这个有效的棋盘！也就是 row == n 的时候！
- 单层搜索逻辑
- 我们只需要判断当前这个棋盘中该位置摆放后，它的行、列、斜线上是否已经存在皇后了，存在的话则直接 continue，不能 break，因为我们还要继续 for 循环判断该行的下一个节点，就像我们组合问题中的下一个树层一样！
- 然后该位置摆放合法的话，则直接将该位置的字符改为 ‘Q’，然后继续递归，最后回溯要将字符改为 ‘.’
另外我们还得做其它的工作就是判断棋盘是否合法：
- 验证棋盘是否合法
- 不能同行
- 不能同列
- 不能同斜线 （45度和135度角）
- 但是在下面代码中可以发现为什么没有在同行进行检查呢？因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用行去重了。
- 除此之外，对于就是在判断列和斜线的时候，我们其实只需要判断到当前行的上方部分即可，因为当前递归的时候，说明还没递归到下一层！
class Solution {
public:
bool isValid(vector<string>& board, int n, int row, int col)
{
// 因为进来这个函数之前，我们还没添加'Q'，所以只需要判断是否出现过一次的'Q'即可判断是否合法！
// 并且其实这里是可以没有判断行合法的，因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
// 判断列是否有其它皇后
for(int i = 0; i < row; ++i)
{
if(board[i][col] == 'Q')
return false;
}
// 判断斜线是否有其它皇后，我们只需要判断斜线的上部分，因为下面的还没递归到！
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
return true;
}
void backtracking(vector<string>& board, int n, int row)
{
// 到达叶子节点也就是棋盘下沿则终止
if(row == n)
{
reslut.push_back(board);
return;
}
for(int i = 0; i < n; ++i)
{
// 不合法直接continue，不能break，因为还得继续for循环
if(!isValid(board, n, row, i))
continue;
board[row][i] = 'Q';
backtracking(board, n, row + 1);
board[row][i] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtracking(board, n, 0);
return reslut;
}
private:
vector<vector<string>> reslut;
};52. N 皇后 II
难度困难415
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1
输出：1提示：
1 <= n <= 9
这道题其实和上面是一模一样的，只是返回值需要变一下，很简单，用一个全局变量计数就行！
class Solution {
public:
bool isValid(vector<string>& board, int n, int row, int col)
{
for(int i = 0; i < row; ++i)
{
if(board[i][col] == 'Q')
return false;
}
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
{
if(board[i][j] == 'Q')
return false;
}
for(int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
{
if(board[i][j] == 'Q')
return false;
}
return true;
}
void backtracking(vector<string>& board, int n, int row)
{
// 到达叶子节点也就是棋盘下沿则终止
if(row == n)
{
count++;
return;
}
for(int i = 0; i < n; ++i)
{
if(!isValid(board, n, row, i))
continue;
board[row][i] = 'Q';
backtracking(board, n, row + 1);
board[row][i] = '.';
}
}
int totalNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtracking(board, n, 0);
return count;
}
private:
int count = 0; // 统计
};