N-Queens II

Description

The N-Queens puzzle is a classic combinatorial challenge. You are given an integer n, and you must figure out how many distinct ways you can place n queens on an n × n chessboard so that no two queens threaten each other.

A queen in chess can attack any piece that lies on the same row, the same column, or either of its two diagonals. Therefore, a valid arrangement requires that every queen occupies its own unique row, column, and diagonals.

Your task is not to return the board configurations themselves, but simply to count how many such valid configurations exist for the given board size n.

Examples

Example 1

Input: n = 4

Output: 2

Explanation: On a 4×4 board, there are exactly two ways to place 4 queens such that none of them attack each other:

Arrangement 1: Queens at positions (row 0, col 1), (row 1, col 3), (row 2, col 0), (row 3, col 2).

Row 0: . Q . .
Row 1: . . . Q
Row 2: Q . . .
Row 3: . . Q .

Arrangement 2: Queens at positions (row 0, col 2), (row 1, col 0), (row 2, col 3), (row 3, col 1).

Row 0: . . Q .
Row 1: Q . . .
Row 2: . . . Q
Row 3: . Q . .

Both arrangements satisfy the constraint that no two queens share the same row, column, or diagonal.

Example 2

Input: n = 1

Output: 1

Explanation: A 1×1 board has only one cell. Placing a single queen there is the only possibility, and it trivially satisfies all constraints since there are no other queens to conflict with.

Example 3

Input: n = 3

Output: 0

Explanation: On a 3×3 board, it is impossible to place 3 queens without at least two of them sharing a row, column, or diagonal. For instance, placing a queen in the center blocks all diagonals, and placing queens on corners still leads to conflicts. Therefore, the count is 0.

Constraints

1 ≤ n ≤ 9

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to consider every possible way to place n queens on the board and then check whether each placement is valid.

Since we know that each row must contain exactly one queen (otherwise two queens would share a row), we can simplify: for each row, try placing the queen in every column. This gives us n choices per row and n rows, resulting in n^n total combinations to explore.

For every candidate placement, we verify the three constraints:

No two queens share the same column.
No two queens share the same main diagonal (top-left to bottom-right).
No two queens share the same anti-diagonal (top-right to bottom-left).

If a placement passes all three checks, we count it as a valid solution. This approach is extremely slow for larger n, but it establishes a clear foundation for understanding the problem.

Step-by-Step Explanation

Let's trace through a simplified version with n = 4. We place queens row by row and check validity after placing all n queens.

Step 1: Start with row 0. Try placing queen at column 0. Placement so far: [0].

Step 2: Move to row 1. Try placing queen at column 0. Placement so far: [0, 0]. After all 4 queens placed, we'd check: queens at (0,0) and (1,0) share column 0 → INVALID.

Step 3: Try column 1 for row 1. Placement so far: [0, 1]. Queens at (0,0) and (1,1) share the main diagonal (0-0 = 1-1 = 0) → INVALID.

Step 4: Try column 2 for row 1. Placement so far: [0, 2]. No column or diagonal conflict between rows 0 and 1 so far. Continue to row 2.

Step 5: Try column 0 for row 2. Placement so far: [0, 2, 0]. Column 0 shared between rows 0 and 2 → INVALID.

Step 6: Try column 1 for row 2. Placement so far: [0, 2, 1]. Check: (1,2) and (2,1) share anti-diagonal (1+2 = 2+1 = 3) → INVALID.

Step 7: Many more attempts continue... Eventually we find [1, 3, 0, 2] and [2, 0, 3, 1] are the two valid placements for n=4.

Step 8: After exhausting all n^n = 256 candidate placements, we count exactly 2 valid solutions.

Algorithm

Generate all possible placements by assigning each of the n rows a column from 0 to n-1 (n^n total combinations).
For each candidate placement array cols[0..n-1]:
a. Check every pair of queens (i, cols[i]) and (j, cols[j]) where i < j.
b. If cols[i] == cols[j], they share a column → invalid.
c. If |i - j| == |cols[i] - cols[j]|, they share a diagonal → invalid.
If no pair conflicts, increment the valid solution count.
Return the total count.

