Backtracking

Overview

Backtracking is a general algorithmic approach for finding solutions to computational problems that involve searching through a space of possible solutions. The algorithm builds candidates incrementally and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot lead to a valid solution.

The technique applies to problems where the solution consists of a sequence of choices, and each choice has a finite set of options. Backtracking explores the decision tree by making a choice, recursively exploring the consequences, and undoing the choice if it leads to failure. This systematic exploration continues until a solution is found or all possibilities are exhausted.

Common applications include solving puzzles (Sudoku, N-Queens, crosswords), constraint satisfaction problems, combinatorial optimization, parsing, and pathfinding in graphs. The algorithm serves as the foundation for many problem-solving techniques in artificial intelligence, operations research, and computer science.

Backtracking differs from brute force by pruning branches of the search tree early when constraints are violated, making it more efficient than exhaustive enumeration. The algorithm maintains state during exploration and restores it when backtracking, which distinguishes it from simple trial-and-error approaches.

# Simple backtracking template
def backtrack(state, choices)
  return state if goal_reached?(state)
  
  choices.each do |choice|
    if valid?(state, choice)
      make_choice(state, choice)
      result = backtrack(state, remaining_choices)
      return result if result
      undo_choice(state, choice)
    end
  end
  
  nil
end

Key Principles

Backtracking operates on three fundamental principles: incremental construction, constraint checking, and systematic exploration.

Incremental Construction builds solutions piece by piece rather than generating complete candidates upfront. At each step, the algorithm extends a partial solution with one additional component. This partial solution represents a node in the search tree, and each possible extension creates a child node. The incremental approach allows the algorithm to detect failures early without constructing the entire solution.

Constraint Checking evaluates whether a partial solution can lead to a complete valid solution. The algorithm applies constraints at each step to prune branches that cannot succeed. Early constraint checking is critical for performance—detecting violations immediately prevents exploring the entire subtree rooted at an invalid partial solution. Constraints can be explicit (hard rules that must be satisfied) or implicit (heuristics that guide the search).

Systematic Exploration ensures all valid solutions can be found through depth-first traversal of the solution space. The algorithm explores one branch completely before moving to the next, maintaining a stack (either explicitly or through recursion) of decision points. When a branch fails, the algorithm backtracks to the most recent decision point and tries the next option.

The backtracking process follows a specific pattern:

1. Choose an unassigned component of the solution
2. Try each possible value for that component
3. For each value, check if it violates any constraints
4. If valid, recursively attempt to complete the solution
5. If recursion succeeds, return the solution
6. If recursion fails, undo the choice and try the next value
7. If all values fail, backtrack to the previous decision

# Backtracking state management
class BacktrackState
  attr_reader :path, :visited
  
  def initialize
    @path = []
    @visited = Set.new
  end
  
  def add(item)
    @path << item
    @visited.add(item)
  end
  
  def remove
    item = @path.pop
    @visited.delete(item)
    item
  end
  
  def valid?(item)
    !@visited.include?(item)
  end
end

The efficiency of backtracking depends on the order of choices and the effectiveness of constraint checking. Choosing variables with fewer legal values first (most constrained variable heuristic) reduces the branching factor. Similarly, ordering values from most to least likely to succeed (least constraining value heuristic) increases the probability of finding solutions quickly.

Backtracking naturally handles problems with multiple solutions by continuing the search after finding the first solution. The algorithm can collect all solutions, find the optimal solution according to some criterion, or stop at the first valid solution depending on requirements.

Ruby Implementation

Ruby's support for blocks, recursion, and dynamic arrays makes it well-suited for implementing backtracking algorithms. The language's expressiveness allows clean separation of the backtracking framework from problem-specific logic.

Basic Recursive Backtracking

class Backtracker
  def solve(initial_state, &block)
    backtrack(initial_state, &block)
  end
  
  private
  
  def backtrack(state, &block)
    return state if block.call(:goal?, state)
    
    choices = block.call(:choices, state)
    choices.each do |choice|
      if block.call(:valid?, state, choice)
        block.call(:apply, state, choice)
        result = backtrack(state, &block)
        return result if result
        block.call(:revert, state, choice)
      end
    end
    
    nil
  end
end

