Java easy to understand backtracking solution.


  • 0
    C
    int count;
    public int totalNQueens(int n) {
        dfs(n, 0, new int[n]);
        return count;
    }
    
    private void dfs(int n, int idx, int[] valid) {
        if (idx == n) {
            count++;
            return;
        }
        for (int j = 0; j < n; j++) {
            if (checkValid(valid, idx, j)) {
                valid[idx] = j;
                dfs(n, idx+1, valid);
            }
        }
    }
    
    private boolean checkValid(int[] valid, int r, int c) {
        for (int i = 0; i < r; i++) {
            if (c == valid[i] || (r-i == Math.abs(c-valid[i]))) {
                return false;
            }
        }
        return true;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.