patternjavascriptModerate

Backtracking: prune the search tree early to avoid exponential blowup

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

backtrackingn-queenssudokupermutationssubsetspruningconstraint

Problem

Problems like N-Queens, Sudoku, permutations, and subsets have exponential search spaces. Naive generate-then-filter is too slow. Backtracking prunes invalid branches before expanding them.

Solution

Backtracking builds a solution incrementally. At each step, check if the current partial solution is still valid before recursing. If invalid, return immediately (prune). Undo the last choice before trying the next alternative (backtrack).

Why

A good constraint check eliminates entire subtrees early. For N-Queens, checking column and diagonal conflicts prunes orders of magnitude of states. The key is that pruning must be cheap relative to what it eliminates.

Gotchas

Always undo state changes after recursion — push/pop, add/delete, mark/unmark
For combinatorics (subsets, permutations), pass a start index to avoid duplicate combinations
Constraint propagation (as in Sudoku solvers) is backtracking enhanced with forward checking

Code Snippets

Subsets and N-Queens with backtracking

// Generate all subsets (power set) using backtracking
function subsets(nums) {
  const result = [];
  function bt(start, current) {
    result.push([...current]);
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      bt(i + 1, current);
      current.pop(); // backtrack
    }
  }
  bt(0, []);
  return result;
}

// N-Queens backtracking
function solveNQueens(n) {
  const results = [], cols = new Set(), diag1 = new Set(), diag2 = new Set();
  function place(row, board) {
    if (row === n) { results.push(board.map(r => '.'.repeat(r) + 'Q' + '.'.repeat(n-r-1))); return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag1.has(row-c) || diag2.has(row+c)) continue;
      cols.add(c); diag1.add(row-c); diag2.add(row+c); board.push(c);
      place(row+1, board);
      cols.delete(c); diag1.delete(row-c); diag2.delete(row+c); board.pop();
    }
  }
  place(0, []);
  return results;
}

Context

Combinatorial search, constraint satisfaction, generating permutations or subsets

Revisions (0)

No revisions yet.