# Usage example: Finding a path in a graph
graph = {
  'A' => ['B', 'C'],
  'B' => ['D', 'E'],
  'C' => ['F'],
  'D' => [],
  'E' => ['F'],
  'F' => []
}

solver = Backtracker.new
start, target = 'A', 'F'

result = solver.solve([start]) do |action, state, choice = nil|
  case action
  when :goal?
    state.last == target
  when :choices
    graph[state.last] || []
  when :valid?
    !state.include?(choice)
  when :apply
    state << choice
  when :revert
    state.pop
  end
end

# => ["A", "C", "F"]

Iterative Backtracking with Explicit Stack

Ruby can implement backtracking iteratively using an explicit stack, which avoids recursion depth limits and provides more control over the search process.

class IterativeBacktracker
  def solve(initial_state)
    stack = [[initial_state, choices_for(initial_state), 0]]
    
    until stack.empty?
      state, choices, index = stack.last
      
      if goal_reached?(state)
        return state
      end
      
      if index >= choices.size
        stack.pop
        next
      end
      
      choice = choices[index]
      stack.last[2] += 1
      
      if valid_choice?(state, choice)
        new_state = apply_choice(state, choice)
        new_choices = choices_for(new_state)
        stack << [new_state, new_choices, 0]
      end
    end
    
    nil
  end
  
  def choices_for(state)
    raise NotImplementedError
  end
  
  def goal_reached?(state)
    raise NotImplementedError
  end
  
  def valid_choice?(state, choice)
    raise NotImplementedError
  end
  
  def apply_choice(state, choice)
    raise NotImplementedError
  end
end

Generator-Based Solution Enumeration

Ruby's Enumerator class enables lazy generation of all solutions without storing them in memory simultaneously.

class SolutionGenerator
  def all_solutions(state)
    Enumerator.new do |yielder|
      generate_solutions(state, yielder)
    end
  end
  
  private
  
  def generate_solutions(state, yielder)
    if complete?(state)
      yielder << state.dup
      return
    end
    
    next_choices(state).each do |choice|
      if valid?(state, choice)
        apply(state, choice)
        generate_solutions(state, yielder)
        revert(state, choice)
      end
    end
  end
  
  # Problem-specific methods
  def complete?(state); raise NotImplementedError; end
  def next_choices(state); raise NotImplementedError; end
  def valid?(state, choice); raise NotImplementedError; end
  def apply(state, choice); raise NotImplementedError; end
  def revert(state, choice); raise NotImplementedError; end
end

# Example: Generate all permutations
class PermutationGenerator < SolutionGenerator
  def initialize(elements)
    @elements = elements
  end
  
  def complete?(state)
    state.size == @elements.size
  end
  
  def next_choices(state)
    @elements - state
  end
  
  def valid?(state, choice)
    !state.include?(choice)
  end
  
  def apply(state, choice)
    state << choice
  end
  
  def revert(state, choice)
    state.pop
  end
end

gen = PermutationGenerator.new([1, 2, 3])
gen.all_solutions([]).first(6)
# => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Constraint Propagation Integration

Advanced backtracking implementations combine constraint checking with constraint propagation to reduce the search space further.

class ConstraintBacktracker
  attr_reader :domains
  
  def initialize(variables, initial_domains)
    @variables = variables
    @domains = initial_domains.dup
    @assignments = {}
  end
  
  def solve
    backtrack_with_propagation
  end
  
  private
  
  def backtrack_with_propagation
    return @assignments.dup if complete?
    
    var = select_unassigned_variable
    ordered_values(var).each do |value|
      if consistent?(var, value)
        assign(var, value)
        saved_domains = save_domains
        
        if propagate_constraints(var, value)
          result = backtrack_with_propagation
          return result if result
        end
        
        restore_domains(saved_domains)
        unassign(var)
      end
    end
    
    nil
  end
  
  def complete?
    @assignments.size == @variables.size
  end
  
  def select_unassigned_variable
    # Most constrained variable heuristic
    (@variables - @assignments.keys).min_by { |v| @domains[v].size }
  end
  
  def ordered_values(var)
    # Least constraining value heuristic
    @domains[var].sort_by { |val| count_conflicts(var, val) }
  end
  
  def assign(var, value)
    @assignments[var] = value
    @domains[var] = [value]
  end
  
  def unassign(var)
    @assignments.delete(var)
  end
  
  def save_domains
    @domains.transform_values(&:dup)
  end
  
  def restore_domains(saved)
    @domains = saved
  end
  
  def propagate_constraints(var, value)
    # Problem-specific constraint propagation
    true
  end
  
  def consistent?(var, value)
    # Problem-specific consistency check
    true
  end
  
  def count_conflicts(var, value)
    # Problem-specific conflict counting
    0
  end
