题目：N皇后
Description
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
Sample
输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
Solution
经典问题！不断试探、纠正！！！ 利用布尔数组判断是否会发生冲突，如果已经有皇后放在了那里，设为1，否则设为0。 判断对角线冲突时，有个比较好的技巧： 由于每条主对角线的（x-y）是一定的，每条副对角线的（x+y）也是一定的。 所以可以用（x-y）表示主对角线，用（x+y）表示副对角线。跟处理列的情况统一了！！！ 因为（x-y）可能会出现负数，所以可以用（x-y+n）表示主对角线！都是作为数组下标表示！
AC Code
class Solution {
public:
int n
;
int a
[20];
bool vis
[20];
bool z
[20];
bool f
[20];
vector
<vector
<string
> > v
;
void write() {
vector
<string
> temp
;
for (int i
= 1; i
<= n
; i
++) {
string s
;
for (int j
= 1; j
<= n
; j
++) {
if (j
== a
[i
]) s
+='Q';
else s
+='.';
}
temp
.push_back(s
);
}
v
.push_back(temp
);
}
void dfs(int dep
) {
if (dep
> n
) {
write(); return;
}
for (int i
= 1; i
<= n
; i
++) {
if (!vis
[i
] && !z
[i
+ dep
] && !f
[i
- dep
+ n
]) {
vis
[i
] = 1; z
[i
+ dep
] = 1; f
[i
- dep
+ n
] = 1;
a
[dep
] = i
;
dfs(dep
+ 1);
vis
[i
] = 0; z
[i
+ dep
] = 0; f
[i
- dep
+ n
] = 0;
}
}
}
vector
<vector
<string
>> solveNQueens(int m
) {
n
=m
;
dfs(1);
return v
;
}
};
PS：希望对你有帮助！
