4.11 Constraint satisfaction problems

What this is and why it exists

Every search algorithm so far has treated a state as a lump. It could ask "is this the goal?" and "what states follow it?", and nothing else. A constraint problem gives the algorithm the one thing that formulation hides: the inside of a state. Once the solver can see that a state is a set of variables with values, two things become possible that were not possible before. It can notice that an assignment has already made the rest of the problem impossible, long before it reaches a dead end. And it can decide what to work on next, rather than taking whatever the successor function happens to hand it. That is why one general solver beats a hand-written search on timetabling, scheduling and a large family of puzzles.

The vocabulary

• Variable — a thing that needs a value.
• Domain — the set of values one variable is allowed to take.
• Constraint — a rule saying which combinations of values are allowed.
• Constraint graph — variables as nodes, constraints as edges between them.
• Consistent assignment — a partial assignment violating no constraint.
• Complete assignment — one where every variable has a value.
• Backtracking search — assign one variable, recurse, undo on failure.
• Forward checking — after an assignment, delete the values it rules out elsewhere.
• Arc consistency — repeat that deletion until nothing more can be deleted.

The mental model

Write the problem down as three lists and the solver comes free. The variables, the values each may take, and the rules relating them. Map colouring: one variable per region, the colours as the domain, and one rule per pair of neighbouring regions saying their colours differ. Eight queens: one variable per column, the row as the value, and rules saying no two share a row or a diagonal. A timetable: one variable per class, a room-and-slot pair as the value, and rules saying nothing double-books a room or a teacher. Three problems that look nothing alike turn out to be the same shape, and that is the whole return on the formulation.

Draw the constraint graph and you can see the difficulty. A node per variable, an edge wherever a rule relates two of them. A problem whose graph falls into separate pieces is really several small problems and should be solved that way. A problem whose graph is a tree can be solved without any search at all, in time linear in the number of variables. Everything in between is where the search methods earn their place, and every ordering rule below is reading something off this picture.

Backtracking search is depth-first search that knows what it is looking at. Choose an unassigned variable, try a value, check the rules that value touches, and recurse. If nothing works, undo the last assignment and try the next value. It looks like plain depth-first search and it is far better, for a reason worth stating: assignments commute. Colouring region A red then region B blue reaches the same state as doing it the other way round. A general search treats those as two different sequences and explores both; a constraint solver fixes an order and explores each set of choices once. That alone removes a factorial amount of work.

Most of the speed, though, comes from not searching. After each assignment, look at the neighbours in the graph and delete from their domains any value the assignment has ruled out. That is forward checking, and it turns a failure you would have found ten levels down into one you find now — a variable whose domain has gone empty means this line is dead. Arc consistency pushes the same idea further: keep deleting until no deletion is possible anywhere, not only next to the last assignment. On map colouring with three colours this often solves the problem outright with no search at all.

Then decide what to look at next, because the order is not neutral. Three rules do most of the work, and they pull in a sensible direction once you see what each is for.

Choose the most constrained variable — the one with the fewest values left. It is the one most likely to fail, and finding out now is cheaper than finding out after twenty more assignments. This is the single most valuable of the three, and it is the opposite of what feels natural.

Break ties with the most constraining variable — the one involved in the most rules with unassigned variables. Fixing it prunes the most elsewhere.

Then choose the least constraining value — the one that rules out fewest options for the neighbours. The reasoning is different here and worth noticing: you are choosing a variable you expect to fail on, and a value you expect to succeed with, so the two rules are not contradicting each other.

When search still stalls, the local methods from the previous topic apply here too. Start from a complete assignment that breaks some rules, and repeatedly reassign the variable involved in the most violations to the value that violates fewest. It is hill climbing with a problem-specific move, it has the same failure at local minima, and with random restarts it solves n-queens for very large n in about the same time regardless of size. Two methods, both correct, and the one to reach for depends on whether you need every solution or one.

What you should now be able to explain or do

State a problem as variables, domains and constraints, and check the statement by finding a rule you left out. Draw the constraint graph, and read off whether it separates, is a tree, or needs real search. Run backtracking search by hand, and explain the commuting argument for why it beats generic depth-first search. Apply forward checking after an assignment, and arc consistency to a whole problem. Order variables by most constrained and most constraining, and values by least constraining, and say why the two directions are not in conflict. Solve map colouring, n-queens and a small timetable in this formulation.

Check yourself