Solving N-Queens with DFS: From the Backtracking Framework to Bit Manipulation, in Full Detail

Problem Restatement

Place N queens on an N × N chessboard such that no two queens share a row, column, or diagonal. Return all valid arrangements (LeetCode 51) or the count of valid arrangements (LeetCode 52).

For N = 4, there are two solutions:

plaintextCopy

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

The Key Insight: Turn "Place N Queens" into "One Queen per Row"

Brute-forcing every cell means choosing N out of N² squares—the combinations explode. But the problem's constraints hide two pieces of information:

1. There are N queens and N rows—exactly one queen per row
2. Once you place queens row by row, the "different rows" constraint is satisfied automatically

So the problem collapses into a row-by-row decision process: pick a column for row 0, a column for row 1... a column for row N-1. As long as every step satisfies "no column conflicts, no diagonal conflicts," you have a solution when you're done.

This is the state space of DFS (depth-first search): a decision tree of depth N, where level i represents the column choice for row i.

The Three Questions of Backtracking

Before writing any backtracking solution, answer three questions:

Pseudocode skeleton:

plaintextCopy

function backtrack(row): if row === N: record solution; return for col in 0..N-1: if valid(row, col): place(row, col) backtrack(row + 1) undo placement(row, col) # backtracking: return the state to the previous level

The "undo" step is the soul of backtracking—without it, a bad choice on one path pollutes its sibling branches.

Version 1: The Naive Set Check

The most intuitive approach uses three sets to record "already occupied" positions:

tsCopy

function solveNQueensBasic(n: number): string[][] { const queens: number[] = []; // queens[row] = col const cols = new Set<number>(); // occupied columns const diag1 = new Set<number>(); // occupied main diagonals (the \ direction) const diag2 = new Set<number>(); // occupied anti-diagonals (the / direction) const solutions: string[][] = []; const render = () => queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)); const backtrack = (row: number) => { if (row === n) { solutions.push(render()); return; } for (let col = 0; col < n; col++) { // the derivation of the diagonal property is in the next section if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue; queens.push(col); cols.add(col); diag1.add(row - col); diag2.add(row + col); backtrack(row + 1); queens.pop(); cols.delete(col); diag1.delete(row - col); diag2.delete(row + col); } }; backtrack(0); return solutions; }

The three sets correspond to the three types of conflicts; each check is O(1), which is enough for medium sizes. But why can diagonals be identified by row - col and row + col? That's the only piece of math in this problem that requires any thought.

Diagonals: Two Constants

Look at the board coordinates (row, col):

• Main diagonals (the \ direction): cells on the same diagonal share a constant row - col. (0,0), (1,1), and (2,2) all equal 0; (0,3) and (1,4) both equal -3.
• Anti-diagonals (the / direction): cells on the same diagonal share a constant row + col. (0,3), (1,2), (2,1), and (3,0) all equal 3.

So "do two queens' diagonals conflict?" becomes "are the two constant values already occupied?" With N cells there are 2N - 1 diagonals, and each constant governs one direction, so they never get mixed up.

Version 2: Swap Sets for Boolean Arrays

Set has hashing overhead; when the board size is bounded, arrays are more direct:

tsCopy

const cols = new Array<boolean>(n).fill(false); const diag1 = new Array<boolean>(2 * n - 1).fill(false); // row - col ∈ [-(n-1), n-1] const diag2 = new Array<boolean>(2 * n - 1).fill(false); // row + col ∈ [0, 2n-2]

When checking, shift row - col to a non-negative index (row - col + n - 1). This already pushes performance to "good enough," but there's an even more elegant form.

Version 3: Bit Manipulation Compression

Pack the three "occupancy tables" into three integers: bit col set to 1 means column col is occupied. The conflict check goes from "table lookup" to "bitwise AND":

tsCopy

function totalNQueens(n: number): number { let count = 0; const backtrack = (row: number, cols: number, ld: number, rd: number) => { if (row === n) { count++; return; } // In the three bitmaps, a set bit means occupied; after inverting, the set bits are the columns available in this row // (1 << n) - 1 limits the range to the low n bits, avoiding interference from junk bits above let available = ~(cols | ld | rd) & ((1 << n) - 1); while (available) { // lowbit: pick the lowest available column const pick = available & -available; available ^= pick; // remove it from the available set backtrack( row + 1, cols | pick, // the column is occupied (ld | pick) << 1, // left diagonal: shift everything left by one for the next row (rd | pick) >> 1, // right diagonal: shift everything right by one for the next row ); } }; backtrack(0, 0, 0, 0); return count; }

Three tricks, all at once:

1. ~(cols | ld | rd)—OR the three occupancy bitmaps and invert: the remaining 1s are this row's available columns. & ((1 << n) - 1) chops off the high bits.
2. available & -available—extract the lowest set bit (lowbit), i.e. the leftmost available column.
3. The diagonals move with the walk: each row down, the main diagonal's affected positions shift left by one column (<< 1), and the anti-diagonal shifts right (>> 1). This even saves the row - col arithmetic—the shifts are the geometry of the diagonals.

Tracing n = 4 by Hand

Walk through it with version 3's logic (following only one successful path; the code explores column 0 first in lowbit order, that branch has no solution, and the first complete solution it finds is the one in the table below):

In rows 2 and 3 of the table, the ld/rd values contain bits beyond 4 bits (like 11000); they come from the previous row's << 1 overflow and don't affect the result—the trailing & ((1 << n) - 1) in the available computation zeroes the high bits, so only the low 4 bits participate in the check.

The placement sequence [1, 3, 0, 2] is the first solution. Other branches of the search tree will naturally backtrack when they hit a row where available === 0 (no usable columns).

Complexity

• Time complexity: O(N!) order—row 0 has at most N choices, row 1 at most N-2 (subtracting column and diagonal conflicts)... the exact upper bound is N!, though pruning brings it far below that in practice.
• Space complexity: O(N)—recursion depth N, and the three bitmaps take constant space.

Common Mistakes Checklist

1. Mixing up the diagonal directions: confusing row - col and row + col passes small tests but misses solutions at scale. The safest fix is to derive it on the spot with the two points (1,1) and (0,3).
2. Forgetting to undo state: a missing cols.delete(col) pollutes all sibling branches; results are wrong or the search hangs.
3. The bitwise version doesn't limit bit width: ~(cols | ld | rd) in a 32-bit integer sets all high bits to 1; without & ((1 << n) - 1), it places queens on columns that don't exist.
4. Output format: LeetCode requires returning a string board; watch the boundaries of ".".repeat() and don't splice the Q outside the columns.

Summary

N-Queens is the "standard teaching case" of backtracking: it's small enough to trace by hand, yet deep enough to optimize all the way down to bit manipulation. The real takeaway isn't this specific problem, but the general framework—model the problem as layer-by-layer decisions, prune with occupancy state, backtrack by undoing state. When you later tackle permutation, Sudoku, or subset problems, it's the same machine with different parts.