Constraint Satisfaction
When the goal is not a path but an assignment. Variables, domains, and rules that must all hold at once, solved by backtracking that is smarter than brute force.
Sudoku, exam timetables, seating plans, and colouring a map so no two neighbours match all share a shape. You are not looking for a route from A to B. You are trying to assign values to a set of variables so that a list of rules is satisfied all at once. These are constraint satisfaction problems, and because they have this common structure, one general method solves all of them. Better still, a few simple tricks make that method dramatically faster.
A different shape of problem
In the search problems from earlier weeks, a state was a black box and the answer was a sequence of actions. A constraint satisfaction problem, or CSP, opens the box. It says a state is made of variables, each of which must be given a value, and there are constraints saying which combinations of values are allowed.
The goal is not a path but a complete, legal assignment: a value for every variable such that no constraint is broken. Because so many real problems fit this mould, treating them as CSPs lets us reuse one solver and one set of speed-up tricks everywhere.
Defining a CSP
Every CSP is described by three things. Learn these labels, because exam questions ask you to identify them for a given problem.
- Variables: the things that need a value. For map colouring, each region is a variable.
- Domains: the set of allowed values for each variable. For map colouring, the domain might be {red, green, blue}.
- Constraints: the rules restricting which combinations are legal. For map colouring, adjacent regions must have different colours.
| Problem | Variables | Domain | Constraint |
|---|---|---|---|
| Map colouring | Each region | The available colours | Adjacent regions differ |
| Sudoku | Each empty cell | Digits 1 to 9 | No repeat in row, column, or box |
| N-queens | Each queen (one per column) | The rows | No two queens attack each other |
| Exam timetable | Each exam | The time slots | Clashing exams get different slots |
The constraint graph
A CSP where each constraint links two variables can be drawn as a constraint graph: one node per variable, and an edge between any two variables that share a constraint. For map colouring, the graph has a node per region and an edge between every pair of neighbouring regions.
This picture is not just decoration. The shape of the graph tells the solver a lot: densely connected variables are the hardest to assign and should be tackled first, and separate components can be solved independently. Many of the speed-up tricks in section 5 are really about reading the constraint graph.
Backtracking search
The standard way to solve a CSP is backtracking search. It is depth-first search with one crucial addition: it checks constraints as it goes and abandons a path the moment it becomes illegal.
- Pick an unassigned variable.
- Try a value from its domain that does not break any constraint with already-assigned variables.
- If a legal value exists, assign it and move on to the next variable.
- If no legal value exists, backtrack: undo the previous assignment and try a different value there.
The word backtrack is the whole trick. Instead of building a full assignment and then checking it (hopeless, there are far too many), backtracking fails fast. The instant a variable has no legal value, it knows the current partial assignment is doomed and retreats, pruning away everything beneath it.
Making backtracking smart
Plain backtracking works, but a few well-known heuristics make it hugely faster by choosing what to do next more wisely and spotting dead ends earlier.
Choosing which variable to assign next
- Minimum remaining values (MRV): assign the variable with the fewest legal values left. Tackle the most constrained variable first, because if it is going to fail, fail now rather than after lots of wasted work.
- Degree heuristic: break ties by choosing the variable involved in the most constraints, the most connected node in the graph.
Choosing which value to try
- Least constraining value (LCV): prefer the value that rules out the fewest options for neighbouring variables, keeping future choices open.
Spotting dead ends early
- Forward checking: when you assign a value, immediately remove it from the domains of neighbouring variables. If any neighbour is left with no legal values, backtrack straight away rather than later.
- Constraint propagation (arc consistency, AC-3): go further and repeatedly prune domains across the whole graph, so that every variable is consistent with its neighbours. This often solves easy CSPs with almost no search at all.
Watch a map get coloured
Here is the classic example: colour the states of Australia with three colours so no two neighbouring states share a colour. The nodes are the states and the edges are the "must differ" constraints. Step through backtracking as it tries colours, hits a dead end, and backtracks to fix an earlier choice.
Each node is a state; an edge means the two states must have different colours. Three colours are available.
Key points and practice
- A CSP is defined by variables, domains, and constraints; the goal is a legal complete assignment.
- A constraint graph links variables that share a constraint and reveals structure to exploit.
- Backtracking search is depth-first search that checks constraints as it goes and retreats the moment a variable has no legal value.
- MRV and the degree heuristic choose which variable to assign; LCV chooses which value.
- Forward checking and arc consistency prune domains to spot dead ends early.
The variables are the regions to be coloured. The domain of each variable is the set of available colours, for example {red, green, blue}. The constraints state that any two regions sharing a border must be given different colours. A solution is an assignment of a colour to every region such that no bordering pair shares a colour.
Backtracking search assigns variables one at a time, checking constraints against already-assigned variables at each step, and undoes the most recent assignment as soon as a variable has no legal value. It differs from generate-and-test, which builds a complete assignment before checking it, by failing fast: it abandons a doomed partial assignment immediately, pruning away all the complete assignments that would have extended it and saving enormous effort.
MRV (minimum remaining values) chooses the next variable to assign as the one with the fewest legal values remaining, tackling the most constrained variable first so that failures are found early rather than deep in the search. Forward checking, after each assignment, removes that value from the domains of neighbouring variables, and if any neighbour is left with an empty domain the search backtracks immediately. Both speed up backtracking by detecting dead ends as early as possible instead of exploring branches that are already doomed.