end

Practical Examples

N-Queens Problem

The N-Queens problem places N chess queens on an N×N chessboard such that no two queens attack each other. This classic backtracking problem demonstrates constraint checking and state management.

class NQueens
  def initialize(n)
    @n = n
    @solutions = []
  end
  
  def solve
    solve_recursive([], 0)
    @solutions
  end
  
  private
  
  def solve_recursive(queens, row)
    if row == @n
      @solutions << queens.dup
      return
    end
    
    @n.times do |col|
      if safe?(queens, row, col)
        queens << col
        solve_recursive(queens, row + 1)
        queens.pop
      end
    end
  end
  
  def safe?(queens, row, col)
    queens.each_with_index do |queen_col, queen_row|
      # Same column
      return false if queen_col == col
      
      # Diagonal
      return false if (row - queen_row).abs == (col - queen_col).abs
    end
    true
  end
end

solver = NQueens.new(4)
solutions = solver.solve
# => [[1, 3, 0, 2], [2, 0, 3, 1]]
# Two solutions: queens at columns [1,3,0,2] and [2,0,3,1] for rows 0-3

# Visualize first solution
def print_board(solution)
  n = solution.size
  solution.each do |col|
    row = Array.new(n, '.')
    row[col] = 'Q'
    puts row.join(' ')
  end
end

print_board(solutions.first)
# . Q . .
# . . . Q
# Q . . .
# . . Q .

Sudoku Solver

Sudoku solving demonstrates backtracking with multiple constraint types and cell selection strategies.

class SudokuSolver
  def initialize(board)
    @board = board.map(&:dup)
    @size = 9
    @box_size = 3
  end
  
  def solve
    return @board if solve_recursive
    nil
  end
  
  private
  
  def solve_recursive
    row, col = find_empty_cell
    return true unless row
    
    (1..@size).each do |num|
      if valid_placement?(row, col, num)
        @board[row][col] = num
        return true if solve_recursive
        @board[row][col] = 0
      end
    end
    
    false
  end
  
  def find_empty_cell
    # Most constrained cell first
    best_cell = nil
    min_options = @size + 1
    
    @size.times do |row|
      @size.times do |col|
        next if @board[row][col] != 0
        
        options = count_valid_options(row, col)
        if options < min_options
          min_options = options
          best_cell = [row, col]
          return best_cell if options == 1  # Only one option, use it
        end
      end
    end
    
    best_cell
  end
  
  def count_valid_options(row, col)
    (1..@size).count { |num| valid_placement?(row, col, num) }
  end
  
  def valid_placement?(row, col, num)
    # Check row
    return false if @board[row].include?(num)
    
    # Check column
    return false if @board.any? { |r| r[col] == num }
    
    # Check 3x3 box
    box_row = (row / @box_size) * @box_size
    box_col = (col / @box_size) * @box_size
    
    @box_size.times do |i|
      @box_size.times do |j|
        return false if @board[box_row + i][box_col + j] == num
      end
    end
    
    true
  end
end

# Example puzzle (0 represents empty cell)
puzzle = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solver = SudokuSolver.new(puzzle)
solution = solver.solve

Subset Sum Problem

Finding subsets of numbers that sum to a target value demonstrates backtracking with numeric constraints and optimization opportunities.

