Constraint Satisfaction

What I do

• Formulate and solve constraint satisfaction problems
• Implement search algorithms
• Apply backtracking and propagation
• Design constraint solvers
• Optimize constraint solving
• Handle complex combinatorial problems

When to use me

Use me when:

• Scheduling and planning problems
• Resource allocation
• Puzzle solving (Sudoku, crossword)
• Configuration problems
• Combinatorial optimization

Key Concepts

CSP Framework

Variables: {X1, X2, X3, ..., Xn}
Domains: {D1, D2, D3, ..., Dn}
Constraints: {C1, C2, C3, ..., Cm}

Goal: Find assignment to all variables satisfying all constraints

Python CSP Example

from constraint import Problem, BacktrackingSolver

# Define problem
problem = Problem(BacktrackingSolver())

# Variables with domains
problem.addVariable("A", [1, 2, 3, 4])
problem.addVariable("B", [1, 2, 3, 4])
problem.addVariable("C", [1, 2, 3, 4])

# Constraints
def all_different(vars):
    return len(set(vars)) == len(vars)

problem.addConstraint(all_different, ["A", "B", "C"])
problem.addConstraint(lambda a, b: a + b > 4, ["A", "B"])
problem.addConstraint(lambda b, c: b != c, ["B", "C"])

# Solve
solutions = problem.getSolutions()
print(solutions)

Algorithms

• Backtracking: Systematic search
• Forward Checking: Prune domains early
• Arc Consistency (AC-3): Remove inconsistent values
• Min-Conflicts: Local search for large problems
• Genetic Algorithms: For complex constraints

Applications

• Scheduling: Employee rostering, class scheduling
• Routing: Vehicle routing with constraints
• Puzzles: Sudoku, N-Queens
• Configuration: Product configuration
• Planning: Task ordering with dependencies