52.N-Queens II N皇后II

class Solution {
    public int sum = 0;
    public int totalNQueens(int n) {
        int[] arr = new int[n];
        Nqueen(0, n, arr);
        return sum;
    }
    public void Nqueen(int i, int n, int arr[]) {
        if (i == n) {
            sum++;
        } 
                else {
            for (int temp = 0; temp < n; temp++) {
                arr[i] = temp;
                boolean flag = true;
                for (int x = 0; x < i; x++) {
                    if (arr[i] == arr[x] || (Math.abs(arr[i] - arr[x]) == Math.abs(x - i))) {
                        flag = false;
                        arr[i] = 0;
                        break;
                    }
                }
                if (flag == true) {
                    Nqueen(i + 1, n, arr);
                }
            }
        }
    }
}

cclass Solution {
int count;
boolean bool[][];
int n;
public int totalNQueens(int n) {
count = 0;
bool = new boolean[n][n];
this.n = n;
dfs(0);
return count;
}
private void dfs(int x) {
if (x == n) {
count++;
return;
}
for (int i = 0; i < n; i++) {
int temp = x;
int flag = 0;
while (temp >= 0) {
if((i+flag=0&&bool[temp][i-flag])||bool[temp][i])break;
temp--;
flag++;
}
if(temp==-1) {
bool[x][i] = true;
dfs(x+1);
bool[x][i] = false;
}
}
}
}

![](https://uploadfiles.nowcoder.com/images/20190906/800352933_1567743952539_26109DE22E46F983CC1EED0A44A00D2D)
2 * n 的原因

class Solution {
int count;
boolean bool_col[];
boolean bool_x[];
boolean bool_y[];
int n;
public int totalNQueens(int _n) {
n = _n ;
count = 0;
bool_col = new boolean [n] ;
bool_x = new boolean [2n] ;
bool_y = new boolean [2n] ;
dfs(0);
return count ;
}
private void dfs(int i) {
if(i == n ) {
count++;
return ;
}
for(int x = 0 ; x <n ; x++) {
if(!bool_col[x] && !bool_x[x+i]&&!bool_y[i-x+n]) {
bool_col[x] = bool_x[x+i] = bool_y[i-x+n] = true;
dfs(i+1);
bool_col[x] = bool_x[x+i] = bool_y[i-x+n] = false;
}
}
}
}
```