题目：
N皇后问题：将n个皇后放置在(n imes n)的棋盘上，并且皇后彼此之间不能相互攻击。给定一个整数n，返回所有不同n皇后问题的具体解。
示例：
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
题目链接：https://leetcode-cn.com/problems/n-queens
思路：
n皇后问题的经典解法便是回溯，我们当然可以一一列举出棋盘上八个皇后所有可能的位置分布，然后再逐一判断满足条件，但通常我们无法承受这样的枚举量。而回溯法是将生成和检查过程有机地结合起来，减少不必要的枚举。
具体到问题中，显然所有皇后都应出现在不同的行和列中，我们逐行放入一个皇后，将列一一列举，判断当前放入皇后与此前放入的皇后是否会在列以及对角线上冲突，如果冲突，继续枚举下一列，否则，放入该皇后。
通过解答树可以帮助理解其中的回溯过程。
代码：
class Solution {
public:
int C[100] = {-1}; // C[i]=j表示第i行的皇后被放置在第j列
void search(int n, int cur, vector<vector<string>> &ans){
if(cur == n){
vector<string> one_sol;
for(int i = 0; i < n; ++i){
string str(n, '.');
for(int j = 0; j < str.size(); ++j){
if(j == C[i]) str[j] = 'Q'; //根据C[i]可以知道Q放置在哪一列
}
one_sol.push_back(str);
}
ans.push_back(one_sol);
}else for(int i = 0; i < n; ++i){ //对每一列
int ok = 1;
C[cur] = i; //尝试将cur行的皇后放到i列
for(int j = 0; j < cur; ++j){ //判断是否与此前放入的皇后冲突
if(C[cur] == C[j] || cur+C[cur] == j+C[j] || cur-C[cur] == j-C[j]){ //行+列表示副对角线，行-列表示主对角线
ok = 0; break;
}
}
if(ok) search(n, cur+1, ans); //不冲突就寻找下一行皇后放置的位置
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
search(n, 0, ans);
return ans;
}
};