题目
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4输出: 2解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
链接：https://leetcode-cn.com/problems/n-queens-ii/solution/javahui-su-suan-fa-by-zuki-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解答及思路
使用int二维数组flags存放是否能落子，为0则能落子，大于0则不能落子。由于每行只能有一个棋子，于是我使每次落子行都与n-1相等，落完字后调用dfs1函数将与这个子相关的（横、竖、左斜、右斜）子的flags内相关坐标执行++操作，循环过这次落子后，使用dfs2函数回溯再执行下一次循环。
源码
class Solution {
boolean flag = true;
int[][] flags;
int num;
int m;
public int totalNQueens(int n) {
if(flag){
flags = new int[n][n];
m = n;
flag = false;
}
if(n==1){
for(int i = 0;i<m;i++){
if(flags[0][i]==0){
num++;
}
}
}else{
for(int i = 0;i<m;i++){
if(flags[n-1][i]==0){
dfs1(n-1,i);
totalNQueens(n-1);
dfs2(n-1,i);
}
}
}
return num;
}
public void dfs1(int row,int high){
for(int i = 0;i<m;i++){
flags[row][i] ++ ;
flags[i][high] ++ ;
if(i+high-row>=0&&i+high-row<m){
flags[i][i+high-row] ++ ;
}
if(high+row-i>=0&&high+row-i<m){
flags[i][high+row-i] ++ ;
}
}
}
public void dfs2(int row,int high){
for(int i = 0;i<m;i++){
flags[row][i] -- ;
flags[i][high] -- ;
if(i+high-row>=0&&i+high-row<m){
flags[i][i+high-row] -- ;
}
if(high+row-i>=0&&high+row-i<m){
flags[i][high+row-i] -- ;
}
}
}
}