Code

class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        vector<int> cols(n, 0);
        // Generate all n^n placements
        function<void(int)> generate = [&](int row) {
            if (row == n) {
                // Validate placement
                for (int i = 0; i < n; i++) {
                    for (int j = i + 1; j < n; j++) {
                        if (cols[i] == cols[j] || 
                            abs(i - j) == abs(cols[i] - cols[j])) {
                            return;
                        }
                    }
                }
                count++;
                return;
            }
            for (int c = 0; c < n; c++) {
                cols[row] = c;
                generate(row + 1);
            }
        };
        generate(0);
        return count;
    }
};

class Solution:
    def totalNQueens(self, n: int) -> int:
        count = 0
        cols = [0] * n

        def generate(row: int) -> None:
            nonlocal count
            if row == n:
                # Validate the complete placement
                for i in range(n):
                    for j in range(i + 1, n):
                        if cols[i] == cols[j] or abs(i - j) == abs(cols[i] - cols[j]):
                            return
                count += 1
                return
            for c in range(n):
                cols[row] = c
                generate(row + 1)

        generate(0)
        return count

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        int[] cols = new int[n];
        generate(cols, 0, n);
        return count;
    }

    private void generate(int[] cols, int row, int n) {
        if (row == n) {
            // Validate placement
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (cols[i] == cols[j] ||
                        Math.abs(i - j) == Math.abs(cols[i] - cols[j])) {
                        return;
                    }
                }
            }
            count++;
            return;
        }
        for (int c = 0; c < n; c++) {
            cols[row] = c;
            generate(cols, row + 1, n);
        }
    }
}

Complexity Analysis

Time Complexity: O(n^n × n²)

We generate n^n total placements (n choices for each of the n rows). For each complete placement, we check all O(n²) pairs of queens to verify validity. This makes the approach extremely slow even for moderate values of n.

Space Complexity: O(n)

We use an array of size n to store the column assignment for each row, plus O(n) recursion stack depth.

Why This Approach Is Not Efficient

The brute force approach generates n^n total placements. For n = 9 (the maximum constraint), that is 9^9 = 387,420,489 placements, and each requires O(n²) = O(81) pair checks, totaling roughly 31 billion operations. This is far too slow.

The fundamental problem is that we only check validity AFTER placing all n queens. This means we waste enormous effort on placements that were already doomed from the very first conflict. For example, if queens in rows 0 and 1 share a column, we still proceed to fill rows 2 through n-1 before discovering the conflict.

Key insight: if we check validity INCREMENTALLY — validating each queen as we place it — we can prune entire subtrees of the search space the moment a conflict appears. This is the essence of backtracking.

Better Approach - Backtracking

Intuition

Instead of generating all placements and validating at the end, we validate incrementally. We place queens one row at a time, and before placing a queen in a column, we check whether it conflicts with any queen already placed in the rows above.

Think of it like building a tower of blocks one level at a time. Before adding each block, you check if it fits with the blocks below. If it does not fit, you immediately try a different block instead of finishing the entire tower only to discover it collapses.

For each candidate position in the current row, we scan all previously placed queens to verify:

No queen in the same column.
No queen on the same diagonal.

If the position is safe, we place the queen and recurse to the next row. If no position is safe, we backtrack to the previous row and try a different column there.

This pruning dramatically reduces the search space compared to brute force because we never explore branches that are already known to be invalid.

Step-by-Step Explanation

Let's trace through with n = 4:

Step 1: Row 0 — try column 0. No previous queens, so it is safe. Place queen at (0, 0). Board: [Q, -, -, -].

Step 2: Row 1 — try column 0. Column 0 is occupied by row 0 → skip. Try column 1. Diagonal check: |0-1| == |0-1| → same diagonal → skip. Try column 2. Column 2 is free, no diagonal conflict with (0,0). Place queen at (1, 2). Board: [Q, -, Q, -] mapped as cols = [0, 2].

