Backtracking Search Algorithm

Overview

Backtracking search is a systematic algorithm for solving Constraint Satisfaction Problems (CSPs). It explores the solution space by incrementally building candidate solutions and abandoning partial candidates ("backtracking") when they cannot possibly lead to a valid complete solution.

How It Works

The algorithm works by:

1. Selecting an unassigned variable from the problem
2. Trying each value in the variable's domain
3. Checking consistency with existing assignments
4. Recursively solving the reduced problem
5. Backtracking when a dead-end is reached

Pseudo Code

function BACKTRACKING-SEARCH(csp)
    # Returns a solution assignment or failure
    return RECURSIVE-BACKTRACKING({}, csp)

function RECURSIVE-BACKTRACKING(assignment, csp)
    # Returns a solution assignment or failure
    
    # Base case: all variables assigned
    if assignment is complete then 
        return assignment
    
    # Select next variable to assign
    var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp)
    
    # Try each value in the variable's domain
    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
        # Check if this value is consistent with current assignment
        if value is consistent with assignment given CONSTRAINTS[csp] then
            # Add the assignment
            add {var = value} to assignment
            
            # Recursively solve the rest
            result ← RECURSIVE-BACKTRACKING(assignment, csp)
            
            # If successful, propagate the solution
            if result ≠ failure then 
                return result
            
            # Otherwise, undo this assignment and try next value
            remove {var = value} from assignment
    
    # No valid assignment found for this variable
    return failure

Key Functions Explained

• SELECT-UNASSIGNED-VARIABLE: Chooses which variable to assign next

  • Can use heuristics like MRV (Minimum Remaining Values)
  • Or degree heuristic (most constraining variable)

• ORDER-DOMAIN-VALUES: Orders the values to try for a variable

  • Can use least-constraining-value heuristic
  • Tries to leave maximum flexibility for future assignments

Strengths

1. Completeness

• Guaranteed to find a solution if one exists
• Systematically explores the entire search space

2. Memory Efficiency

• Space complexity is O(d·n) where d is depth and n is number of variables
• Only stores the current path, not the entire search tree

3. Early Pruning

• Detects failures early and abandons infeasible partial solutions
• Avoids exploring large portions of the search space

4. Simplicity

• Straightforward to implement and understand
• Natural recursive structure maps well to the problem

5. Flexibility

• Can be enhanced with various heuristics and optimizations
• Works with any type of constraints (unary, binary, n-ary)

When to Use Backtracking Search

Ideal Scenarios

1. Constraint Satisfaction Problems

   • Sudoku puzzles
   • N-Queens problem
   • Map coloring
   • Scheduling problems
   • SAT solving

2. Combinatorial Optimization

   • When you need to find all solutions
   • When the solution space is relatively small
   • When constraints can quickly eliminate branches

3. Problems with Clear Constraints

   • Binary constraints between variables
   • Well-defined consistency checks
   • Problems where partial solutions can be validated

Consider Alternatives When

• Very Large Search Spaces: May be too slow without optimizations
• Continuous Domains: Better suited for other techniques
• Optimization Problems: When you need the best solution, not just any solution
• Real-time Applications: May not meet strict time constraints

Common Enhancements

1. Forward Checking

Maintain arc consistency by eliminating values from future variables that would violate constraints.

2. Arc Consistency (AC-3)

Preprocess the problem to reduce domain sizes before search begins.

3. Variable Ordering Heuristics

• MRV (Minimum Remaining Values): Choose variable with fewest legal values
• Degree Heuristic: Choose variable involved in most constraints

4. Value Ordering Heuristics

• Least Constraining Value: Try values that rule out fewest choices for neighbors

5. Constraint Propagation

Propagate the implications of each assignment to detect failures earlier.

Example Implementation (Python)

def backtracking_search(csp):
    """Entry point for backtracking search."""
    return recursive_backtracking({}, csp)

def recursive_backtracking(assignment, csp):
    """Recursive backtracking with assignment."""
    # Check if assignment is complete
    if is_complete(assignment, csp):
        return assignment
    
    # Select unassigned variable
    var = select_unassigned_variable(csp.variables, assignment, csp)
    
    # Try each value in domain
    for value in order_domain_values(var, assignment, csp):
        if is_consistent(var, value, assignment, csp.constraints):
            # Add assignment
            assignment[var] = value
            
            # Recursive call
            result = recursive_backtracking(assignment, csp)
            if result is not None:
                return result
            
            # Remove assignment (backtrack)
            del assignment[var]
    
    return None  # Failure

Time and Space Complexity

• Time Complexity: O(b^d) in worst case

  • b = branching factor (size of domains)
  • d = depth (number of variables)
  • Can be much better with good heuristics

• Space Complexity: O(d)

  • Only stores current assignment path
  • Much more efficient than storing entire tree

Conclusion

Backtracking search is a fundamental algorithm for CSPs that provides a complete and systematic approach to finding solutions. While it can be slow for large problems, its simplicity and ability to be enhanced with heuristics make it a valuable tool in many problem-solving scenarios. The key to effective use is understanding when the problem structure allows for efficient pruning of the search space.