按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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] 等等，但是这道题很明显是一个二维问题，一个棋盘既有行又有列，这一下子让我们有点不知从何下手，但是其实我们分析一下还是可以发现，我们之前将的回溯的树形结构其实也是一个类似二维的情况，对于本题来说只不过是空间变成了二维而已！
首先来看⼀下皇后们的约束条件：
- 不能同行
- 不能同列
- 不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树，下面用一个 3*3 的棋牌，将搜索过程抽象为一颗树，如图：
可以发现只要我们用皇后们的约束条件，来回溯搜索这颗树，期间发现不满足要求的就可以直接剪枝跳过，而一旦搜索到了树的叶子节点，说明就找到了皇后们的合理位置了，就将其加入结果集！
- 函数头的设计：
- 还是一样，定义一个全局变量二维数组
ret来记录最终结果。然后用n表示棋盘的宽和高，用row来记录当前遍历到棋盘的第几层了，还有一个一维字符串数组也就相当于一个二维数组board作为当前棋盘。
- 还是一样，定义一个全局变量二维数组
- 递归函数出口：
- 很可以看出，只有到棋盘最下沿也就是叶子节点的时候，我们才能得到这个有效的棋盘，也就是
row == n的时候，进行结果集的添加以及返回！
- 很可以看出，只有到棋盘最下沿也就是叶子节点的时候，我们才能得到这个有效的棋盘，也就是
- 函数体的内容：
- 首先需要判断当前这个棋盘中该位置摆放后，它的行、列、斜线上是否已经存在皇后了，存在的话则直接
continue跳过该位置。 - 然后该位置如果摆放是合法的话，则直接将该位置的字符改为
Q，然后继续递归，最后回溯要将字符改为.即可。
- 首先需要判断当前这个棋盘中该位置摆放后，它的行、列、斜线上是否已经存在皇后了，存在的话则直接
另外我们还得做其它的工作就是判断棋盘是否合法：
- 不能同行
- 不能同列
- 不能同斜线 （
45度和135度角）
但其实我们并不需要进行同行的判断，因为在单层搜索的过程中，每一层递归，只会选 for 循环（也就是同一行）里的一个元素，所以不用行去重了。除此之外，对于就是在判断列和斜线的时候，我们其实只需要判断到当前行的上方部分即可，因为当前递归的时候，说明还没递归到下一层！
class Solution {
private:
vector<vector<string>> ret; // 存放结果集
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.')); // 进行棋盘初始化
dfs(board, n, 0);
return ret;
}
void dfs(vector<string>& board, int n, int row)
{
// 递归函数出口
if(row >= n)
{
ret.push_back(board);
return;
}
for(int col = 0; i < col; ++i)
{
// 先判断当前下棋位置是否符合要求，不符合直接跳过，相当于剪枝
if(validate(board, n, row, col) == false)
continue;
// 回溯三部曲
board[row][col] = 'Q';
dfs(board, n, row + 1);
board[row][col] = '.';
}
}
// 检查当前位置是否符合规则（不需要检查行，因为上面的dfs迭代已经进行了回溯操作）
bool validate(vector<string>& board, int n, int x, int y)
{
// 检查列
for(int i = 0; i < x; ++i)
if(board[i][y] == 'Q')
return false;
// 检查斜线
for(int i = x - 1, j = y - 1; i >= 0 && j >= 0; --i, --j)
if(board[i][j] == 'Q')
return false;
for(int i = x - 1, j = y + 1; i >= 0 && j < n; --i, ++j)
if(board[i][j] == 'Q')
return false;
return true;
}
};剪枝的优化
其实对于剪枝操作，我们是可以进行优化的，上面我们的剪枝操作，其实是直接遍历棋盘中对应的列、斜线上是否有出现过棋子，但其实可以不用每次都去遍历这些位置，而是通过布尔值类型的数组，记录下当前斜线、列是否出现过棋子，出现过的话就直接跳过即可，这个判断速度是很快的，就是 O(1) 级别的，就是哈希的思想，用空间换时间！
对于列的判断其实还好说，就是个简单的一维数组 col_used，其中 col_used[i] 为 true 就表示第 i 列已经存在元素了，则此时直接跳过即可，要做到这个设置并不难，因为我们下棋是往下走的，所以往下走的时候就可以顺便进行 col_used[i] 的设置了！
但是对于斜线上来判断是否存在就不好搞了，这里就要借用我们学过的一次函数，一次函数中斜率为 -1 和 1 的时候，其实就可以对应为矩阵中的主对角线和副对角线，如下图所示：
对于副对角线来说，因为 y = x + b，可以得到 y - x = b，所以截距其实就是一个定值，根据这个定制，我们就能固定一条对角线上无论 y 和 x 怎么变化都能找出固定的截距，也就是一个参照值，用来记录当前对角线是否存在棋子！
但是副对角线的下三角部分的截距小于零了，会造成数组越界，所以我们统一让等式两边都加上棋盘的宽度，最后得到 y - x + n = b + n。
也就是说我们只需要判断副对角线数组 minor_diag[y - x + n] 是否为 true，为 true 表示存在元素，然后别忘了这个对角线数组因为加了 n，所以在开辟的时候大小是 2*n。
对于主对角线也是如此，不过因为主对角线最小截距为一，所以不需要关心越界问题，但是因为其等式为 y = -x + b，得到 y + x = b，那么我们判断的依据就是判断主对角线数组 main_diag[y + x] 是否为 true，是的话则直接跳过，但是此时如果 x 或者 y 大于 n 的话也是会越界，所以同样也需要让主对角线数组 main_diag 在开辟的时候大小是 2*n！
class Solution {
private:
vector<vector<string>> ret; // 存放结果集
bool col_used[10]; // 表示列是否有棋子
bool main_diag[20]; // 表示主对角线是否有棋子
bool minor_diag[20]; // 表示次对角线是否有棋子
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.')); // 进行棋盘初始化
dfs(board, n, 0);
return ret;
}
void dfs(vector<string>& board, int n, int row)
{
// 递归函数出口
if(row >= n)
{
ret.push_back(board);
return;
}
for(int col = 0; col < n; ++col)
{
// 进行剪枝处理，判断是否位置有效
if(col_used[col] == true ||
main_diag[row + col] == true ||
minor_diag[row - col + n] == true)
continue;
// 回溯三部曲
board[row][col] = 'Q';
col_used[col] = main_diag[row + col] = minor_diag[row - col + n] = true;
dfs(board, n, row + 1);
col_used[col] = main_diag[row + col] = minor_diag[row - col + n] = false;
board[row][col] = '.';
}
}
};