Step 3: Row 2 — try column 0. Diagonal check with (1,2): |2-1| = 1, |0-2| = 2 → no diagonal conflict. But check with (0,0): |2-0| = 2, |0-0| = 0 → no diagonal conflict AND column 0 is taken by row 0 → skip. Try column 1. Check (0,0): col 1 ≠ 0, |2-0|=2 ≠ |1-0|=1 → OK. Check (1,2): col 1 ≠ 2, |2-1|=1 == |1-2|=1 → diagonal conflict → skip. Try column 2: occupied by row 1 → skip. Try column 3. Check (0,0): OK. Check (1,2): |2-1|=1, |3-2|=1 → diagonal conflict → skip. All columns failed → backtrack.

Step 4: Backtrack to row 1, undo (1,2). Try column 3 for row 1. Check (0,0): col 3 ≠ 0, |1-0|=1 ≠ |3-0|=3 → safe. Place queen at (1,3). cols = [0, 3].

Step 5: Row 2 — try column 1. Check (0,0): OK. Check (1,3): |2-1|=1 ≠ |1-3|=2 → OK. Place at (2,1). cols = [0, 3, 1].

Step 6: Row 3 — try column 0: taken by row 0 → skip. Try column 1: taken by row 2 → skip. Try column 2. Check (0,0): |3-0|=3 ≠ |2-0|=2 → OK. Check (1,3): |3-1|=2 ≠ |2-3|=1 → OK. Check (2,1): |3-2|=1 == |2-1|=1 → diagonal conflict → skip. Try column 3: taken by row 1 → skip. All failed → backtrack.

Step 7: Backtrack to row 2. Undo (2,1). Try column 2 for row 2. Check (0,0): |2-0|=2 == |2-0|=2 → diagonal → skip. Try column 3. Check (0,0): OK. Check (1,3): col 3 taken → skip. All failed → backtrack.

Step 8: Backtrack to row 1. Undo (1,3). All columns for row 1 exhausted with queen at (0,0). Backtrack to row 0.

Step 9: Undo (0,0). Try column 1 for row 0. Place at (0,1). cols = [1].

Step 10: Continue recursion... Eventually find cols = [1, 3, 0, 2] → valid solution! Count = 1.

Step 11: Continue exploring... find cols = [2, 0, 3, 1] → valid solution! Count = 2.

Step 12: After exhausting all possibilities with backtracking, return count = 2.

Backtracking N-Queens on a 4×4 Board — Watch how queens are placed row by row, with conflicts causing immediate backtracking rather than completing an invalid placement.

Algorithm

Start from row 0. For each row, try placing the queen in every column (0 to n-1).
Before placing, check all previously placed queens for conflicts:
- Same column: cols[prev_row] == current_col
- Same diagonal: |prev_row - current_row| == |cols[prev_row] - current_col|
If safe, place the queen and recurse to the next row.
If row == n, all queens placed → increment count.
If no column is safe, backtrack to the previous row and try the next column there.
Return the final count after exploring all possibilities.

Code

class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        vector<int> cols(n, -1);

        function<void(int)> solve = [&](int row) {
            if (row == n) {
                count++;
                return;
            }
            for (int col = 0; col < n; col++) {
                bool safe = true;
                for (int prev = 0; prev < row; prev++) {
                    if (cols[prev] == col || 
                        abs(prev - row) == abs(cols[prev] - col)) {
                        safe = false;
                        break;
                    }
                }
                if (safe) {
                    cols[row] = col;
                    solve(row + 1);
                    cols[row] = -1;
                }
            }
        };

        solve(0);
        return count;
    }
};

class Solution:
    def totalNQueens(self, n: int) -> int:
        count = 0
        cols = [-1] * n

        def solve(row: int) -> None:
            nonlocal count
            if row == n:
                count += 1
                return
            for col in range(n):
                safe = True
                for prev in range(row):
                    if cols[prev] == col or abs(prev - row) == abs(cols[prev] - col):
                        safe = False
                        break
                if safe:
                    cols[row] = col
                    solve(row + 1)
                    cols[row] = -1

        solve(0)
        return count

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        int[] cols = new int[n];
        java.util.Arrays.fill(cols, -1);
        solve(cols, 0, n);
        return count;
    }

    private void solve(int[] cols, int row, int n) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            boolean safe = true;
            for (int prev = 0; prev < row; prev++) {
                if (cols[prev] == col ||
                    Math.abs(prev - row) == Math.abs(cols[prev] - col)) {
                    safe = false;
                    break;
                }
            }
            if (safe) {
                cols[row] = col;
                solve(cols, row + 1, n);
                cols[row] = -1;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n! × n)