class SubsetSum
  def initialize(numbers, target)
    @numbers = numbers.sort.reverse  # Larger numbers first
    @target = target
    @solutions = []
  end
  
  def find_all
    backtrack([], 0, 0)
    @solutions
  end
  
  def find_one
    backtrack_first([], 0, 0)
  end
  
  private
  
  def backtrack(subset, sum, start_idx)
    if sum == @target
      @solutions << subset.dup
      return
    end
    
    return if sum > @target  # Prune: exceeded target
    
    start_idx.upto(@numbers.size - 1) do |i|
      num = @numbers[i]
      
      # Prune: remaining numbers too small
      remaining = @numbers[i..-1].sum
      break if sum + remaining < @target
      
      subset << num
      backtrack(subset, sum + num, i + 1)
      subset.pop
    end
  end
  
  def backtrack_first(subset, sum, start_idx)
    return subset.dup if sum == @target
    return nil if sum > @target
    
    start_idx.upto(@numbers.size - 1) do |i|
      num = @numbers[i]
      
      subset << num
      result = backtrack_first(subset, sum + num, i + 1)
      return result if result
      subset.pop
    end
    
    nil
  end
end

solver = SubsetSum.new([3, 34, 4, 12, 5, 2], 9)
solver.find_all
# => [[4, 5], [4, 3, 2], [7, 2]]

# With optimization: finding subset closest to target
class SubsetSumClosest < SubsetSum
  def find_closest
    @best = nil
    @best_diff = Float::INFINITY
    backtrack_closest([], 0, 0)
    @best
  end
  
  private
  
  def backtrack_closest(subset, sum, start_idx)
    diff = (@target - sum).abs
    if diff < @best_diff
      @best_diff = diff
      @best = subset.dup
    end
    
    return if sum >= @target  # Don't exceed target
    
    start_idx.upto(@numbers.size - 1) do |i|
      subset << @numbers[i]
      backtrack_closest(subset, sum + @numbers[i], i + 1)
      subset.pop
    end
  end
end

Word Break Problem

Determining if a string can be segmented into dictionary words demonstrates backtracking with memoization for overlapping subproblems.

class WordBreak
  def initialize(dictionary)
    @dictionary = Set.new(dictionary)
    @max_length = dictionary.map(&:length).max
  end
  
  def segment(text)
    backtrack(text, 0, [])
  end
  
  def all_segments(text)
    solutions = []
    backtrack_all(text, 0, [], solutions)
    solutions
  end
  
  private
  
  def backtrack(text, start, words)
    return words if start == text.length
    
    # Try all possible next words
    (start + 1).upto([start + @max_length, text.length].min) do |end_pos|
      word = text[start...end_pos]
      if @dictionary.include?(word)
        words << word
        result = backtrack(text, end_pos, words)
        return result if result
        words.pop
      end
    end
    
    nil
  end
  
  def backtrack_all(text, start, words, solutions)
    if start == text.length
      solutions << words.dup
      return
    end
    
    (start + 1).upto([start + @max_length, text.length].min) do |end_pos|
      word = text[start...end_pos]
      if @dictionary.include?(word)
        words << word
        backtrack_all(text, end_pos, words, solutions)
        words.pop
      end
    end
  end
end

dict = ['cat', 'cats', 'and', 'sand', 'dog']
solver = WordBreak.new(dict)

solver.segment('catsanddog')
# => ['cats', 'and', 'dog']

solver.all_segments('catsanddog')
# => [['cats', 'and', 'dog'], ['cat', 'sand', 'dog']]

Common Patterns

Choice Point Management

Managing decision points requires careful state handling. The choice point pattern encapsulates the state before making a decision, enabling rollback.

class ChoicePoint
  attr_reader :variable, :value, :state_snapshot
  
  def initialize(variable, value, state_snapshot)
    @variable = variable
    @value = value
    @state_snapshot = state_snapshot
  end
end

class StatefulBacktracker
  def initialize
    @choice_stack = []
    @state = {}
  end
  
  def make_choice(variable, value)
    snapshot = @state.dup
    choice = ChoicePoint.new(variable, value, snapshot)
    @choice_stack << choice
    @state[variable] = value
  end
  
  def undo_last_choice
    return nil if @choice_stack.empty?
    
    choice = @choice_stack.pop
    @state = choice.state_snapshot
    choice
  end
  
  def current_state
    @state.dup
  end
end

Pruning Strategies

Effective pruning eliminates branches early based on domain knowledge or heuristics.

