Backtracking: Systematic Search Strategies

Master backtracking techniques to solve constraint satisfaction problems. Learn recursive exploration, pruning strategies, and optimization with implementation examples.

Backtracking Usage (2023)

Puzzles (35%)

Combinatorics (25%)

Optimization (20%)

AI (15%)

Other (5%)

1. Backtracking Fundamentals

Core Principles:

Incremental Build: Construct solutions step-by-step
Constraint Checking: Abandon invalid paths early
State Undo: Revert changes when backtracking
Complete Search: Explores all possibilities

Time Complexities:

Problem	Brute Force	Backtracking
N-Queens	O(nⁿ)	O(n!)
Sudoku	O(9ⁿ)	O(9^m) (m ≈ empty cells)
Subsets	O(n×2ⁿ)	O(2ⁿ)
Permutations	O(n×n!)	O(n!)

General Template:


function backtrack(candidate, state) {
  if (isSolution(candidate, state)) {
    recordSolution(candidate);
    return;
  }
  
  for (const choice of getChoices(state)) {
    if (isValid(choice, state)) {
      makeChoice(choice, state);
      backtrack([...candidate, choice], state);
      undoChoice(choice, state);
    }
  }
}

2. Classic Backtracking Problems

N-Queens Problem


function solveNQueens(n) {
  const result = [];
  const board = Array(n).fill().map(() => Array(n).fill('.'));
  
  function backtrack(row) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (isValidPlacement(board, row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  }
  
  backtrack(0);
  return result;
}

function isValidPlacement(board, row, col) {
  // Check column and diagonals
  for (let i = 0; i < row; i++) {
    if (board[i][col] === 'Q') return false;
    const colDiff = row - i;
    if (board[i][col - colDiff] === 'Q') return false;
    if (board[i][col + colDiff] === 'Q') return false;
  }
  return true;
}

Optimization: Use bitmask for faster validation

Sudoku Solver


function solveSudoku(board) {
  function backtrack() {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] === '.') {
          for (let num = 1; num <= 9; num++) {
            const char = num.toString();
            if (isValid(board, i, j, char)) {
              board[i][j] = char;
              if (backtrack()) return true;
              board[i][j] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  
  backtrack();
}

function isValid(board, row, col, char) {
  for (let i = 0; i < 9; i++) {
    if (board[row][i] === char) return false;
    if (board[i][col] === char) return false;
    const boxRow = 3 * Math.floor(row / 3) + Math.floor(i / 3);
    const boxCol = 3 * Math.floor(col / 3) + (i % 3);
    if (board[boxRow][boxCol] === char) return false;
  }
  return true;
}

Optimization: MRV heuristic (Minimum Remaining Values)

3. Advanced Techniques

Pruning Strategies

Forward Checking


function backtrackWithFC(state, domains) {
  if (isComplete(state)) return state;
  
  const variable = selectUnassignedVariable(state);
  for (const value of orderDomainValues(variable, domains)) {
    if (isConsistent(value, state)) {
      const newDomains = pruneDomains(state, variable, value, domains);
      if (!hasEmptyDomain(newDomains)) {
        state[variable] = value;
        const result = backtrackWithFC(state, newDomains);
        if (result) return result;
        delete state[variable];
      }
    }
  }
  return null;
}

Branch and Bound


let bestSolution = null;
let bestCost = Infinity;

function branchAndBound(state, cost = 0) {
  if (cost >= bestCost) return; // Prune
  
  if (isComplete(state)) {
    bestSolution = [...state];
    bestCost = cost;
    return;
  }
  
  for (const choice of getChoices(state)) {
    const newCost = cost + getCost(choice);
    if (newCost < bestCost) {
      makeChoice(state, choice);
      branchAndBound(state, newCost);
      undoChoice(state, choice);
    }
  }
}

Memoization in Backtracking


const memo = new Map();

function backtrackMemo(state) {
  const key = serializeState(state);
  if (memo.has(key)) return memo.get(key);
  
  if (isSolution(state)) {
    memo.set(key, state);
    return state;
  }
  
  for (const choice of getChoices(state)) {
    makeChoice(state, choice);
    const result = backtrackMemo(state);
    if (result) {
      memo.set(key, result);
      return result;
    }
    undoChoice(state, choice);
  }
  
  memo.set(key, null);
  return null;
}

Backtracking Patterns

Pattern	Example Problems	Key Insight
Combinatorial	Subsets, Combinations	Include/exclude elements
Permutation	String Permutations, N-Queens	Swap and backtrack
Constraint Satisfaction	Sudoku, Graph Coloring	Validate before recursing
Optimization	TSP, Knapsack	Track best solution

4. Real-World Applications

Puzzle Solving

Sudoku/Cryptarithmetic: Systematically explore possibilities

function solveCryptarithmetic(puzzle) {
  const letters = [...new Set(puzzle.join('').replace(/[^A-Z]/g, ''))];
  const usedDigits = new Set();
  // Backtracking solution assigning digits to letters
}

Circuit Design

FPGA Routing: Find valid component placements

function routeFPGA(components, grid) {
  // Backtracking with spatial constraints
}

DNA Sequencing

Fragment Assembly: Reconstruct sequences from overlaps

function assembleDNA(fragments) {
  // Backtracking through possible fragment orders
}

Backtracking Implementation Checklist

✓ Define state representation clearly

✓ Implement efficient isValid() checks

✓ Prune invalid paths early

✓ Clean up state when backtracking

✓ Consider memoization for repeated states

Pro Tip: For optimization problems, combine backtracking with branch-and-bound. Use heuristic ordering (e.g., most constrained variable first) to reduce search space dramatically.

0 Interaction

0 Views

0 Likes