Implementing CSP solvers with systematic search
Scope: Backtracking search for CSPs, variable ordering heuristics, value ordering, optimization Lines: ~320 Last Updated: 2025-10-18
Activate this skill when:
Basic algorithm: Depth-first search with constraint checking
Completeness: Explores entire search tree
Performance: Exponential worst case O(d^n)
Minimum Remaining Values (MRV): Choose variable with fewest legal values
Degree heuristic: Tiebreaker for MRV
Dynamic ordering: Recompute best variable at each step
Least Constraining Value (LCV): Try value leaving most choices for other variables
Random ordering: No heuristic
def backtracking_search(variables, domains, constraints):
"""
Find solution to CSP using backtracking.
Returns:
Assignment (dict) if solution found, None otherwise
"""
return backtrack({}, variables, domains, constraints)
def backtrack(assignment, variables, domains, constraints):
"""Recursive backtracking with constraint checking."""
# Base case: assignment complete
if len(assignment) == len(variables):
return assignment
# Select unassigned variable
var = select_unassigned_variable(variables, assignment)
# Try each value in domain
for value in order_domain_values(var, domains):
# Check if assignment consistent
if is_consistent(var, value, assignment, constraints):
# Add to assignment
assignment[var] = value
# Recurse
result = backtrack(assignment, variables, domains, constraints)
if result is not None:
return result
# Backtrack: remove assignment
del assignment[var]
return None # No solution found
def is_consistent(var, value, assignment, constraints):
"""Check if var=value consistent with current assignment."""
for other_var, other_value in assignment.items():
# Check constraint between var and other_var
if (var, other_var) in constraints:
constraint = constraints[(var, other_var)]
if not constraint(value, other_value):
return False
# Check reverse constraint
if (other_var, var) in constraints:
constraint = constraints[(other_var, var)]
if not constraint(other_value, value):
return False
return TrueWhen to use:
def select_unassigned_variable_mrv(variables, assignment, domains):
"""
Select variable with MRV heuristic.
Choose variable with fewest remaining legal values.
"""
unassigned = [v for v in variables if v not in assignment]
# Count remaining values for each variable
def count_values(var):
# If using domain reduction, count current domain size
return len(domains[var])
# Choose variable with minimum remaining values
mrv_var = min(unassigned, key=count_values)
return mrv_var
def select_unassigned_variable_mrv_degree(
variables, assignment, domains, constraints
):
"""
MRV with degree heuristic as tiebreaker.
Degree = number of constraints with unassigned variables.
"""
unassigned = [v for v in variables if v not in assignment]
def mrv_degree_key(var):
# Primary: MRV (fewer values better, so positive count)
mrv = len(domains[var])
# Secondary: Degree (more constraints better, so negative count)
degree = -sum(
1 for other_var in unassigned
if other_var != var and (
(var, other_var) in constraints or
(other_var, var) in constraints
)
)
return (mrv, degree)
return min(unassigned, key=mrv_degree_key)
# Example usage
variables = ['A', 'B', 'C', 'D']
domains = {
'A': {1, 2, 3}, # 3 values
'B': {1, 2}, # 2 values (MRV chooses this)
'C': {1, 2, 3, 4}, # 4 values
'D': {1, 2, 3} # 3 values
}
assignment = {}
var = select_unassigned_variable_mrv(variables, assignment, domains)
print(var) # 'B'Benefits:
def order_domain_values_lcv(var, assignment, domains, constraints):
"""
Order values using LCV heuristic.
Try value that rules out fewest choices for other variables first.
"""
def count_conflicts(value):
"""Count how many values ruled out in other domains."""
conflicts = 0
for other_var in domains:
if other_var in assignment or other_var == var:
continue # Skip assigned and self
# Count values in other_var ruled out by var=value
for other_value in domains[other_var]:
if (var, other_var) in constraints:
constraint = constraints[(var, other_var)]
if not constraint(value, other_value):
conflicts += 1
return conflicts
# Sort values by number of conflicts (ascending)
values = sorted(domains[var], key=count_conflicts)
return values
# Example
def backtrack_with_heuristics(assignment, variables, domains, constraints):
"""Backtracking with MRV and LCV."""
if len(assignment) == len(variables):
return assignment
# MRV: Select most constrained variable
var = select_unassigned_variable_mrv(variables, assignment, domains)
# LCV: Try least constraining values first
values = order_domain_values_lcv(var, assignment, domains, constraints)
for value in values:
if is_consistent(var, value, assignment, constraints):
assignment[var] = value
result = backtrack_with_heuristics(
assignment, variables, domains, constraints
)
if result is not None:
return result
del assignment[var]
return NoneWhen to use:
def backtrack_fc(assignment, domains, variables, constraints):
"""Backtracking with forward checking (domain pruning)."""
if len(assignment) == len(variables):
return assignment
var = select_unassigned_variable_mrv(variables, assignment, domains)
for value in domains[var]:
if is_consistent(var, value, assignment, constraints):
# Save current domains
saved_domains = {v: d.copy() for v, d in domains.items()}
# Assign and forward check
assignment[var] = value
domains[var] = {value}
# Prune domains of unassigned variables
pruned = forward_check(var, value, domains, constraints, assignment)
if pruned: # No domain wipeout
result = backtrack_fc(
assignment, domains, variables, constraints
)
if result is not None:
return result
# Restore domains and backtrack
domains.update(saved_domains)
del assignment[var]
return None
def forward_check(var, value, domains, constraints, assignment):
"""
Prune domains after assigning var=value.
Returns False if any domain becomes empty.
"""
for other_var in domains:
if other_var in assignment or other_var == var:
continue
if (var, other_var) in constraints:
constraint = constraints[(var, other_var)]
# Remove inconsistent values from other_var
to_remove = []
for other_value in domains[other_var]:
if not constraint(value, other_value):
to_remove.append(other_value)
for v in to_remove:
domains[other_var].discard(v)
# Check for domain wipeout
if len(domains[other_var]) == 0:
return False
return TrueBenefits:
def find_all_solutions(variables, domains, constraints):
"""Find all solutions to CSP."""
solutions = []
def backtrack_all(assignment):
if len(assignment) == len(variables):
# Found complete assignment
solutions.append(assignment.copy())
return
var = select_unassigned_variable_mrv(variables, assignment, domains)
for value in domains[var]:
if is_consistent(var, value, assignment, constraints):
assignment[var] = value
backtrack_all(assignment) # Don't return early
del assignment[var]
backtrack_all({})
return solutions
# Example: All 4-Queens solutions
variables = list(range(4))
domains = {i: {0, 1, 2, 3} for i in range(4)}
def no_attack_constraint(col1, col2, row1, row2):
"""Queens don't attack each other."""
return (col1 != col2 and # Different columns
abs(row1 - row2) != abs(col1 - col2)) # Not diagonal
constraints = {
(i, j): (lambda c1, c2, r1=i, r2=j:
no_attack_constraint(c1, c2, r1, r2))
for i in range(4) for j in range(i + 1, 4)
}
all_solutions = find_all_solutions(variables, domains, constraints)
print(f"Found {len(all_solutions)} solutions") # 2 solutionsWhen to use:
| Variable Order | Value Order | Use Case | Performance | |----------------|-------------|----------|-------------| | Static | Static | Baseline | Worst | | MRV | Static | Medium problems | Good | | MRV + Degree | Static | Tight constraints | Better | | MRV | LCV | Single solution | Best | | MRV + Degree | LCV | Complex CSPs | Best |
Technique | Overhead | Benefit | When to Use
------------------------|----------|----------------|------------------
Forward Checking | Low | Medium | Always
Maintaining Arc-3 | Medium | High | Tight constraints
Conflict Backjumping | Medium | High | Deep search trees
Symmetry Breaking | Low | Problem-dep | Symmetric problems
Randomization + Restart | Low | Problem-dep | Heavy-tailed dist✅ DO: Use MRV heuristic (almost always helps)
✅ DO: Implement forward checking
✅ DO: Copy domains when backtracking (not references)
✅ DO: Use degree heuristic as MRV tiebreaker
❌ DON'T: Recompute static information in loops
❌ DON'T: Use LCV when finding all solutions (overhead wasted)
❌ DON'T: Forget to restore state when backtracking
❌ DON'T: Use recursion depth for very large problems (use iterative)❌ Static variable ordering
# Inefficient: Always tries variables in same order
for var in variables:
if var not in assignment:
return var✅ Use MRV to choose most constrained variable
❌ No domain pruning
# Slow: Checks all constraints at assignment time only
if is_consistent(var, value, assignment, constraints):
assignment[var] = value✅ Use forward checking to prune domains early
❌ Computing LCV for all solutions
# Wasteful: LCV overhead without benefit
def backtrack_all(assignment):
# ... finding all solutions
values = order_domain_values_lcv(var, ...) # Wasted work✅ Use LCV only when finding single solution
❌ Modifying shared domain objects
# Bug: Modifying domain affects all branches
domains[var].remove(value) # Side effect!
backtrack(assignment, domains, ...)✅ Copy domains before modification
❌ Deep recursion without iterative alternative
# Risk: Stack overflow on large problems
def backtrack(assignment, ...):
return backtrack(assignment, ...) # 1000+ levels✅ Implement iterative version or increase stack limit
csp-modeling.md - Defining CSP problems and variablesconstraint-propagation.md - Domain reduction techniquessat-solving-strategies.md - Boolean constraint solvingoptimization-algorithms.md - Optimization with constraintsgraph-algorithms.md - Graph coloring and constraint graphsLast Updated: 2025-10-18 Format Version: 1.0 (Atomic)