module PruningStrategies
  # Bound-based pruning for optimization problems
  def prune_by_bound?(partial_solution, best_solution)
    return false unless best_solution
    
    lower_bound = calculate_lower_bound(partial_solution)
    lower_bound >= objective_value(best_solution)
  end
  
  # Feasibility pruning
  def prune_infeasible?(partial_solution)
    !satisfies_mandatory_constraints?(partial_solution)
  end
  
  # Dominance pruning
  def prune_dominated?(partial_solution, existing_solutions)
    existing_solutions.any? { |sol| dominates?(sol, partial_solution) }
  end
  
  # Symmetry pruning
  def prune_symmetric?(partial_solution, seen_canonical)
    canonical = canonicalize(partial_solution)
    seen_canonical.include?(canonical)
  end
end

class OptimizingBacktracker
  include PruningStrategies
  
  def find_optimal(initial_state)
    @best_solution = nil
    @best_value = Float::INFINITY
    
    backtrack_optimize(initial_state)
    @best_solution
  end
  
  private
  
  def backtrack_optimize(state)
    if complete?(state)
      value = objective_value(state)
      if value < @best_value
        @best_value = value
        @best_solution = state.dup
      end
      return
    end
    
    return if prune_by_bound?(state, @best_solution)
    return if prune_infeasible?(state)
    
    next_choices(state).each do |choice|
      if valid?(state, choice)
        apply(state, choice)
        backtrack_optimize(state)
        revert(state, choice)
      end
    end
  end
end

Variable Ordering Heuristics

The order in which variables are assigned significantly impacts performance. Common heuristics include most constrained variable and minimum remaining values.

class VariableOrderer
  # Most constrained variable: choose variable with smallest domain
  def most_constrained(variables, domains)
    variables.min_by { |var| domains[var].size }
  end
  
  # Most constraining variable: affects most other variables
  def most_constraining(variables, constraints)
    variables.max_by { |var| count_constraints(var, constraints) }
  end
  
  # Degree heuristic: most connections to unassigned variables
  def highest_degree(variables, graph, assigned)
    unassigned = variables - assigned.keys
    unassigned.max_by { |var| graph[var].count { |neighbor| !assigned.key?(neighbor) } }
  end
  
  # Combined heuristic: break ties
  def select_variable(variables, domains, constraints, assigned)
    unassigned = variables - assigned.keys
    
    # Primary: most constrained
    min_domain_size = unassigned.map { |v| domains[v].size }.min
    candidates = unassigned.select { |v| domains[v].size == min_domain_size }
    
    return candidates.first if candidates.size == 1
    
    # Secondary: most constraining
    candidates.max_by { |var| count_constraints(var, constraints) }
  end
  
  private
  
  def count_constraints(var, constraints)
    constraints.count { |c| c.involves?(var) }
  end
end

Value Ordering Heuristics

After selecting a variable, ordering its possible values affects the likelihood of finding solutions quickly.

class ValueOrderer
  # Least constraining value: leaves most options for other variables
  def least_constraining(variable, domain, state, constraints)
    domain.sort_by do |value|
      test_state = state.dup
      test_state[variable] = value
      count_eliminated_values(test_state, variable, constraints)
    end
  end
  
  # Prefer values that satisfy more constraints
  def most_satisfying(variable, domain, state, constraints)
    domain.sort_by do |value|
      test_state = state.dup
      test_state[variable] = value
      -count_satisfied_constraints(test_state, constraints)
    end
  end
  
  # Random ordering for randomized algorithms
  def randomized(domain)
    domain.shuffle
  end
  
  private
  
  def count_eliminated_values(state, variable, constraints)
    count = 0
    constraints.each do |constraint|
      next unless constraint.involves?(variable)
      
      constraint.affected_variables(variable).each do |other_var|
        next if state.key?(other_var)
        
        # Count how many values become invalid for other_var
        count += count_invalid_values(other_var, state, constraint)
      end
    end
    count
  end
  
  def count_satisfied_constraints(state, constraints)
    constraints.count { |c| c.satisfied?(state) }
  end
end

Constraint Recording

Recording conflicts and learned constraints speeds up backtracking by avoiding repeated failures.

