Backtracking

Build an answer one choice at a time; the instant a choice can't lead anywhere valid, undo it and try the next — a pruned depth-first walk of the decision tree.

9 min read Watch it move Build it

Backtracking builds a solution one decision at a time, and the moment a choice makes the rest impossible it undoes that choice and tries the next one. It's a depth-first search of the tree of possibilities that abandons dead branches early instead of grinding through every full combination. The classic example is N-Queens: place queens on a chessboard row by row so no two can attack each other.

The three moves: choose, explore, un-choose

1Choose — make the next decision (place a queen in some column of the current row).
2Explore — recurse to decide the rest, assuming this choice sticks.
3Prune — before recursing, check the choice is still legal; if it violates a constraint, skip it entirely.
4Backtrack — when a branch dead-ends (no legal choice remains), *un-choose* the last decision and let the loop try the next option.

Prune early, prune often

The whole speedup comes from pruning: cutting off a branch the instant it's clearly hopeless. A partial N-Queens board with two queens on the same diagonal can never be completed, so backtracking abandons it immediately rather than filling in the remaining rows.

A real trace: 4-Queens

Place one queen per row, left to right, on a 4×4 board. Columns are numbered 0–3.

1Row 0: place a queen at column 0.
2Row 1: columns 0 and 1 are attacked (same column / diagonal), so place at column 2.
3Row 2: every column is attacked by the queens above — dead end. Backtrack to row 1.
4Row 1: try the next legal column, 3. Place there.
5Row 2: column 1 is free — place there.
6Row 3: all four columns are attacked — dead end. Backtrack up… row 2 and row 1 are exhausted, so backtrack all the way to row 0.
7Row 0: try column 1 instead. This branch succeeds: queens end at columns (1, 3, 0, 2) — a valid solution.

Always undo what you did

The un-choose step is easy to forget. If you place a queen (or add to a subset) before recursing, you must remove it after the recursive call returns — otherwise the *sibling* branches inherit stale state and produce wrong answers.

function solveNQueens(n) {
  const cols = [];              // cols[r] = column of the queen in row r
  const solutions = [];

  function safe(row, col) {
    for (let r = 0; r < row; r++) {
      const c = cols[r];
      if (c === col) return false;                 // same column
      if (Math.abs(c - col) === row - r) return false; // same diagonal
    }
    return true;
  }

  function place(row) {
    if (row === n) { solutions.push([...cols]); return; } // base case
    for (let col = 0; col < n; col++) {
      if (!safe(row, col)) continue; // prune illegal choices
      cols.push(col);                // choose
      place(row + 1);                // explore
      cols.pop();                    // un-choose (backtrack)
    }
  }

  place(0);
  return solutions;
}

OperationTimeSpace

Worst case · N choices, then N−1, … before pruningO(N!)O(N)

With pruning · recursion depth = NFar below N! in practiceO(N)

Check yourself

When a partial placement can't be completed into a valid solution, backtracking…