Leetcode - 52. N-Queens II

🏰 Solving the N-Queens Problem with Backtracking

The N-Queens problem is a classic in algorithms and interview prep. It asks:

Place N queens on an N×N chessboard so that no two queens attack each other.

Queens can attack vertically, horizontally, and diagonally. The task is to count the total number of valid arrangements.

---

✨ Key Insight

When placing queens row by row:

• Each row can have only one queen.
• Each column can have only one queen.
• Each diagonal can have only one queen.

So, at each step, we just need to check if placing a queen in the current cell (r, c) is safe. If yes → place it and recurse to the next row.

---

⚙️ Backtracking Approach

We use recursion to try all possible placements:

1. Row by row recursion – Start from row 0, and for each column, check if placing a queen is valid.
2. Use sets for quick lookup:

• col: columns where queens are already placed.
• posDiag: positive diagonals (r + c is constant).

• negDiag: negative diagonals (r - c is constant).

  1. If a position (r, c) is safe:

• Place queen → add to sets.

• Recurse for next row.

• Backtrack → remove from sets.

  1. When r === n, we found a valid arrangement → increment result.

---

🖥️ Implementation (JavaScript)

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
    let col = new Set();
    let posDiag = new Set();
    let negDiag = new Set();
    let res = 0;

    const backtrack = (r) => {
        if (r === n) {
            res += 1;  // Found a valid board
            return;
        }

        for (let c = 0; c < n; c++) {
            // Check if queen can be placed
            if (col.has(c) || posDiag.has(r + c) || negDiag.has(r - c)) {
                continue;
            }

            // Place queen
            col.add(c);
            posDiag.add(r + c);
            negDiag.add(r - c);

            // Recurse to next row
            backtrack(r + 1);

            // Backtrack (remove queen)
            col.delete(c);
            posDiag.delete(r + c);
            negDiag.delete(r - c);
        }
    };

    backtrack(0);
    return res;
};

---

⏱️ Time & Space Complexity

• Time Complexity: O(N!)

  • In the worst case, we try N options for row 1, N-1 for row 2, and so on.
  • The actual branching is smaller due to pruning (invalid placements), but O(N!) is a safe upper bound.

• Space Complexity: O(N)

  • Sets col, posDiag, and negDiag hold at most N elements.
  • Recursion stack depth is N.

---

✅ Example Run

For n = 4, the valid solutions are 2:

. Q . .      . . Q .
. . . Q      Q . . .
Q . . .      . . . Q
. . Q .      . Q . .

The function correctly returns 2.

---

🎯 Final Thoughts

• This problem is a perfect introduction to backtracking because you learn how to try, prune, and backtrack.
• Sets make the lookup O(1), which is much cleaner than scanning the board every time.
• Once you master this, you can extend it to actually return the board configurations instead of just counting them.

---