N-Queens - DSA Learning Guide

Overview

The N-Queens problem places n queens on an n x n chessboard so that no two attack each other: no shared row, column, or diagonal. It is the classic constraint-satisfaction backtracking problem.

Place one queen per row. For each row, try each column that is not attacked, recurse to the next row, and remove the queen when backtracking. Tracking attacked columns and diagonals in sets (or bitmasks) makes each safety check O(1). The key insight: all cells on one diagonal share row - col, and all cells on one anti-diagonal share row + col.

Seating rivals at a banquet

You seat one guest per row of tables. Each rival glares along their row, column, and both diagonals. You seat row by row, and when a row has no safe seat, you go back and move the previous guest.

When to use it

Placement problems with conflict rules between items.
Learning how to track constraints efficiently during backtracking.
Any problem where you fill a grid row by row with restrictions.

Problem patterns it solves

Row-by-row placement

Recognize it when: one item per row with column and diagonal conflicts.

51. N-Queens
52. N-Queens II

Grid constraint filling

Recognize it when: fill cells so rows, columns, and boxes stay valid.

37. Sudoku Solver
36. Valid Sudoku

Bitmask constraint tracking

Recognize it when: small n with fast conflict checks.

52. N-Queens II (bitmask)
1240. Tiling a Rectangle with the Fewest Squares

Where it is used in real software

Scheduling with conflicts

Assigning exam slots or rooms so conflicting items never share a slot is the same constraint-propagation idea.

VLSI and layout

Placing components so they do not interfere resembles queen placement with conflict rules.

Benchmarking solvers

N-Queens is a standard benchmark for constraint programming and SAT solvers.

Key terms

Column set: Columns already holding a queen.
Diagonal (row - col): Constant along top-left to bottom-right diagonals.
Anti-diagonal (row + col): Constant along top-right to bottom-left diagonals.
Bitmask: Integers whose bits mark attacked columns and diagonals.

How it works, step by step

1
Place row by row
Each row gets exactly one queen, so rows never conflict.
2
For each column in the row
Check cols, diag (r - c), and antiDiag (r + c) sets.
3
Place the queen
Add c, r - c, r + c to the sets and record the column.
4
Recurse to the next row
If r === n, a full solution is found.
5
Remove the queen
Delete from the sets and try the next column.

Solving 4-Queens

queens[r] = column of the queen in row r

Row	Try column	Result	queens
0	0	place	[0]
1	0, 1 attacked; 2	place	[0, 2]
2	0..3 all attacked	backtrack	[0]
1	3	place	[0, 3]
2	1	place	[0, 3, 1]
3	all attacked	backtrack to row 0	[]
0	1	place	[1]
1..3	3, then 0, then 2	place all	[1, 3, 0, 2]

NOWRow: 0 | Try column: 0 | Result: place | queens: [0]

First solution: [1, 3, 0, 2], shown as .Q.. / ...Q / Q... / ..Q. . The mirror [2, 0, 3, 1] is the only other solution for n = 4.

Implementation

1function solveNQueens(n) {2  const result = [];3  const queens = new Array(n).fill(-1);4  const cols = new Set(), diag = new Set(), anti = new Set();5 6  function place(r) {7    if (r === n) {8      result.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)));9      return;10    }11    for (let c = 0; c < n; c++) {12      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;13      queens[r] = c;14      cols.add(c); diag.add(r - c); anti.add(r + c);15      place(r + 1);16      cols.delete(c); diag.delete(r - c); anti.delete(r + c);17    }18  }19  place(0);20  return result;21}22 23// 52. N-Queens II with bitmasks: counts solutions very fast24function totalNQueens(n) {25  const full = (1 << n) - 1;26  function count(cols, left, right) {27    if (cols === full) return 1;28    let total = 0;29    let free = full & ~(cols | left | right);30    while (free) {31      const bit = free & -free; // lowest free column32      free -= bit;33      total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1);34    }35    return total;36  }37  return count(0, 0, 0);38}

Complexity and performance

TimeO(n!)

Upper bound; pruning makes it much faster in practice.

Safety checkO(1)

Sets, boolean arrays, or bitmasks.

SpaceO(n)

Constraint sets and recursion.

Solutions for n = 892

n = 4 has 2; n = 2 and 3 have none.

Trade-offs

Sets vs arrays vs bitmasks

Sets are readable; boolean arrays are faster; bitmasks are fastest and elegant but harder to read. All give O(1) checks.

Scanning the board for conflicts

Checking attacks by scanning is O(n) per placement; constraint sets remove that cost.

Variants and related techniques

Count only

N-Queens II returns the number of solutions; the bitmask version counts n = 14 quickly.

Symmetry reduction

Only try first-row columns in the left half and double the count (careful with odd n).

Sudoku

Same idea with row, column, and 3 x 3 box constraints and more choices per cell.

Common mistakes

Negative indexes for r - c.
Fix: Offset by n when using arrays: r - c + n.
Forgetting to remove constraints on backtrack.
Fix: Delete from all three sets after the recursive call.
Building strings inside the recursion.
Fix: Build the board strings only when a full solution is found.

Interview questions

Why do r - c and r + c identify diagonals?

Moving down-right increases both r and c by 1, keeping r - c constant. Moving down-left increases r and decreases c, keeping r + c constant.

How would you speed up N-Queens II?

Use bitmasks for columns and both diagonals, extract free positions with bit tricks, and shift the diagonal masks when moving to the next row.

Practice problems

Problem	Difficulty	What it trains
51. N-Queens	Hard	Constraint sets.
52. N-Queens II	Hard	Bitmask counting.
36. Valid Sudoku	Medium	Constraint tracking.
37. Sudoku Solver	Hard	Backtracking with three constraint types.