class ConstraintRecorder
  def initialize
    @conflict_cache = {}
    @learned_constraints = []
  end
  
  def record_conflict(state, variable, value)
    key = conflict_key(state, variable)
    @conflict_cache[key] ||= Set.new
    @conflict_cache[key] << value
  end
  
  def is_known_conflict?(state, variable, value)
    key = conflict_key(state, variable)
    @conflict_cache[key]&.include?(value) || false
  end
  
  def learn_constraint(variables, forbidden_combination)
    @learned_constraints << {
      variables: variables,
      forbidden: forbidden_combination
    }
  end
  
  def violates_learned?(state)
    @learned_constraints.any? do |constraint|
      vars = constraint[:variables]
      next unless vars.all? { |v| state.key?(v) }
      
      combination = vars.map { |v| state[v] }
      combination == constraint[:forbidden]
    end
  end
  
  private
  
  def conflict_key(state, variable)
    # Create key from assigned variables, excluding current variable
    assigned = state.reject { |k, v| k == variable }
    assigned.sort.to_h.hash
  end
end

Performance Considerations

Backtracking performance varies dramatically based on problem size, constraint tightness, and implementation choices. Understanding these factors enables optimization for specific use cases.

Time Complexity Analysis

The worst-case time complexity of backtracking is exponential: O(b^d) where b is the branching factor (average number of choices per decision) and d is the maximum depth of the search tree. For N-Queens with N=8, the search tree has up to 8! = 40,320 leaf nodes, though constraint checking prunes most branches early.

Constraint propagation reduces the effective branching factor. In Sudoku, each cell has 9 possible values initially, but constraint propagation typically reduces this to 2-3 options per cell, dramatically shrinking the search space.

The best-case scenario finds a solution on the first path explored, achieving O(d) time complexity. Heuristics that order variables and values intelligently push performance toward best-case behavior.

# Measuring backtracking performance
class PerformanceTracker
  attr_reader :nodes_visited, :backtracks, :solutions_found
  
  def initialize
    reset
  end
  
  def reset
    @nodes_visited = 0
    @backtracks = 0
    @solutions_found = 0
    @start_time = nil
  end
  
  def start
    @start_time = Time.now
  end
  
  def visit_node
    @nodes_visited += 1
  end
  
  def backtrack
    @backtracks += 1
  end
  
  def found_solution
    @solutions_found += 1
  end
  
  def stats
    elapsed = Time.now - @start_time
    {
      nodes: @nodes_visited,
      backtracks: @backtracks,
      solutions: @solutions_found,
      time: elapsed,
      nodes_per_second: @nodes_visited / elapsed
    }
  end
end

Space Complexity

Recursive backtracking uses O(d) space for the call stack, where d is the maximum depth. Each stack frame stores the current state and remaining choices. For problems with large state representations, this becomes significant.

Iterative backtracking with explicit stacks has similar space requirements but provides control over stack size and state representation. Incremental state updates (adding/removing one element rather than copying entire states) reduce space overhead.

# Space-efficient state management
class IncrementalState
  def initialize
    @assignments = {}
    @history = []
  end
  
  def assign(var, value)
    old_value = @assignments[var]
    @assignments[var] = value
    @history << [var, old_value]
  end
  
  def backtrack
    return if @history.empty?
    
    var, old_value = @history.pop
    if old_value.nil?
      @assignments.delete(var)
    else
      @assignments[var] = old_value
    end
  end
  
  def [](var)
    @assignments[var]
  end
  
  def key?(var)
    @assignments.key?(var)
  end
  
  # No full state copies needed
  def memory_footprint
    @assignments.size + @history.size
  end
end

Pruning Effectiveness

Early pruning has multiplicative impact on performance. If pruning eliminates 90% of branches at each level, a depth-10 search tree shrinks from 10^10 nodes to 10^9 nodes, a 10x speedup.

Forward checking, which checks constraints on unassigned variables after each assignment, provides cheap but effective pruning. Arc consistency algorithms like AC-3 perform deeper constraint propagation at higher computational cost per node but with better pruning.

