按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
题解
这题先按思路敲，不要忙着写细节（比如isValid），写个注释放在函数里面就行，先把大体框架写完，思路捋清楚，再回头去写细节。
首先，可以把初始地图cur全初始化为.，后面单独修改需要的位置为Q。
递归函数每次传入当前行row，函数目的是寻找当前行row中哪一列的位置可以作为合法放置的位置。所以在函数中，遍历列col从0到n，面对当前位置cur[row][col]，需要做以下操作：
- 检查
cur[row][col]是否合法。编写判断函数isvalid，因为每次都是合法才在此位置放置皇后，所以只需要判断到当前位置而不是整个地图。针对row,col分别判断三个条件：- 判断行，行只需要判断
0到row - 判断列 ，同样
0到col - 斜线，分为 左上方 和 右上方
- 判断行，行只需要判断
- 如果合法，将此位置字符设置为
Q，放置皇后，然后row+1进入下次递归，出此递归之后，恢复字符串为.，撤销当前位置的选择。
当row=n时，表明已经完成了对每一行的搜寻，将当前地图cur加入结果中。
查看代码
class Solution {
public:
vector<vector<string>> res;
vector<string> cur;//当前图
bool isValid(int& row,int& col,int &n){
//判定在row,col位置放置皇后是否合法,每次都是合法才加，所以只需要针对row,col分别判断三个条件
//1.判断行
for(int i=0;i<row;++i){
if(cur[i][col]=='Q')
return false;
}
//2.判断列
for(int i=0;i<col;++i){
if(cur[row][i]=='Q')
return false;
}
//3.斜线
//3.1左上方
int i=row;
int j=col;
while(i>=0&&j>=0){
if(cur[i][j]=='Q')
return false;
--i;
--j;
}
//3.2右上方
i=row;
j=col;
while(i>=0&&j<n){
if(cur[i][j]=='Q')
return false;
--i;
++j;
}
return true;
}
//每次传入row即可
void work(int& n,int row){
if(row==n){//到最后一行了，结束
//生成地图
res.emplace_back(cur);
return;
}
//只需要遍历当前行所有的列，寻找可用位置
for(int col=0;col<n;++col){
if(!isValid(row,col,n)){//这个位置不可以选择
continue;
}
//选择col,生成当前行 （一开始打算每次生成当前行，后面发现不需要这么麻烦，全初始化再改一个点比较好）
// string line="";
// for(int i=0;i<n;i++){
// line+=(i==col)?"Q":".";
// }
cur[row][col]='Q';
// cur.emplace_back(line);
work(n,row+1);
// cur.pop_back();
cur[row][col]='.';
}
}
vector<vector<string>> solveNQueens(int n) {
//当前图默认全.
for(int i=0;i<n;++i){
string line="";
for(int j=0;j<n;++j){
line+=".";
}
cur.emplace_back(line);
}
work(n,0);
return res;
}
};