按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
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
经典的回溯法问题，类似的需要回溯法的还有排列组合问题，一般是DFS+回溯来实现一个暴力搜索。
N皇后问题的有两个核心，一个是回溯，一个是对4个限定条件的判断（行、列、两条对角线）
1.回溯核心逻辑
void backtracking(element length,element end,element result,element set,int startIndex,...)
{
if(终止条件==end){
result.add(set); //将当前集合加到结果集中
for(i=startIndex;i<length;++i){
更新当前集合set;
backtracking(length,end,result,set,...); //往下一层遍历
还原当前集合set;
}
}
2.由于棋盘每行每列都会有一个皇后，我们可以选择一行一行确定或者一列一列遍历，这边我选择一行一行遍历。如果一行一行遍历，那么我们在遍历的过程中只需要记录列的皇后放置信息（因为每行放置了皇后之后就会进入下一层遍历，不会在该层停留，即已经确保了同一行只有一个皇后）、主对角线、副对角线的信息。
| (0,0) | (0,1) | (0,2) | (0,3) |
| (1,0) | (1,1) | (1,2) | (1,3) |
| (2,0) | (2,1) | (2,2) | (2,3) |
| (3,0) | (3,1) | (3,2) | (3,3) |
在一个棋盘上，假设某点坐标为( i , j )我们可以明显看出同一主对角线上i - j的值相同（注意不是|i - j|相同），同一副对角线上的i + j相同，据此我们可以用三个数组来快速判断某个位置能不能放入皇后。
1 class Solution {
2 public:
3 vector<int> column,ldiagonal,rdiagonal;
4 vector<vector<string>> result;
5 void backtracking(int n,vector<string> mmap,int row){
6 if (row==n){ //棋盘内已有n个皇后
7 result.push_back(mmap);
8 return;
9 }
10
11 for (int j=0;j<n;++j){
12 if (column[j]==0&&ldiagonal[row+j]==0&&rdiagonal[row-j+n-1]==0){
13 // cout<<row<<" and "<<j<<endl;
14 // cout<<row-j+n-1<<" "<<abs(row-j)<<endl;
15 mmap[row][j]='Q';
16 column[j]=1;
17 ldiagonal[row+j]=1;
18 rdiagonal[row-j+n-1]=1;
19 backtracking(n,mmap,row+1);
20 //回溯
21 rdiagonal[row-j+n-1]=0;
22 ldiagonal[row+j]=0;
23 column[j]=0;
24 mmap[row][j]='.';
25 }
26 }
27 return;
28 }
29 vector<vector<string>> solveNQueens(int n) {
30 //初始化
31 vector<string> initial;
32 for (int i=0;i<n;++i){
33 string temp;
34 for (int j=0;j<n;++j){
35 temp.push_back('.');
36 }
37 initial.push_back(temp);
38 }
39 for (int i=0;i<25;++i){
40 column.push_back(0);
41 rdiagonal.push_back(0);
42 ldiagonal.push_back(0);
43 }
44
45 backtracking(n,initial,0);
46
47 return result;
48 }
49 };
标签：...,遍历,int,对角线,51,力扣,回溯,皇后 From： https://www.cnblogs.com/coderhrz/p/17044381.html