1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    private int ans = 0;   
    public int Nqueen(int n) {
        int[] pos = new int[n];
        backtrack(n, 0, pos);
        return ans;
    }

    private boolean isValid(int[] pos,int row,int col){
        for(int i=0;i<row;i++){
            if(pos[i]==col||Math.abs(row-i)==Math.abs(col-pos[i])){
                return false;
            }
        }
        return true;
    }

    private void backtrack(int n,int row,int[] pos){
        if(row==n){
            ans++;
            return;
        }

        for(int i=0;i<n;i++){
            if(isValid(pos, row, i)){
                pos[row]=i;
                backtrack(n, row+1, pos);
            }
        }
    }