# Comparing pruning strategies
class PruningComparison
  def solve_no_pruning(problem)
    tracker = PerformanceTracker.new
    tracker.start
    
    result = backtrack_basic(problem, tracker)
    
    { result: result, stats: tracker.stats, strategy: 'none' }
  end
  
  def solve_with_forward_checking(problem)
    tracker = PerformanceTracker.new
    tracker.start
    
    result = backtrack_forward_check(problem, tracker)
    
    { result: result, stats: tracker.stats, strategy: 'forward_checking' }
  end
  
  def solve_with_arc_consistency(problem)
    tracker = PerformanceTracker.new
    tracker.start
    
    result = backtrack_arc_consistency(problem, tracker)
    
    { result: result, stats: tracker.stats, strategy: 'arc_consistency' }
  end
  
  def compare(problem)
    [
      solve_no_pruning(problem),
      solve_with_forward_checking(problem),
      solve_with_arc_consistency(problem)
    ]
  end
end

Caching and Memoization

Caching subproblem results avoids redundant computation when the same partial state appears multiple times. This works when subproblems overlap, converting exponential algorithms to polynomial in some cases.

class MemoizedBacktracker
  def initialize
    @cache = {}
  end
  
  def solve(state)
    key = cache_key(state)
    return @cache[key] if @cache.key?(key)
    
    result = if goal?(state)
      state
    else
      attempt_solve(state)
    end
    
    @cache[key] = result
    result
  end
  
  private
  
  def cache_key(state)
    # Create canonical representation for caching
    # Order-independent if problem has symmetries
    state.sort.to_h.hash
  end
  
  def attempt_solve(state)
    choices(state).each do |choice|
      if valid?(state, choice)
        new_state = apply(state, choice)
        result = solve(new_state)
        return result if result
      end
    end
    nil
  end
end

Parallelization Opportunities

Backtracking parallelizes naturally by exploring different branches concurrently. The first few levels of the search tree provide independent subproblems that threads or processes can solve simultaneously.

require 'concurrent-ruby'

class ParallelBacktracker
  def initialize(thread_count = 4)
    @thread_pool = Concurrent::FixedThreadPool.new(thread_count)
  end
  
  def solve(initial_state, depth_to_parallelize = 2)
    # Generate work items by expanding tree to specified depth
    work_items = generate_work_items(initial_state, depth_to_parallelize)
    
    # Solve each branch in parallel
    futures = work_items.map do |partial_state|
      Concurrent::Future.execute(executor: @thread_pool) do
        solve_sequential(partial_state)
      end
    end
    
    # Return first solution found
    futures.each do |future|
      result = future.value
      return result if result
    end
    
    nil
  ensure
    @thread_pool.shutdown
  end
  
  private
  
  def generate_work_items(state, depth)
    return [state] if depth == 0 || goal?(state)
    
    items = []
    choices(state).each do |choice|
      if valid?(state, choice)
        new_state = apply(state, choice)
        items.concat(generate_work_items(new_state, depth - 1))
      end
    end
    items
  end
  
  def solve_sequential(state)
    # Standard sequential backtracking for branch
    return state if goal?(state)
    
    choices(state).each do |choice|
      if valid?(state, choice)
        result = solve_sequential(apply(state, choice))
        return result if result
      end
    end
    nil
  end
end

Implementation Approaches

Recursive vs Iterative

Recursive implementations express backtracking naturally through the call stack but face stack depth limitations. Ruby's default stack size handles depths up to several thousand levels, sufficient for most problems.

Iterative implementations using explicit stacks avoid recursion limits and provide more control over search traversal. The stack stores tuples of (state, choices, index) rather than relying on call frames.

# Recursive approach
def solve_recursive(state)
  return state if complete?(state)
  
  next_choices(state).each do |choice|
    if valid?(state, choice)
      apply!(state, choice)
      result = solve_recursive(state)
      return result if result
      revert!(state, choice)
    end
  end
  
  nil
end

# Iterative equivalent
def solve_iterative(initial_state)
  stack = [[initial_state, next_choices(initial_state), 0]]
  
  while stack.any?
    state, choices, idx = stack.pop
    
    return state if complete?(state)
    
    if idx < choices.size
      choice = choices[idx]
      stack.push([state, choices, idx + 1])  # Save point for next choice
      
      if valid?(state, choice)
        new_state = apply(state, choice)
        stack.push([new_state, next_choices(new_state), 0])
      end
    end
  end
  
  nil
