49. N-Queens II

Place one queen per row. For each row try every column that isn't already attacked; track occupied columns and both diagonals in sets for O(1) checks. Recurse to the next row, and count a solution each time all n rows are filled.

Idea

Exactly one queen sits in each row, so we decide row by row which column to use. A column is safe if no earlier queen shares its column or either diagonal. Cells on the same:

• column share col;
• ↘ diagonal share row - col;
• ↙ diagonal share row + col.

Three sets track occupied columns and diagonals, giving O(1) safety checks. Backtracking explores placements; each time we fill all n rows, we've found one arrangement.

Algorithm

backtrack(row):

1. If row == n, increment the solution count.
2. For each col in 0..n-1: skip if col, row-col, or row+col is occupied. Otherwise mark them, recurse on row+1, then unmark.

Worked example: n = 4

The 4×4 board has exactly 2 non-attacking arrangements (mirror images of each other).

Complexity

• Time: O(n!) — pruned heavily by the attack checks.
• Space: O(n) for the sets and recursion.

import java.util.HashSet;
import java.util.Set;

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        backtrack(0, n, new HashSet<>(), new HashSet<>(), new HashSet<>());
        return count;
    }

    private void backtrack(int row, int n, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) {
                continue;
            }
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            backtrack(row + 1, n, cols, diag1, diag2);
            cols.remove(col);
            diag1.remove(row - col);
            diag2.remove(row + col);
        }
    }
}