N-Queens II

NeetCode: N-Queens II · LeetCode: 52. N-Queens II · Difficulty: Hard

Place n queens on an n x n chessboard so that no two queens attack each other (same row, column or diagonal). Return the number of distinct solutions. Unlike N-Queens, the boards are counted, not built.

Example

Text

Input:  n = 4    Output: 2
Input:  n = 1    Output: 1
Input:  n = 2    Output: 0
Input:  n = 8    Output: 92

Brute force: try every permutation and validate

Put exactly one queen in each row. Then the column of the queen in row r is perm[r], and no two queens share a column exactly when perm is a permutation of 0..n. So enumerate all n! permutations and, for each one, check only the diagonals: queens in rows i < j clash when |perm[i] - perm[j]| == j - i.

Java

public class Main {
    static class Solution {
        public int totalNQueens(int n) {
            int[] perm = new int[n];
            for (int i = 0; i < n; i++) {
                perm[i] = i;
            }
            return permute(perm, 0);
        }

        // Counts the valid arrangements of perm[k..] after fixing perm[0..k).
        private int permute(int[] perm, int k) {
            if (k == perm.length) {
                return valid(perm) ? 1 : 0;
            }
            int count = 0;
            for (int i = k; i < perm.length; i++) {
                swap(perm, k, i);
                count += permute(perm, k + 1);
                swap(perm, k, i);
            }
            return count;
        }

        private boolean valid(int[] perm) {
            for (int i = 0; i < perm.length; i++) {
                for (int j = i + 1; j < perm.length; j++) {
                    if (Math.abs(perm[i] - perm[j]) == j - i) {
                        return false;
                    }
                }
            }
            return true;
        }

        private void swap(int[] a, int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        for (int n : new int[] {4, 1, 2, 8}) {
            System.out.println("n = " + n + " -> " + sol.totalNQueens(n));
        }
    }
}

Output

n = 4 -> 2
n = 1 -> 1
n = 2 -> 0
n = 8 -> 92

The permutation count is n!, so the int return type is enough while n stays small. The swap-based recursion visits every permutation once, and each takes O(n^2) to validate. Nothing is pruned: a clash between the first two rows is only noticed after all n rows are filled. Time: O(n! * n^2). Space: O(n) for the permutation and recursion.

Optimal: row-by-row backtracking with column and diagonal flags

Place one queen per row and skip any square that is attacked. Three boolean[] arrays answer "is this square attacked?" in O(1):

cols[c]: a queen is already in column c.
diag[r + c]: cells on the same / diagonal share r + c.
anti[r + n - 1 - c]: cells on the same \ diagonal share r - c; adding n - 1 keeps the index non-negative.

Set the flags, recurse into the next row, add up the counts, then clear the flags. The recursion returns how many placements succeeded, so no board is built.

Java

public class Main {
    static class Solution {
        public int totalNQueens(int n) {
            return solve(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
        }

        private int solve(int r, int n, boolean[] cols, boolean[] diag, boolean[] anti) {
            if (r == n) {
                return 1;
            }
            int count = 0;
            for (int c = 0; c < n; c++) {
                int d = r + c;
                int a = r + n - 1 - c;
                if (cols[c] || diag[d] || anti[a]) {
                    continue; // attacked: prune
                }
                cols[c] = true;
                diag[d] = true;
                anti[a] = true;
                count += solve(r + 1, n, cols, diag, anti);
                cols[c] = false;
                diag[d] = false;
                anti[a] = false;
            }
            return count;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        for (int n : new int[] {4, 1, 2, 8}) {
            System.out.println("n = " + n + " -> " + sol.totalNQueens(n));
        }
    }
}

Output

n = 4 -> 2
n = 1 -> 1
n = 2 -> 0
n = 8 -> 92

Time: bounded by O(n!) (row r has at most n - r free columns) and much less in practice, since attacked squares are pruned at once. Space: O(n) for the flag arrays and the recursion.

The three arrays can also be packed into three integer bitmasks (shift the diagonal masks by one bit per row and pick the lowest free square with free & -free), which removes the inner loop over attacked squares. The algorithm is the same.

How to explain it in an interview

Baseline: enumerate all n! column permutations and check diagonals: O(n² · n!), with no early pruning.
Key insight: one queen per row, and reject a square the moment it is attacked. Column, r + c and r - c each identify a line, so three boolean arrays give an O(1) attack test.
Steps: (1) solve(r) returns 1 when r == n; (2) loop over columns and continue if any of the three flags is set; (3) set the flags; (4) add solve(r + 1) to the count; (5) clear the flags.
Complexity: time bounded by O(n!), much smaller in practice; space O(n).
Follow-ups and pitfalls: bitmasks speed it up further, and symmetry allows counting only half of the first-row columns and doubling. r - c can be negative, so the index is r + n - 1 - c.