N-Queens

BACKTRACKING · HARD

Builds on Day 9: Recursion & the Call Stack

Both solutions below are recursive backtracking searches over board rows; read that lesson first if recursive call stacks are still new.

The problem

The n-queens puzzle is the problem of placing n queens on an n × n chessboard so that no two queens attack each other — meaning no two share a row, a column, or a diagonal. Given n, return all distinct solutions, each represented as a board where 'Q' marks a queen and '.' marks an empty space.

Solution 1: Brute force — try every column in every row, validate only at the end

Place a queen in some column of every row, trying all n columns per row with no regard for conflicts, and only check whether the FULL board is valid once every row has a queen. This animation deliberately uses a 3×3 board instead of 4×4 — n=3 has zero valid solutions (same as n=2, a well-known fact), which keeps the fully unpruned search small enough to watch (~66 steps) while still honestly demonstrating exhaustive brute-force search reaching the mathematically correct answer, “no solution exists.”

Brute force: place any column, validate the FULL board at the end
    ↓
place any column  →  recurse to the next row  →  check FULL board now
(no conflict check)  (repeat for every row)      (validate every pair)

Cost: O(n^n) placements explored before any conflict is ever caught.

Interactive visualization

queen just placed valid final board full board checked, invalid

3×3 board — no valid solution exists

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

This animation uses a 3×3 board (n=3) — no valid solution exists at this size, so watch it exhaustively try everything and correctly conclude there’s none. The optimal solution below uses n=4, where real solutions exist.

The code

function solveNQueensBrute(n) {
  const result = [];
  function dfs(row, board) {
    if (row === n) {
      let ok = true;
      for (let r = 0; r < n && ok; r++) for (let r2 = r + 1; r2 < n && ok; r2++)
        if (board[r] === board[r2] || Math.abs(board[r] - board[r2]) === Math.abs(r - r2)) ok = false;
      if (ok) result.push(board.map(c => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)));
      return;
    }
    for (let col = 0; col < n; col++) { board.push(col); dfs(row + 1, board); board.pop(); }
  }
  dfs(0, []);
  return result;
}

Line by line:

• board is built up one row at a time — board[row] is which column that row’s queen sits in.
• Every column is tried in every row unconditionally — there’s no check on whether a choice conflicts with an already-placed queen.
• Only once row === n (a full board exists) does the code check every PAIR of placed queens for same-column or same-diagonal conflicts (Math.abs(board[r] - board[r2]) === Math.abs(r - r2) catches diagonal attacks — the column difference equals the row difference exactly when two positions sit on the same diagonal).

Complexity

Metric	Value
Time	O(n^n) placements explored
Space	O(n) recursion depth

Solution 2: Optimal — track used columns/diagonals, prune before placing

Instead of waiting until the end, track which columns and which diagonals are already occupied as you go — the moment a column choice would conflict with an existing queen, skip it immediately, with zero extra recursion.

Optimal: track used columns/diagonals, prune before placing
    ↓
column/diagonal used?        →  skip — no recursion  →  otherwise: place + recurse
(3 Sets track this in O(1))     (if conflict found)     (then backtrack after)

Cost: conflicting branches never get explored at all.

Interactive visualization

queen just placed valid final board column/diagonal conflict — skip, no recursion

4×4 board — 2 valid solutions exist

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

This animation uses a 4×4 board (n=4) — the smallest board size with real solutions, and it finds both of them.

The code

function solveNQueensOptimal(n) {
  const result = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  const board = [];
  function dfs(row) {
    if (row === n) { result.push(board.map(c => ".".repeat(c) + "Q" + ".".repeat(n - c - 1))); return; }
    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); board.push(col);
      dfs(row + 1);
      board.pop(); cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }
  dfs(0);
  return result;
}

Line by line:

• cols tracks occupied columns directly. diag1 tracks row - col, which is CONSTANT along every “"-direction diagonal — any two cells on the same “" diagonal share the same row - col value. diag2 tracks row + col, constant along every “/”-direction diagonal.
• if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue is the entire optimization — an O(1) check per column, skipping instantly instead of recursing into a doomed branch.
• After the recursive call returns, all three sets get the current column’s entries DELETED — this is the backtrack step, undoing the placement so the next column choice in this row sees a clean state.

Complexity

Metric	Value
Time	Much smaller than O(n^n) — commonly cited near O(n!) in practice
Space	O(n) for the board plus the 3 Sets

Complexity comparison

Solution	Board size used	Placements explored
Brute force (unpruned)	3×3 (0 solutions exist)	Up to O(n^n)
Optimal (pruned)	4×4 (2 solutions exist)	Far fewer — conflicting branches never recursed into

This IS a genuine asymptotic improvement, not just a constant-factor speedup — pruning a conflicting column cuts off its ENTIRE remaining subtree before it’s ever explored, which compounds across every row below it.

Interview corner

Q: How would you count the number of solutions without generating and storing every board?

• Keep the exact same pruning logic.
• Increment a plain counter at the base case instead of building and pushing a board string.
• This saves the O(n²) cost of rendering each solution when only the COUNT is actually needed.

Q: How would you adapt this to solve N-Rooks instead of N-Queens?

• Rooks only attack along rows and columns, never diagonally.
• So you’d only need the cols set — drop both diagonal sets entirely.
• That also makes N-Rooks a strictly easier pruning problem than N-Queens.

Q: Why does the optimal solution’s pruning check happen BEFORE placing a queen, not after?

• Checking before means an invalid column is skipped with zero extra work — no recursive call, no stack frame, no wasted exploration of everything beneath that bad placement.
• Checking only after (like the brute-force version does, at the very end) means the entire wasted subtree gets fully explored first.

Q: Trick question — what does this log?

const s = new Set([NaN]);
console.log(s.has(NaN), NaN === NaN);

• Answer: true, then false.
• Set (and Map) use an algorithm called SameValueZero for equality checks, which treats NaN as equal to itself — unlike strict equality (===), which never considers NaN equal to ANYTHING, including itself.
• ⚠ Trap: This matters directly here — the optimal solution above relies heavily on Set.has() checks (cols.has(col), diag1.has(row - col), etc.). Sets have their own specific equality rules, separate from === — worth knowing precisely when reasoning about what a Set-based conflict check will and won’t catch.

Quiz

Quiz 1: Why does the brute-force solution have to wait until a full board is placed before checking validity?

It doesn’t track column/diagonal usage incrementally — it only knows how to check a COMPLETE board

Quiz 2: What do the diag1 and diag2 sets represent in the optimal solution?

The two families of diagonals a queen attacks: row − col constant on “", row + col constant on “/”

Quiz 3: Why does checking cols.has(col) alone not fully prevent queens from attacking each other?

Two queens in different rows/columns can still attack diagonally — column-only checking misses that

Quiz 4: The 3×3 board’s brute-force animation explores every placement and finds zero solutions — is that a bug?

No — no valid arrangement exists for n=2 or n=3, a well-known mathematical fact

Quiz 5: What’s the complexity difference between the two solutions?

Brute force is up to O(n^n); optimal prunes immediately and visits far fewer nodes — near O(n!) in practice