In the first row we have n column choices. In the second row, at most n-1 columns can be safe (one is blocked). Continuing this pattern gives roughly n × (n-1) × (n-2) × ... = n! placements explored. For each placement attempt, the safety check scans up to the current row (O(n) in the worst case), giving O(n! × n) total.

Space Complexity: O(n)

We use a single array of size n to track column assignments, plus O(n) recursion stack depth.

Why This Approach Is Not Efficient

While backtracking is a huge improvement over brute force, there is still a bottleneck: the safety check. Every time we want to place a queen, we loop through all previously placed queens (up to n-1) to check for column and diagonal conflicts. This O(n) check per candidate position adds up across the entire recursion tree.

The insight for improvement is that we can make the safety check O(1) instead of O(n) by using auxiliary data structures to track which columns and diagonals are already occupied. Three boolean arrays (or hash sets) — one for columns, one for main diagonals, and one for anti-diagonals — allow us to check all three constraints in constant time.

Optimal Approach - Backtracking with Column and Diagonal Hashing

Intuition

We keep the same backtracking framework — placing queens row by row and pruning invalid branches — but we optimize the conflict detection from O(n) to O(1) per check.

The key observation is about how diagonals work on a chessboard:

All cells on the same main diagonal (going from top-left to bottom-right) share the same value of (row - col). For example, cells (0,0), (1,1), (2,2) all have row - col = 0.
All cells on the same anti-diagonal (going from top-right to bottom-left) share the same value of (row + col). For example, cells (0,2), (1,1), (2,0) all have row + col = 2.

We maintain three sets:

columns: which columns already have a queen.
main_diag: which main diagonals (row - col) already have a queen.
anti_diag: which anti-diagonals (row + col) already have a queen.

Before placing a queen at (row, col), we simply check if col is in columns, (row - col) is in main_diag, or (row + col) is in anti_diag. Each check is O(1). When we place a queen, we add to all three sets. When we backtrack, we remove from all three sets.

This reduces the per-candidate cost from O(n) to O(1), making the overall time complexity O(n!) instead of O(n! × n).

Step-by-Step Explanation

Let's trace through with n = 4, using sets for O(1) conflict detection:

Step 1: Initialize empty sets: columns = {}, main_diag = {}, anti_diag = {}.

Step 2: Row 0, try col 0. Check: 0 ∉ columns, (0-0)=0 ∉ main_diag, (0+0)=0 ∉ anti_diag → safe. Place queen. Update sets: columns={0}, main_diag={0}, anti_diag={0}.

Step 3: Row 1, try col 0. Check: 0 ∈ columns → blocked. Skip.

Step 4: Row 1, try col 1. Check: 1 ∉ columns. (1-1)=0 ∈ main_diag → blocked. Skip.

Step 5: Row 1, try col 2. Check: 2 ∉ columns, (1-2)=-1 ∉ main_diag, (1+2)=3 ∉ anti_diag → safe. Place queen. Update: columns={0,2}, main_diag={0,-1}, anti_diag={0,3}.

Step 6: Row 2, try col 0. Check: 0 ∈ columns → blocked.

Step 7: Row 2, try col 1. Check: 1 ∉ columns, (2-1)=1 ∉ main_diag, (2+1)=3 ∈ anti_diag → blocked. Skip.

Step 8: Row 2, try col 3. Check: 3 ∉ columns, (2-3)=-1 ∈ main_diag → blocked. All cols fail → backtrack. Remove queen from (1,2): columns={0}, main_diag={0}, anti_diag={0}.

Step 9: Row 1, try col 3. Check: 3 ∉ columns, (1-3)=-2 ∉ main_diag, (1+3)=4 ∉ anti_diag → safe. Place. Update: columns={0,3}, main_diag={0,-2}, anti_diag={0,4}.

