Problem Number

52

Problem Title

N-Queens II

LeetCode Link

https://leetcode.com/problems/n-queens-ii/

Contribution Checklist

• I have written the Approach section.
• I have written the Intuition section.
• I have included a working C++ solution.
• I will raise a PR and ensure the filename follows the convention [Number]. [Problem Title].cpp.

Approach

Backtracking with Row-by-Row Placement

Initialization

• Initialize a variable count to 0 to store the number of valid solutions.
• Create three sets (or arrays) to keep track of attacks:
  1. cols – columns where a queen is already placed.
  2. diag – main diagonals under attack (row + col).
  3. anti_diag – anti-diagonals under attack (row - col).

Iteration (Row-by-Row Backtracking)

1. Start from the first row (row = 0).
2. For each column in the current row, check if placing a queen is valid (not in cols, diag, or anti_diag).
3. If valid:
   • Add the column to cols.
   • Add row + col to diag.
   • Add row - col to anti_diag.
   • Recursively place a queen in the next row.
   • After recursion, backtrack by removing the queen from cols, diag, and anti_diag.
4. If row == n, all queens are placed safely. Increment count.

Termination
Return the total count of valid N-Queens solutions.

Intuition

Row-by-Row Safe Placement

• The N-Queens problem is fundamentally a constraint satisfaction problem.
• Each queen attacks its column, main diagonal, and anti-diagonal.
• By keeping track of these attacked positions, we can efficiently check if placing a queen is safe.
• Backtracking allows us to explore all possible configurations row by row.
• The key insight is that each queen placement depends only on columns and diagonals already occupied, so we don’t need to check the entire board each time.

Solution in C++

class Solution {
public:
    int count = 0;

    void backtrack(int row, int n, 
                   unordered_set<int>& cols, 
                   unordered_set<int>& diag, 
                   unordered_set<int>& anti_diag) {
        if (row == n) {
            count++;
            return;
        }

        for (int col = 0; col < n; col++) {
            if (cols.count(col) || diag.count(row + col) || anti_diag.count(row - col))
                continue;

            cols.insert(col);
            diag.insert(row + col);
            anti_diag.insert(row - col);

            backtrack(row + 1, n, cols, diag, anti_diag);

            cols.erase(col);
            diag.erase(row + col);
            anti_diag.erase(row - col);
        }
    }

    int totalNQueens(int n) {
        unordered_set<int> cols, diag, anti_diag;
        backtrack(0, n, cols, diag, anti_diag);
        return count;
    }
};