原题链接
一. 题目描述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
二. 解题思路
本题意思也是十分简单，在一块二维数组中进行分布，要求在一点分布了Q之后，该点所在行，列以及对角就不能再出现Q，你需要输出所有在棋盘上的合法分布。
这个题目看起来比较简单，但是做起来还是有些费劲的，你得遍历枚举所有的可能，然后再每一个点上判断加入Q中是否合法，一听头都大了，不要慌！！我们来用回溯给它秒了！
1. 确定递归参数：首先需要一个chessboard 的一维字符串数组用来存储路径中的值，其次需要一个n 用来记录棋盘的大小，再有就是一个row 记录行数。
2. 确定递归的结束条件：当row == n 的时候就说明已经遍历到最后一行了，可以收集结果并且return了。
3. 单层循环递归：首先得确定在第row 行第 i 列放置皇后(Q) 是合法的(有一个isValid 函数专门判断是否合法)，如果不合法，进行下一次的循环，如果合法，就将该位置放置皇后，然后进行递归处理，等到递归返回之后回溯即可。
4. 判断是否合法函数(isValid)：我们只需要确定该点所在的列和对角上不存在皇后即可，这个函数书写比较简单，具体大家可以看下面的代码。
下图是代码随想录中对具体回溯的一个举例，大家可以参考：
话不多说！！！上代码！！
三. 代码
class Solution {
public:vector<vector<string>> res;bool isValid(vector<string>& chessboard, int n, int col, int row){// 检查列for(int i = 0; i < row; i++){ // 只需要检查 0~row 列有没有Q即可if(chessboard[i][col] == 'Q'){return false;}}// 检查45度for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){if(chessboard[i][j] == 'Q'){return false;}}// 检查135度for(int i = row - 1, j = col + 1; i >= 0 && j<= n; i--, j++){if(chessboard[i][j] == 'Q'){return false;}}return true;}void back(vector<string>& chessboard, int n, int row){if(n == row){res.push_back(chessboard);return;}for(int i = 0; i < n; i++){if(isValid(chessboard, n, i, row)){chessboard[row][i] = 'Q';back(chessboard, n, row + 1);chessboard[row][i] = '.';}}}vector<vector<string>> solveNQueens(int n) {res.clear();vector<string> chessboard(n, string(n, '.'));back(chessboard, n, 0);return res;}
};四. 总结
本题相对于比较难理解一些，建议大家先将我之前发布的几篇回溯文章能够独立完成，这样大家只要能够细心并且静下心来思考就一定能够明白这道题，加油！！！
时间复杂度：O(n!)；
空间复杂度：O(n)。
