52. N Queens II - jiejackyzhang/leetcode-note GitHub Wiki

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

解题思路为backtracking。

public class Solution {
    
    private int res;
    private int N;
    private int[] cols;
    
    public int totalNQueens(int n) {
        res = 0;
        N = n;
        cols = new int[N]; 
        solve(0);
        return res;
    }
    
    private void solve(int row) {
        if(row == N) {
            res++;
            return;
        }
        for(int col = 0; col < N; col++) {
            cols[row] = col;
            if(isValid(row)) {
                solve(row + 1);
            }
        }
    }
    
    private boolean isValid(int row) {
        for(int i = 0; i < row; i++) {
            if(cols[i] == cols[row] || row - i == Math.abs(cols[row] - cols[i])) return false;
        }
        return true;
    }
}