Course4all
Join us on telegram
Home/dsa/Backtracking/N-Queens II

N-Queens II

Master this topic with zero to advance depth.

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).

← Previous QuestionPalindrome Partitioning
Next Question →Regular Expression Matching