Every algorithm on this site so far has either followed one deterministic path (searching,
sorting, traversal) or built an answer up from subproblems that are already known to be optimal
(dynamic programming, the greedy MST algorithms). N-Queens needs a different tool: place
N chess queens on an N×N board so that no two share a row, column, or
diagonal. There's no formula for this and no greedy rule that always works — the only sure way
is to try placements and see. Backtracking is the discipline that makes "try
things" tractable: build a candidate one piece at a time, and the instant a partial choice can't
possibly lead anywhere valid, abandon it right there instead of building the rest of the board
first and discovering the problem at the end.
Queens are placed one column at a time. For each column, the demo tries row 0 upward: a row is rejected if it shares a row or diagonal with any queen already placed in an earlier column (no column check is needed — placing exactly one queen per column rules that out by construction). A row that survives gets a queen, and the search moves on to the next column. Once nothing further is left to explore from a placed queen — every row past it dead-ended in conflicts, or a full board was already found and recorded — the search backtracks: undo that queen and resume trying the next row in the same column. Once every row in a column has been tried this way, that undo bubbles up to the column before it, and so on. The light tan cells show every row the current column's already-placed queens would reject — the algorithm still checks each one individually before rejecting it, one at a time; that shading is only there to help you see why, not a shortcut the algorithm itself takes.
Two queens at (row1, col1) and (row2,
col2) attack each other if row1 = row2 (same
row) or |row1 − row2| = |col1 − col2|
(same diagonal — the row gap equals the column gap either direction). Checking a new placement
against every already-placed queen is O(k) for the k-th queen, cheap
compared to the alternative: generate every complete board first, then check it for conflicts.
That alternative is exactly what the demo's own numbers rule out. Assigning any row 0..N−1
independently to each of the N columns, with no early pruning at all, produces NN
candidate boards to check — for the default 5×5 board that's 3,125; backtracking
finds the same 10 solutions after checking only 220 row placements, because it
throws a doomed partial column out the moment a conflict shows up rather than finishing the board
first. The gap widens fast: an 8×8 board has 92 solutions, reachable in 15,720
backtracking attempts against 88 = 16,777,216 full boards
the naive approach would have to build and check — over a thousand times fewer, computed directly
from the same reference implementation below, not estimated.
function solveNQueens(n) {
const solutions = [];
const queens = []; // queens[col] = row of the queen placed in that column
function conflicts(row, col) {
for (let c = 0; c < queens.length; c++) {
const r = queens[c];
if (r === row) return true; // same row
if (Math.abs(r - row) === Math.abs(c - col)) return true; // same diagonal
// no column check needed — one queen per column, by construction
}
return false;
}
function place(col) {
if (col === n) {
solutions.push(queens.slice());
return;
}
for (let row = 0; row < n; row++) {
if (conflicts(row, col)) continue;
queens.push(row);
place(col + 1);
queens.pop(); // backtrack: undo this placement, try the next row
}
}
place(0);
return solutions;
}Forgetting the diagonal check. One-per-column already rules out row and column
collisions being the only things worth checking — it's tempting to check just the row and stop
there. Checked directly against the demo's own 5×5 board: a variant that only compares rows
reports 120 "solutions" instead of the true 10, and its very first result is
[0, 1, 2, 3, 4] — a queen in every row in order, which is a straight diagonal line
where every single queen attacks every other one. Silently wrong, not silently slow.
Backtracking means actually undoing the placement. The queens.pop()
after the recursive call above isn't cleanup, it's load-bearing: skip it and every deeper column's
conflict check keeps seeing queens that should have been removed, so the search either misses real
solutions or corrupts its own state. This is the first backtracking algorithm on the site, and the
lesson generalizes to any future one: whatever state a placement changes to enable checking deeper
choices has to be changed back, in the same place, on every exit path — including the one after a
solution is found, since the search keeps going to find the rest.
More solutions per board isn't guaranteed as N grows. It's easy to assume a bigger board always has room for more solutions. It doesn't: the 6×6 board has only 4 solutions, fewer than the 5×5 board's 10 — a real dip, not a typo (switch the board size selector above and check the stats line yourself). The sequence for N = 1..8 is 1, 0, 0, 2, 10, 4, 40, 92; nothing about it is smooth, and there's no shortcut for knowing it without actually running the search.
Time: exponential in the worst case — pruning cuts the constant factor
dramatically (see the attempt counts above) but doesn't change the underlying order, and there's
no known closed-form or polynomial way to count N-Queens solutions for general N. Space:
O(N) for the queens array and the recursion stack, since only one row
per column is ever held in memory at once — the search never materializes a full board of
candidates, only the current partial one.
The same shape — build a candidate incrementally, check a constraint as early as possible, undo and try the next option the moment it fails — is the general pattern behind Sudoku solvers, graph coloring, and generating permutations under a constraint, not just this one puzzle. See Choosing a Backtracking Strategy for how this page's structural row/column/diagonal check compares to the other nine entries' own rejection rules.