Introduction
Colouring a map so that neighbours differ, filling in a Sudoku, building a timetable with no clashes: these problems look different, but each asks for values for a set of variables that satisfy a set of rules. Written as a constraint satisfaction problem (CSP), they can all be solved by the same general algorithm, which takes advantage of the structure that ordinary search ignores.
How it works
A CSP has:
- variables, such as the regions of a map or the cells of a Sudoku;
- a domain for each variable: its possible values, such as {red, green, blue} or 1–9;
- constraints, such as "neighbouring regions have different colours" or "no digit twice in a row".
A solution is a complete, consistent assignment: every variable has a value and no constraint is broken.
Backtracking search assigns one variable at a time. For each value in the variable's domain that is consistent with the values already assigned, it assigns it and continues with the next variable. When a variable has no consistent value left, it backtracks: it undoes the most recent assignment and tries that variable's next value. Because it checks constraints immediately, it never extends an assignment that is already broken.
Two improvements make a large difference:
- Minimum remaining values (MRV): assign next the variable with the fewest legal values left. If one has none, the search fails now instead of much later. Ties are often broken by choosing the variable with the most constraints on others (the degree heuristic).
- Forward checking: after assigning a value, remove it from the domains of the unassigned neighbours it conflicts with. If a neighbour's domain becomes empty, this value cannot work, so try the next one at once.
Syntax
def backtrack(assignment):
if complete(assignment): return assignment
var = choose_variable(assignment) # e.g. MRV
for value in domain(var):
if consistent(var, value, assignment):
assignment[var] = value
if (result := backtrack(assignment)): return result
del assignment[var]
return None
Example
neighbours = {
"North": ["West", "East", "Centre"],
"West": ["North", "South", "Centre"],
"South": ["West", "East", "Centre", "Harbour"],
"East": ["North", "South", "Centre", "Harbour"],
"Centre": ["North", "West", "South", "East"],
"Harbour": ["South", "East"],
"Island": [],
}
COLOURS = ["red", "green", "blue"]
def fixed_order(order, assignment, count):
if len(assignment) == len(order):
return dict(assignment)
region = order[len(assignment)]
for colour in COLOURS:
if all(assignment.get(n) != colour for n in neighbours[region]):
assignment[region] = colour
count[0] += 1
found = fixed_order(order, assignment, count)
if found:
return found
del assignment[region]
return None
def mrv_forward(domains, assignment, count):
if len(assignment) == len(neighbours):
return dict(assignment)
region = min(
(r for r in neighbours if r not in assignment),
key=lambda r: (len(domains[r]), -len(neighbours[r])),
)
for colour in [c for c in COLOURS if c in domains[region]]:
narrowed = {r: set(d) for r, d in domains.items()}
narrowed[region] = {colour}
for n in neighbours[region]:
if n not in assignment:
narrowed[n].discard(colour)
if all(narrowed[n] for n in neighbours[region]):
assignment[region] = colour
count[0] += 1
found = mrv_forward(narrowed, assignment, count)
if found:
return found
del assignment[region]
return None
order = ["North", "South", "Island", "Harbour", "West", "East", "Centre"]
count = [0]
print("fixed order:", fixed_order(order, {}, count))
print(" assignments:", count[0])
count = [0]
print("MRV + forward checking:", mrv_forward({r: set(COLOURS) for r in neighbours}, {}, count))
print(" assignments:", count[0])Line by line
- The map has seven districts;
neighbourslists the districts that touch each one, and there are three colours. fixed_ordercolours the districts in a poor order: North and South first, so both get red, which later traps East and Centre.- It hits a dead end at Centre, backs up to West and East, and finds a colouring after 9 assignments.
mrv_forwardalways picks the district with the fewest colours left, preferring the most connected, and removes each chosen colour from the neighbours' domains.- It never needs to back up: 7 assignments for 7 districts.
Expected result
fixed order: {'North': 'red', 'South': 'red', 'Island': 'red', 'Harbour': 'green', 'West': 'blue', 'East': 'blue', 'Centre': 'green'}
assignments: 9
MRV + forward checking: {'South': 'red', 'East': 'green', 'Centre': 'blue', 'North': 'red', 'West': 'green', 'Harbour': 'blue', 'Island': 'red'}
assignments: 7
In the real world
Timetabling for schools and airlines, register allocation in compilers, configuring products from compatible parts, and scheduling hospital shifts are all solved with constraint solvers. Industrial tools such as Google's OR-Tools CP-SAT solver combine backtracking with powerful propagation and learning, and solve problems with millions of constraints.
Common mistakes
- Checking constraints only when the assignment is complete, which is generate-and-test and hopelessly slow.
- Forgetting to undo an assignment when backtracking, or to restore domains after forward checking.
- Choosing variables in a fixed order when MRV would detect failures much earlier.
- Modelling with the wrong variables, such as one variable per digit instead of one per cell.
Best practices
- Write a function that checks a complete assignment, and use it to test the solver.
- Use MRV with the degree heuristic as a tie-breaker; it rarely hurts.
- Count assignments to compare improvements.
Summary
A CSP is a set of variables with domains and constraints. Backtracking search assigns variables one at a time and backs up at dead ends. MRV chooses the most constrained variable and forward checking prunes neighbours' domains, so dead ends appear sooner and the search shrinks.
Quick check
Key takeaways
- Many puzzles and scheduling problems are CSPs and can share one solver.
- Backtracking checks constraints as it goes, so it abandons bad partial assignments early.
- MRV and forward checking find dead ends sooner, often cutting the search dramatically.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.