Step 10: Row 2, try col 1. Check: 1 ∉ columns, (2-1)=1 ∉ main_diag, (2+1)=3 ∉ anti_diag → safe. Place. Update: columns={0,3,1}, main_diag={0,-2,1}, anti_diag={0,4,3}.

Step 11: Row 3, try col 2. Check: 2 ∉ columns, (3-2)=1 ∈ main_diag → blocked. All remaining cols also blocked → backtrack further.

Step 12: Eventually find solution [1,3,0,2]: columns checks pass instantly, count becomes 1.

Step 13: Continue and find solution [2,0,3,1]: count becomes 2.

Step 14: All branches explored. Return 2. Each candidate check was O(1) instead of O(n).

Optimal N-Queens — O(1) Conflict Detection with Sets — Observe how column, main-diagonal, and anti-diagonal sets enable instant conflict checks, dramatically speeding up the backtracking search.

Algorithm

Create three sets: columns, main_diag (tracks row - col values), anti_diag (tracks row + col values).
Define a recursive function solve(row):
a. Base case: if row == n, increment count and return.
b. For each col in 0 to n-1:
- If col ∈ columns OR (row - col) ∈ main_diag OR (row + col) ∈ anti_diag → skip.
- Otherwise, add col to columns, (row-col) to main_diag, (row+col) to anti_diag.
- Recursively call solve(row + 1).
- Remove col from columns, (row-col) from main_diag, (row+col) from anti_diag (backtrack).
Call solve(0) and return count.

Code

class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        unordered_set<int> columns, mainDiag, antiDiag;

        function<void(int)> solve = [&](int row) {
            if (row == n) {
                count++;
                return;
            }
            for (int col = 0; col < n; col++) {
                if (columns.count(col) || mainDiag.count(row - col) || antiDiag.count(row + col)) {
                    continue;
                }
                columns.insert(col);
                mainDiag.insert(row - col);
                antiDiag.insert(row + col);
                solve(row + 1);
                columns.erase(col);
                mainDiag.erase(row - col);
                antiDiag.erase(row + col);
            }
        };

        solve(0);
        return count;
    }
};

class Solution:
    def totalNQueens(self, n: int) -> int:
        count = 0
        columns = set()
        main_diag = set()
        anti_diag = set()

        def solve(row: int) -> None:
            nonlocal count
            if row == n:
                count += 1
                return
            for col in range(n):
                if col in columns or (row - col) in main_diag or (row + col) in anti_diag:
                    continue
                columns.add(col)
                main_diag.add(row - col)
                anti_diag.add(row + col)
                solve(row + 1)
                columns.remove(col)
                main_diag.remove(row - col)
                anti_diag.remove(row + col)

        solve(0)
        return count

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<>();
        Set<Integer> mainDiag = new HashSet<>();
        Set<Integer> antiDiag = new HashSet<>();
        solve(0, n, columns, mainDiag, antiDiag);
        return count;
    }

    private void solve(int row, int n, Set<Integer> columns, Set<Integer> mainDiag, Set<Integer> antiDiag) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (columns.contains(col) || mainDiag.contains(row - col) || antiDiag.contains(row + col)) {
                continue;
            }
            columns.add(col);
            mainDiag.add(row - col);
            antiDiag.add(row + col);
            solve(row + 1, n, columns, mainDiag, antiDiag);
            columns.remove(col);
            mainDiag.remove(row - col);
            antiDiag.remove(row + col);
        }
    }
}

Complexity Analysis

Time Complexity: O(n!)

The backtracking structure is the same as before: at each row, we try up to n columns, but previously placed queens eliminate some options. The branching factor decreases roughly as n, n-2, n-4, ... giving approximately n! nodes explored. The critical improvement is that each node's validity check is now O(1) (set lookup) instead of O(n), removing the extra factor.

Space Complexity: O(n)

We maintain three sets, each holding at most n elements (one per row with a queen). Combined with the recursion stack of depth n, total space is O(n).

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

N-Queens II

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Backtracking

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Backtracking with Column and Diagonal Hashing

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis