Problem #52: N-Queens II

Intuition & Strategy Breakdown

Use backtracking to place queens row by row. Maintain boolean tracking arrays/sets for occupied columns and both main/anti diagonals.

Python Solution

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = set()
        posDiag = set()  # (r + c)
        negDiag = set()  # (r - c)
        
        res = 0
        def backtrack(r):
            if r == n:
                nonlocal res
                res += 1
                return
            
            for c in range(n):
                if c in cols or (r + c) in posDiag or (r - c) in negDiag:
                    continue
                
                cols.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                
                backtrack(r + 1)
                
                cols.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)
        
        backtrack(0)
        return res

Java Solution

class Solution {
    private int count = 0;
    private Set cols = new HashSet<>();
    private Set posDiag = new HashSet<>();
    private Set negDiag = new HashSet<>();

    public int totalNQueens(int n) {
        backtrack(0, n);
        return count;
    }

    private void backtrack(int r, int n) {
        if (r == n) {
            count++;
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols.contains(c) || posDiag.contains(r + c) || negDiag.contains(r - c)) {
                continue;
            }
            cols.add(c);
            posDiag.add(r + c);
            negDiag.add(r - c);
            
            backtrack(r + 1);
            
            cols.remove(c);
            posDiag.remove(r + c);
            negDiag.remove(r - c);
        }
    }
}