Backtracking

Place four queens on a 4×4 chessboard so that no two can attack each other. A queen attacks along her row, her column, and both diagonals.

Have a go on paper. It is fiddly, and the fiddliness is the point — you will notice yourself putting a queen down, discovering it does not work, and taking it back. That taking-it-back is the entire technique.

The obvious way is unthinkable

Four queens on sixteen squares is 1,820 arrangements. Checkable. Eight queens on an 8×8 board is 4.4 billion, and 8×8 is the version you will actually be asked.

// Do not write this.
for (const arrangement of everyPossibleArrangement(board, queens)) {
  if (noneAttack(arrangement)) return arrangement;
}

It is not just slow — it is stupidly slow, because it keeps generating arrangements whose first two queens already attack each other. Once those two are wrong, every one of the millions of arrangements below them is wrong too, and this loop checks each one individually.

The realisation

Build the answer one piece at a time, and check as you go.

Each row holds exactly one queen, so place them row by row. Before placing a queen, ask whether she is attacked by any queen already on the board. If she is, do not place her — and do not explore anything that would have followed.

Watch it run. The red × marks are the rejections:

The shape of the code

Every backtracking solution looks like this. Learn the shape and you can write any of them:

function solve(partial: State): boolean {
  if (isComplete(partial)) return true;          // 1. done?

  for (const move of candidateMoves(partial)) {
    if (!isLegal(partial, move)) continue;       // 2. prune

    apply(partial, move);                        // 3. choose
    if (solve(partial)) return true;             // 4. recurse
    undo(partial, move);                         // 5. un-choose
  }

  return false;                                  // 6. dead end
}

Choose, recurse, un-choose. That undo is the “backtrack”, and it is what lets one partial object serve the entire search instead of copying the board at every step.

For N-queens, partial is just a list of column numbers:

function queens(n: number): number[] | null {
  const cols: number[] = [];        // cols[r] = the column of row r's queen

  function place(row: number): boolean {
    if (row === n) return true;

    for (let col = 0; col < n; col += 1) {
      // Same column, or same diagonal — equal row-gap and column-gap.
      const attacked = cols.some(
        (c, r) => c === col || Math.abs(c - col) === row - r,
      );
      if (attacked) continue;

      cols.push(col);
      if (place(row + 1)) return true;
      cols.pop();                    // ← the backtrack
    }

    return false;
  }

  return place(0) ? cols : null;
}

Because each row gets exactly one entry, rows and columns can never clash by construction. The only real check is the diagonal one, and that test is the neat part: two queens share a diagonal exactly when the vertical gap equals the horizontal gap.

Why the shape recurs

The same five lines solve a surprising number of things:

Two of those have no pruning at all, and it is worth seeing why that is fine. Generating every subset must take $2^n$ steps, because there are $2^n$ answers. Backtracking is not slow there; the output is just large.

Making the prune stronger

Since all the speed comes from rejecting early, the way to go faster is to reject earlier.

Order the candidates. In Sudoku, fill the cell with the fewest legal digits first. A cell with one option is a free move; a cell with none is a contradiction you have found immediately instead of ten levels down.

Look ahead. After placing a queen, check whether some later row now has zero legal columns. If so this branch is already dead — stop now rather than discovering it after five more placements.

Check incrementally. The cols.some(...) above rescans every placed queen. Three boolean arrays — one per column, one per ↘ diagonal, one per ↙ — make the test $O(1)$:

const attacked = usedCol[col] || usedDiag1[row - col + n] || usedDiag2[row + col];

row - col is constant along a ↘ diagonal and row + col along a ↙ one. The + n is only there to keep the index non-negative.

When to reach for it

Backtracking is the answer when you must construct something subject to constraints, and you can tell part-way through that a partial construction is already doomed.

If you cannot judge a partial answer — if legality only becomes visible at the very end — there is nothing to prune and you are back to brute force. And if the problem asks for a count or an optimum over overlapping subproblems rather than one valid arrangement, you probably want dynamic programming, which remembers instead of retrying.