The N-Queens puzzle is the problem of placing $N$ chess queens on an $N \times N$ chessboard so that no two queens threaten each other. This is the "Godfather" of backtracking problems.

Think of Jealous Socialites:

1. You have a party with $N$ socialites (Queens) and $N$ tables.
2. Every socialite wants their own row, their own column, and their own diagonal. They refuse to share!
3. You place socialite 1 in the first column.
4. Then you try a spot for socialite 2. If she's "threatened" by socialite 1, she complains! You have to move her.
5. If you run out of spots for socialite 2, it means socialite 1 was in the wrong place! You have to go back and move socialite 1.

---

Constraints

A queen at (r, c) threatens:

1. Every cell in row r. (Solved by placing only 1 queen per row).
2. Every cell in column c.
3. Every cell on the Positive Diagonal (r + c is constant).
4. Every cell on the Negative Diagonal (r - c is constant).

Optimization ($O(1)$ Checks)

Instead of scanning the whole board to check if a spot is safe, keep Sets for columns and diagonals.

• Cols: Set of $c$ indices.
• Positive Diagonals: Set of $r + c$.
• Negative Diagonals: Set of $r - c$.

---

javascript Standard
/**
 * N-Queens Count Solver
 */
function totalNQueens(n) {
  let solutions = 0;
  const cols = new Set();
  const posDiag = new Set(); // (r + c)
  const negDiag = new Set(); // (r - c)

  function backtrack(r) {
    if (r === n) {
      solutions++;
      return;
    }

    for (let c = 0; c < n; c++) {
      if (cols.has(c) || posDiag.has(r + c) || negDiag.has(r - c)) {
        continue;
      }

      // 1. PLACE
      cols.add(c);
      posDiag.add(r + c);
      negDiag.add(r - c);

      // 2. RECURSE
      backtrack(r + 1);

      // 3. REMOVE (BACKTRACK)
      cols.delete(c);
      posDiag.delete(r + c);
      negDiag.delete(r - c);
    }
  }

  backtrack(0);
  return solutions;
}

console.log(totalNQueens(4)); // Output: 2

---

Complexity

• Time: $O(N!)$. We try $N$ spots for the first row, $N-2$ for the second, etc.
• Space: $O(N)$ to store the sets and recursion stack.

Key Observation

The board itself is rarely needed in the calculation! You can solve the problem just by tracking the restricted indices.

Related Problems

• Sudoku Solver: A more complex 2D backtracking grid.
• Word Search: Navigating a 2D grid of characters.
• Knight’s Tour: Visiting every square on a chessboard exactly once.