end

Depth-First vs Breadth-First Search

Standard backtracking uses depth-first search (DFS), exploring one path completely before trying alternatives. DFS uses minimal memory (O(depth)) and finds solutions quickly when they exist at depth.

Breadth-first search (BFS) explores all nodes at one depth before moving deeper, guaranteeing the shallowest solution but requiring O(branching_factor^depth) memory. BFS makes sense when solution depth varies widely and shallow solutions are preferable.

# DFS backtracking (standard)
def dfs_backtrack(state)
  return state if goal?(state)
  
  choices(state).each do |choice|
    if valid?(state, choice)
      result = dfs_backtrack(apply(state, choice))
      return result if result
    end
  end
  nil
end

# BFS adaptation
def bfs_backtrack(initial_state)
  queue = [initial_state]
  
  until queue.empty?
    state = queue.shift
    return state if goal?(state)
    
    choices(state).each do |choice|
      queue << apply(state, choice) if valid?(state, choice)
    end
  end
  
  nil
end

Iterative Deepening

Iterative deepening depth-first search (IDDFS) combines DFS memory efficiency with BFS optimality. The algorithm performs depth-limited DFS repeatedly with increasing depth limits.

class IterativeDeepeningBacktracker
  def solve(initial_state, max_depth = Float::INFINITY)
    depth = 0
    
    while depth <= max_depth
      result = depth_limited_search(initial_state, depth)
      return result if result
      depth += 1
    end
    
    nil
  end
  
  private
  
  def depth_limited_search(state, limit, depth = 0)
    return state if goal?(state)
    return nil if depth >= limit
    
    choices(state).each do |choice|
      if valid?(state, choice)
        result = depth_limited_search(
          apply(state, choice),
          limit,
          depth + 1
        )
        return result if result
      end
    end
    
    nil
  end
end

Constraint Satisfaction Problem Framework

Implementing backtracking as a generic CSP solver separates the algorithm from problem-specific logic, enabling reuse across different problems.

class CSP
  attr_reader :variables, :domains, :constraints
  
  def initialize(variables, domains, constraints)
    @variables = variables
    @domains = domains
    @constraints = constraints
  end
  
  def solve
    BacktrackingCSPSolver.new(self).solve
  end
end

class BacktrackingCSPSolver
  def initialize(csp)
    @csp = csp
    @assignment = {}
  end
  
  def solve
    backtrack
  end
  
  private
  
  def backtrack
    return @assignment if complete?
    
    var = select_unassigned_variable
    order_domain_values(var).each do |value|
      if consistent?(var, value)
        assign(var, value)
        result = backtrack
        return result if result
        unassign(var)
      end
    end
    
    nil
  end
  
  def complete?
    @assignment.size == @csp.variables.size
  end
  
  def select_unassigned_variable
    # MRV heuristic
    unassigned = @csp.variables - @assignment.keys
    unassigned.min_by { |v| @csp.domains[v].size }
  end
  
  def order_domain_values(var)
    @csp.domains[var]
  end
  
  def consistent?(var, value)
    @csp.constraints.all? do |constraint|
      constraint.satisfied?(@assignment.merge(var => value))
    end
  end
  
  def assign(var, value)
    @assignment[var] = value
  end
  
  def unassign(var)
    @assignment.delete(var)
  end
end

# Using the framework for N-Queens
class QueensConstraint
  def satisfied?(assignment)
    assignment.each do |row1, col1|
      assignment.each do |row2, col2|
        next if row1 == row2
        
        # Check column and diagonal conflicts
        return false if col1 == col2
        return false if (row1 - row2).abs == (col1 - col2).abs
      end
    end
    true
  end
end

# Solve 4-Queens using CSP framework
n = 4
variables = (0...n).to_a
domains = variables.map { |v| [v, (0...n).to_a] }.to_h
constraints = [QueensConstraint.new]

csp = CSP.new(variables, domains, constraints)
solution = csp.solve

Reference

Backtracking Algorithm Template

Common Problem Types

Pruning Techniques

Variable Ordering Heuristics

Performance Characteristics

Note: d = depth, b = branching factor

State Management Operations

Ruby-Specific Optimizations

Constraint Types

Termination Conditions