20.20 Building a Constraint Solver
Design a small constraint solver that assigns values to variables while satisfying a set of rules.
20.20 Building a Constraint Solver
Problem
Design a small constraint solver that assigns values to variables while satisfying a set of rules.
Constraint solvers appear in scheduling systems, puzzle engines, configuration tools, package managers, type checkers, layout engines, test-case generators, compilers, and planning systems. They answer questions such as:
Can these requirements all be satisfied?
Which assignment satisfies them?
Which constraints conflict?
A simple example is map coloring. Adjacent regions must have different colors.
A != B
A != C
B != C
C != D
With colors:
red, green, blue
one valid assignment is:
A = red
B = green
C = blue
D = red
The core algorithmic problem is search with pruning. The engineering problem is representing variables, domains, constraints, failures, and explanations clearly.
Solution
Use backtracking search. Assign one variable at a time. After each assignment, check constraints. If the partial assignment violates a constraint, undo the assignment and try a different value.
The search tree looks like this:
A = red
B = red invalid
B = green
C = red invalid
C = blue valid so far
Backtracking is simple, complete for finite domains, and easy to extend with heuristics.
Modeling Variables and Domains
A constraint satisfaction problem has variables and possible values for each variable.
from dataclasses import dataclass
from typing import Callable
@dataclass(frozen=True)
class Variable:
name: str
@dataclass
class Problem:
variables: list[str]
domains: dict[str, list[object]]
constraints: list[object]
Example:
problem = Problem(
variables=["A", "B", "C", "D"],
domains={
"A": ["red", "green", "blue"],
"B": ["red", "green", "blue"],
"C": ["red", "green", "blue"],
"D": ["red", "green", "blue"],
},
constraints=[],
)
A domain is the set of values a variable may take.
Defining Constraints
A constraint can be represented as a function over an assignment.
@dataclass(frozen=True)
class Constraint:
variables: tuple[str, ...]
predicate: Callable[[dict[str, object]], bool]
description: str
The variables field says which variables the constraint depends on. The predicate returns True if the current assignment is acceptable.
For inequality:
def not_equal(left, right):
return Constraint(
variables=(left, right),
predicate=lambda assignment: (
left not in assignment
or right not in assignment
or assignment[left] != assignment[right]
),
description=f"{left} != {right}",
)
The predicate allows partial assignments. If either variable is not assigned yet, the constraint cannot be violated yet.
Build the map-coloring problem:
problem.constraints = [
not_equal("A", "B"),
not_equal("A", "C"),
not_equal("B", "C"),
not_equal("C", "D"),
]
Checking Consistency
A partial assignment is consistent if all relevant constraints hold.
def is_consistent(problem, assignment, variable):
for constraint in problem.constraints:
if variable not in constraint.variables:
continue
if not constraint.predicate(assignment):
return False
return True
Only constraints involving the most recently assigned variable need to be checked. This avoids unnecessary work.
Basic Backtracking
The solver recursively assigns variables.
def solve(problem):
return backtrack(problem, {})
def backtrack(problem, assignment):
if len(assignment) == len(problem.variables):
return dict(assignment)
variable = select_unassigned_variable(problem, assignment)
for value in problem.domains[variable]:
assignment[variable] = value
if is_consistent(problem, assignment, variable):
result = backtrack(problem, assignment)
if result is not None:
return result
del assignment[variable]
return None
Variable selection:
def select_unassigned_variable(problem, assignment):
for variable in problem.variables:
if variable not in assignment:
return variable
raise ValueError("all variables are already assigned")
Use it:
solution = solve(problem)
print(solution)
Possible output:
{'A': 'red', 'B': 'green', 'C': 'blue', 'D': 'red'}
This is the minimal working solver.
Returning All Solutions
Sometimes one solution is not enough.
def solve_all(problem):
results = []
backtrack_all(problem, {}, results)
return results
def backtrack_all(problem, assignment, results):
if len(assignment) == len(problem.variables):
results.append(dict(assignment))
return
variable = select_unassigned_variable(problem, assignment)
for value in problem.domains[variable]:
assignment[variable] = value
if is_consistent(problem, assignment, variable):
backtrack_all(problem, assignment, results)
del assignment[variable]
This enumerates every solution. Be careful: the number of solutions can be very large.
Detecting Unsatisfiable Problems
If solve returns None, no assignment satisfies all constraints.
Example:
unsat = Problem(
variables=["A", "B"],
domains={
"A": ["red"],
"B": ["red"],
},
constraints=[
not_equal("A", "B"),
],
)
print(solve(unsat))
Output:
None
The solver proves unsatisfiability by exhausting the finite search space.
For large problems, plain exhaustion may be too slow. Add pruning heuristics.
Minimum Remaining Values
The minimum remaining values heuristic selects the variable with the fewest legal values under the current partial assignment.
This often reduces branching.
def legal_values(problem, assignment, variable):
values = []
for value in problem.domains[variable]:
assignment[variable] = value
if is_consistent(problem, assignment, variable):
values.append(value)
del assignment[variable]
return values
Select the most constrained variable:
def select_mrv_variable(problem, assignment):
unassigned = [
variable
for variable in problem.variables
if variable not in assignment
]
return min(
unassigned,
key=lambda variable: len(
legal_values(problem, assignment, variable)
),
)
Use it inside backtracking:
variable = select_mrv_variable(problem, assignment)
MRV is especially helpful when domains shrink unevenly.
Forward Checking
Forward checking removes values from neighboring domains after an assignment.
If A = red and A != B, then red can be removed from B's domain.
A simple implementation copies domains at each step.
def forward_check(problem, domains, assignment, variable):
new_domains = {
name: list(values)
for name, values in domains.items()
}
for constraint in problem.constraints:
if variable not in constraint.variables:
continue
for other in constraint.variables:
if other == variable or other in assignment:
continue
allowed = []
for value in new_domains[other]:
assignment[other] = value
if constraint.predicate(assignment):
allowed.append(value)
del assignment[other]
if not allowed:
return None
new_domains[other] = allowed
return new_domains
Backtracking with domains:
def solve_with_forward_checking(problem):
domains = {
variable: list(values)
for variable, values in problem.domains.items()
}
return backtrack_fc(problem, {}, domains)
def backtrack_fc(problem, assignment, domains):
if len(assignment) == len(problem.variables):
return dict(assignment)
variable = min(
[
name
for name in problem.variables
if name not in assignment
],
key=lambda name: len(domains[name]),
)
for value in domains[variable]:
assignment[variable] = value
if is_consistent(problem, assignment, variable):
next_domains = forward_check(
problem,
domains,
assignment,
variable,
)
if next_domains is not None:
result = backtrack_fc(
problem,
assignment,
next_domains,
)
if result is not None:
return result
del assignment[variable]
return None
Forward checking catches dead ends earlier than plain backtracking.
Example: Sudoku
Sudoku is a constraint satisfaction problem.
Variables:
one variable per cell
Domains:
digits 1 through 9
Constraints:
cells in same row differ
cells in same column differ
cells in same 3x3 box differ
given cells keep their fixed values
Variable names:
def cell(row, col):
return f"r{row}c{col}"
Build variables and domains:
def sudoku_problem(givens):
variables = [
cell(row, col)
for row in range(9)
for col in range(9)
]
domains = {}
for row in range(9):
for col in range(9):
name = cell(row, col)
if (row, col) in givens:
domains[name] = [givens[(row, col)]]
else:
domains[name] = list(range(1, 10))
constraints = []
for row in range(9):
row_cells = [
cell(row, col)
for col in range(9)
]
constraints.extend(all_different(row_cells))
for col in range(9):
col_cells = [
cell(row, col)
for row in range(9)
]
constraints.extend(all_different(col_cells))
for box_row in range(0, 9, 3):
for box_col in range(0, 9, 3):
box_cells = [
cell(row, col)
for row in range(box_row, box_row + 3)
for col in range(box_col, box_col + 3)
]
constraints.extend(all_different(box_cells))
return Problem(variables, domains, constraints)
Pairwise all-different constraints:
def all_different(variables):
constraints = []
for i, left in enumerate(variables):
for right in variables[i + 1:]:
constraints.append(not_equal(left, right))
return constraints
This formulation is straightforward. More efficient Sudoku solvers use stronger propagation, but the same constraint model applies.
Constraint Graph
A constraint graph connects variables that appear in a constraint together.
For map coloring:
A -- B
| \ |
| \ |
C -- D
Build neighbors:
def constraint_neighbors(problem):
neighbors = {
variable: set()
for variable in problem.variables
}
for constraint in problem.constraints:
for variable in constraint.variables:
for other in constraint.variables:
if other != variable:
neighbors[variable].add(other)
return neighbors
The constraint graph helps with heuristics such as degree ordering and forward checking.
Degree Heuristic
When MRV ties, choose the variable involved in the most constraints. This tends to expose conflicts early.
def select_mrv_degree_variable(problem, assignment):
neighbors = constraint_neighbors(problem)
unassigned = [
variable
for variable in problem.variables
if variable not in assignment
]
return min(
unassigned,
key=lambda variable: (
len(legal_values(problem, assignment, variable)),
-len(neighbors[variable]),
),
)
This combines two practical ideas:
- Choose a variable with few legal values.
- Break ties by choosing a highly connected variable.
Least Constraining Value
After choosing a variable, try values that eliminate the fewest options for neighbors.
def order_lcv_values(problem, assignment, variable):
neighbors = constraint_neighbors(problem)
unassigned_neighbors = [
neighbor
for neighbor in neighbors[variable]
if neighbor not in assignment
]
def eliminated_count(value):
assignment[variable] = value
count = 0
for neighbor in unassigned_neighbors:
for neighbor_value in problem.domains[neighbor]:
assignment[neighbor] = neighbor_value
if not all(
constraint.predicate(assignment)
for constraint in problem.constraints
if neighbor in constraint.variables
):
count += 1
del assignment[neighbor]
del assignment[variable]
return count
return sorted(
problem.domains[variable],
key=eliminated_count,
)
Least constraining value often improves search on dense problems.
Explaining Failures
A solver that only returns None is hard to debug. Track the constraint that failed.
def first_failed_constraint(problem, assignment, variable):
for constraint in problem.constraints:
if variable not in constraint.variables:
continue
if not constraint.predicate(assignment):
return constraint
return None
Use it for diagnostics:
assignment = {
"A": "red",
"B": "red",
}
failed = first_failed_constraint(problem, assignment, "B")
print(failed.description)
Output:
A != B
Full conflict explanation is a deeper topic, but even this small hook helps users understand why a branch failed.
Optimization Problems
Some problems require the best valid solution, not just any valid solution.
Example:
assign tasks to workers
minimize total cost
Add an objective function.
def solve_best(problem, objective):
best_solution = None
best_score = math.inf
for solution in solve_all(problem):
score = objective(solution)
if score < best_score:
best_score = score
best_solution = solution
return best_solution, best_score
This brute-force method works only for small problems. Larger optimization problems need branch-and-bound, integer programming, local search, or specialized solvers.
Branch and Bound
Branch and bound prunes partial assignments that cannot beat the best known solution.
if lower_bound(partial_assignment) >= best_score:
skip this branch
This requires a problem-specific lower bound. For scheduling, the lower bound might be the cost already assigned. For routing, it might be current path cost plus a heuristic estimate.
The important pattern is:
search + feasibility pruning + objective pruning
Testing
Test a satisfiable problem.
def test_map_coloring_solution():
problem = Problem(
variables=["A", "B"],
domains={
"A": ["red", "green"],
"B": ["red", "green"],
},
constraints=[
not_equal("A", "B"),
],
)
solution = solve(problem)
assert solution is not None
assert solution["A"] != solution["B"]
Test an unsatisfiable problem.
def test_unsatisfiable_problem():
problem = Problem(
variables=["A", "B"],
domains={
"A": ["red"],
"B": ["red"],
},
constraints=[
not_equal("A", "B"),
],
)
assert solve(problem) is None
Test all solutions.
def test_all_solutions():
problem = Problem(
variables=["A", "B"],
domains={
"A": [1, 2],
"B": [1, 2],
},
constraints=[
not_equal("A", "B"),
],
)
solutions = solve_all(problem)
assert len(solutions) == 2
These tests verify satisfiability, unsatisfiability, and enumeration.
Common Bugs
The most common constraint solver bug is writing predicates that fail on partial assignments. A constraint should usually return true until all required information is available.
Another common bug is mutating domains in place during search and failing to restore them. Copy domains or maintain an undo stack.
Variable ordering can dominate performance. A solver that works on small examples may fail badly without MRV or forward checking.
All-different constraints implemented as pairwise inequalities are simple but can be inefficient for large groups.
Returning the first solution can hide better solutions when an objective exists.
Recursive search can produce huge solution sets. Add limits or streaming iteration when enumeration is requested.
Failure messages that only say “no solution” are not useful. Expose at least the violated constraint for local failures.
Recipe
Build the solver in layers.
Represent variables, domains, and constraints explicitly. Write constraints so they tolerate partial assignments. Implement plain backtracking first. Add consistency checking after every assignment. Add all-solution enumeration when needed. Add MRV and degree heuristics to reduce search. Add forward checking to prune domains earlier. Add least-constraining-value ordering for dense problems. Add failure explanations for diagnostics. Add branch-and-bound when optimizing an objective.
The main lesson is that a constraint solver is controlled search. The correctness comes from complete backtracking over finite domains. The performance comes from pruning, ordering, propagation, and problem-specific bounds.