Course4all

N-Queens II

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Backtracking.

N-Queens II

Counting Solutions

This is identical to N-Queens I, but instead of returning the board layouts, we only need to return the total number of distinct solutions.

Optimization

Since we don't need to construct the board, we can use bitmasks for extremely fast collision detection and state management.
Count the number of distinct N-Queens solutions. Includes visual N=4 solution count.
Hard

Examples

Input: n = 4
Output: 2
Approach 1

Level I: Backtracking (Count only)

Intuition

Use the same backtracking logic as N-Queens I, but increment a counter instead of saving the board.
Maintain a count variable. Use boolean arrays to track occupied columns, main diagonals, and anti-diagonals.
⏱ O(N!)💾 O(N)

Detailed Dry Run

Dry Run: N=4 | Row | Valid Cols | Action | Count | | :-- | :--- | :--- | :--- | | 0 | {0,1,2,3} | Try 1 | 0 | | 1 | {3} | Try 3 | 0 | | 2 | {0} | Try 0 | 0 | | 3 | {2} | FOUND! | 1 |
java
class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];
        boolean[] d1 = new boolean[2 * n];
        boolean[] d2 = new boolean[2 * n];
        backtrack(0, n, cols, d1, d2);
        return count;
    }
    private void backtrack(int r, int n, boolean[] cols, boolean[] d1, boolean[] d2) {
        if (r == n) {
            count++; return;
        }
        for (int c = 0; c < n; c++) {
            int id1 = r - c + n;
            int id2 = r + c;
            if (cols[c] || d1[id1] || d2[id2]) continue;
            cols[c] = d1[id1] = d2[id2] = true;
            backtrack(r + 1, n, cols, d1, d2);
            cols[c] = d1[id1] = d2[id2] = false;
        }
    }
}
Approach 2

Level II: Bitmask Backtracking

Intuition

Use integers as bitmasks for lightning-fast state management.
Represent occupied columns, diagonals as bits in an integer. Only use bitwise operations to check and update state.
⏱ O(N!)💾 O(N)

Detailed Dry Run

N=4. Initial: columns=0, ld=0, rd=0. Available: bits in ~(cols | ld | rd).

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionPalindrome Partitioning
Next Question →Regular Expression Matching