Problem Description

The N-Queens II problem asks you to determine the total number of distinct ways to place n queens on an n x n chessboard so that no two queens attack each other. A queen can attack horizontally, vertically, and diagonally. Your task is to return the total count of valid arrangements, not the arrangements themselves.

• Each solution must have exactly one queen in every row and every column.
• No two queens can share the same diagonal.
• The input is a single integer n (where 1 ≤ n ≤ 9).
• Return a single integer: the number of valid solutions.

Thought Process

At first glance, you might consider brute-forcing every possible way to place n queens on the board and checking if each configuration is valid. However, since the number of possible placements grows rapidly with n, this approach is not practical for larger boards.

Instead, we can use recursion and backtracking to build solutions step by step. The key insight is that by placing one queen per row and ensuring that no two queens threaten each other, we can reduce the search space significantly. We can also use sets or arrays to efficiently track which columns and diagonals are already under attack, allowing us to quickly determine if a position is safe for placing a queen.

The shift from brute-force to backtracking is crucial: instead of generating all board states, we only try positions that are guaranteed not to violate the constraints up to that point.

Solution Approach

We use a recursive backtracking algorithm to solve the N-Queens II problem. Here’s how the solution works step by step:

1. Represent the Board: Since only one queen can be placed per row, we can represent the board by keeping track of which column in each row contains a queen.
2. Track Attacked Positions:
   • We use a set (or boolean array) to track which columns are already occupied by queens.
   • We use two additional sets for the two types of diagonals:
     • Main diagonal (row - col): All cells with the same row - col are on the same main diagonal.
     • Anti-diagonal (row + col): All cells with the same row + col are on the same anti-diagonal.
3. Recursive Backtracking:
   • At each recursive call, we try to place a queen in the current row.
   • For each column, we check if placing a queen in that column (and the current row) would conflict with any already-placed queens by checking the column and diagonal sets.
   • If it’s safe, we mark the column and diagonals as occupied and move to the next row.
   • If we reach row n, it means we’ve placed all queens successfully, so we increment our solution count.
   • After trying a position, we backtrack by unmarking the column and diagonals to try other possibilities.
4. Return the Result: After the recursive process completes, return the total count of valid solutions found.

This approach is efficient because it prunes invalid branches early, never exploring board configurations that would result in conflicts later.

Example Walkthrough

Let’s walk through the process for n = 4:

1. Start with an empty board and begin placing queens row by row.
2. Row 0: Try placing a queen in column 0. Mark column 0, main diagonal (0), and anti-diagonal (0) as occupied.
3. Row 1: Try columns 0-3. Only column 2 is safe (columns 0 and diagonals for 1 and 3 are attacked). Place queen at (1,2), mark accordingly.
4. Row 2: Try columns 0-3. Only column 1 is safe. Place queen at (2,1), mark accordingly.
5. Row 3: Try columns 0-3. No safe column, so backtrack.
6. Backtrack to row 2, remove queen, try other columns (none safe), backtrack further.
7. Continue this process, exploring other positions in row 0 (columns 1, 2, 3) and their downstream possibilities.
8. Eventually, find two valid solutions for n=4. The algorithm counts both and returns 2.

At every step, invalid configurations are pruned immediately, so the algorithm never tries to place queens in positions that would lead to conflicts.

Code Implementation

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row, cols, diag1, diag2):
            if row == n:
                return 1
            count = 0
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                count += backtrack(row + 1, cols, diag1, diag2)
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
            return count

        return backtrack(0, set(), set(), set())
      

class Solution {
public:
    int totalNQueens(int n) {
        return backtrack(0, n, vector<bool>(n), vector<bool>(2 * n), vector<bool>(2 * n));
    }
private:
    int backtrack(int row, int n, vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2) {
        if (row == n) return 1;
        int count = 0;
        for (int col = 0; col < n; ++col) {
            int d1 = row - col + n;
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            cols[col] = diag1[d1] = diag2[d2] = true;
            count += backtrack(row + 1, n, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
        return count;
    }
};
      

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

    private int backtrack(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        if (row == n) return 1;
        int count = 0;
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n;
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            cols[col] = diag1[d1] = diag2[d2] = true;
            count += backtrack(row + 1, n, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
        return count;
    }
}
      

var totalNQueens = function(n) {
    function backtrack(row, cols, diag1, diag2) {
        if (row === n) return 1;
        let count = 0;
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            count += backtrack(row + 1, cols, diag1, diag2);
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
        return count;
    }
    return backtrack(0, new Set(), new Set(), new Set());
};
      

Time and Space Complexity

• Brute-force approach: There are n^n ways to place n queens on an n x n board (since each queen can go in any square), but most are invalid. Checking each configuration for validity is also expensive, leading to an exponential time complexity.
• Backtracking approach: At each row, we only try columns that are not under attack, pruning large portions of the search space. The worst-case time complexity is O(n!) because for each row, there is at most one queen per column, and we never revisit columns. For small n (up to 9), this is efficient.
• Space complexity: O(n) for the recursion stack and for the sets/arrays tracking columns and diagonals.

The optimized backtracking approach is efficient for the problem constraints.

Summary

The N-Queens II problem challenges us to count all valid ways to place n queens on an n x n chessboard without conflict. By using backtracking and efficiently tracking columns and diagonals, we prune invalid placements early and count only valid solutions. This approach is both elegant and practical for the given constraints, and highlights the power of recursive problem-solving with state tracking.