n皇后问题是应用回溯法的经典问题。任一行、列、对角线不能有两皇后并存，因此在判断是否合法时，可以将某一行是否有皇后、某一列是否有皇后分别用数组存起来。注意到，对于往左下右上的对角线，每个点的行号(i)和列号(j)的和相等且与别的对角线不同，因此可用数组将此对角线是否有皇后，即i+j是否为1记录下来,n*n的棋盘有2*n-1条左下到右上的对角线；对于从左上到右下的对角线也类似，每个点的行号(i)和列号(j)的差相等且与别的对角线不同，但是差值可能会出现负值，所以将差值加上n-1，便于用数组记录。
解决判断是否合法的问题后，就要考虑怎么用回溯法求解了。我的思路是在探测第i行后，如果找到一个可以放置皇后的位置j后，则会递归探测下一行，结束后则会继续探测i行j+1列，故可以找到所有的n皇后的解。
class Solution {
public:
vector<vector<string>> ans;
vector<string> res;
vector<vector<string>> solveNQueens(int n) {
res = vector<string>(n,string(n,'.'));
nQueens(,n);
return ans;
}
void nQueens(int i,int n)
{//在n*n的棋盘上，第i-1行之前满足条件
if(i>=n)
{
ans.push_back(res);
return;
}
for(int j=;j<n;j++)
{
res[i][j] = 'Q';
if(isValid(res,n))
nQueens(i+,n);
res[i][j] = '.';
}
}
bool isValid(vector<string>& sol, int n)
{//行和列用数组保存，左下的对角线和一样，右下的对角线差一样，且独一无二，也用数组表示
vector<int> row(n, );
vector<int> col(n, );
vector<int> ldia( * n - , );
vector<int> rdia( * n - , );
for (int i = ; i < sol.size(); i++)
{
string str = sol[i];
for (int j = ; j < n; j++)
{
if (sol[i][j] == 'Q')
{
if (row[i] || col[j] || ldia[i + j] || rdia[i-j+n-])
return false;
row[i] = ; col[j] = ;
ldia[i + j] = ; rdia[i-j+n-] = ;
}
}
}
return true;
}
};