Skip to content
learn
  1. Learn
  2. Artificial Intelligence
  3. Intelligent Agents and Problem Solving by Search

AI AI-01.08

Constraint satisfaction problems

Variables, domains and constraints; backtracking, forward checking and arc consistency, with a Sudoku solver that shows every propagation step.

Intermediate 12 min Last reviewed

The big idea

Some problems are not about finding a route but about filling in blanks so that every rule holds. A Sudoku: put a digit in each empty square so that no row, column or box repeats. A timetable: give each exam a slot so that no student has two at once. A map: colour each region so that neighbours differ. The order in which you fill the blanks does not matter. Only the finished assignment does.

These are constraint satisfaction problemsA problem defined by variables, a domain of possible values for each, and constraints that restrict which combinations of values are allowed. A solution assigns every variable a value that satisfies all constraints. (CSPs), and their structure is a gift. A general search treats each state as a black box. A CSP solver can look inside: it knows which variables a constraint touches, so when it places one value it can immediately cross off the values that are now impossible elsewhere.

That is exactly how people solve Sudoku in pencil. You write a 5 in a square, then cross 5 off the little candidate lists in that row, column and box. When some square is left with a single candidate, you write it in, and cross that off too. Often the whole puzzle falls out with almost no guessing. This lesson turns that pencil work into algorithms.

How it works

Step 1: Variables, domains, constraints

A CSP has three parts:

  • Variables: the blanks. In Sudoku, the 81 squares.
  • Domains: the values each variable may take. In Sudoku, the digits 1 to 9 (or just the given digit for pre-filled squares).
  • Constraints: rules about which combinations are allowed. In Sudoku, "all different" for each row, column and box. Each "all different" over 9 squares can be written as pairwise "not equal" constraints, so every square has 20 peers it must differ from.

Constraints that involve two variables are binary, and a CSP with binary constraints can be drawn as a constraint graphA graph with one node per variable and an edge between every two variables that share a constraint.. The classic small example is colouring the regions of a map of Australia with three colours so that neighbouring regions differ:

Map colouring of Australia as a constraint graph, with forward checking after one assignment Seven regions as nodes: Western Australia, Northern Territory, South Australia, Queensland, New South Wales, Victoria and Tasmania. Edges join regions that share a border. Western Australia has been assigned red and glows. Its edges to Northern Territory and South Australia glow, and those two regions' domains have shrunk to green and blue. Queensland, New South Wales and Victoria still have red, green and blue. Tasmania has no edges. WA red NT green, blue SA green, blue Q red, green, blue NSW red, green, blue V red, green, blue T red, green, blue Figure 1. Edges join neighbouring regions, which must get different colours. Assigning WA = red lets forward checking cross red off its neighbours, NT and SA, along the glowing edges. Tasmania shares no border, so it is independent.

The basic solver is depth-first search with one twist. Backtracking searchDepth-first search for CSPs that assigns one variable at a time, checks the constraints immediately, and undoes the most recent choice when a variable has no consistent value left. assigns one variable at a time, and after each assignment checks whether any constraint is already broken. If it is, it tries the next value. If a variable has no value left that fits, it backtracks: it undoes the previous assignment and tries that variable's next value.

Backtracking is complete (it finds a solution if one exists), and checking constraints early prunes huge parts of the search tree. But on its own it is short-sighted. It only notices a problem when it reaches the variable that has no options left, which may be dozens of assignments after the choice that caused it.

Step 3: Forward checking

Forward checkingAfter each assignment, remove the assigned value from the domains of all unassigned neighbours, and backtrack at once if any domain becomes empty. looks one step ahead. After assigning a variable, cross its value off the domains of all its unassigned neighbours, as in Figure 1. If any neighbour's domain becomes empty, this assignment is already doomed: backtrack immediately, without waiting to reach that neighbour.

Step 4: Arc consistency

Forward checking only looks at the neighbours of the variable just assigned. Arc consistencyA binary constraint from X to Y is arc consistent if every value left in X's domain has at least one compatible value in Y's domain. AC-3 enforces this for every constraint. goes further. An arc from to is consistent if every value left in 's domain has at least one compatible value in 's domain. If a value of has no support, remove it. And because 's domain shrank, arcs pointing into might now fail too, so they are checked again. The standard algorithm, AC-3, keeps a queue of arcs and repeats this until nothing changes.

For Sudoku's "not equal" constraints, arc consistency reduces to the pencil rule: when a square is down to one candidate, cross that candidate off all of its peers, which may leave other squares with one candidate, and so on in a chain. Running arc consistency after every assignment is called maintaining arc consistency (MAC).

Step 5: Choosing what to try next

Two ordering heuristics make a dramatic difference:

  • Minimum remaining values (MRV): assign next the variable with the fewest values left in its domain. It is the "most constrained" variable, the one most likely to fail, so a doomed branch is discovered early. In Sudoku, fill the square with the fewest candidates first.
  • Least constraining value: when choosing a value for that variable, try first the one that rules out the fewest options for the neighbours, which keeps the most doors open.

The principle sounds backwards but works: choose the variable that is most likely to fail, then the value that is most likely to succeed.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Small grey digits are each square's remaining candidates (shown when the solver propagates). Try this:

  1. On the easy puzzle, run backtracking only. It works through the squares in reading order and needs 200 assignments, 151 of them later undone.
  2. Switch to forward checking, MRV. Watch the candidate lists shrink before anything is placed. It solves the puzzle with 49 assignments, one per empty square, and no backtracking at all.
  3. Switch to the hard puzzle. Plain backtracking gives up after 150,000 assignments. Forward checking with MRV solves it in 481, and arc consistency in 274, because its chains of crossings-off reach further than the immediate neighbours.

The same idea in code

AC-3 on a small timetabling CSP. Four talks share one room with four time slots, A must come before B, B and C before D, and C cannot share a slot with A or B:

ac3.pyruns with python3 (standard library)
from collections import deque
from itertools import product

# Four talks to place in time slots 1 to 4 of one room.
domains = {t: {1, 2, 3, 4} for t in "ABCD"}
before = lambda x, y: x < y
differ = lambda x, y: x != y
# (X, Y): test(value of X, value of Y)
constraints = {
    ("A", "B"): before,             # A is an intro to B
    ("B", "D"): before,             # B is an intro to D
    ("C", "D"): before,             # C is also needed before D
    ("A", "C"): differ,             # one room: different slots
    ("B", "C"): differ,
}
for (x, y), test in list(constraints.items()):  # add reverse arcs
    constraints[(y, x)] = lambda b, a, test=test: test(a, b)

def revise(x, y):
    """Drop values of x that have no supporting value in y."""
    test = constraints[(x, y)]
    bad = {a for a in domains[x]
           if not any(test(a, b) for b in domains[y])}
    domains[x] -= bad
    return bool(bad)

def ac3():
    queue = deque(constraints)
    while queue:
        x, y = queue.popleft()
        if revise(x, y):
            if not domains[x]:
                return False           # no value left: unsolvable
            # x shrank, so arcs pointing at x must be checked again
            queue.extend((z, w) for (z, w) in constraints
                         if w == x and z != y)
    return True

print("before:", {t: sorted(d) for t, d in domains.items()})
print("consistent:", ac3())
print("after: ", {t: sorted(d) for t, d in domains.items()})

# Arc consistency checks pairs only. The full solutions left:
for slots in product(*(sorted(domains[t]) for t in "ABCD")):
    v = dict(zip("ABCD", slots))
    if all(test(v[x], v[y]) for (x, y), test in constraints.items()):
        print("solution:", v)

Output

before: {'A': [1, 2, 3, 4], 'B': [1, 2, 3, 4], 'C': [1, 2, 3, 4], 'D': [1, 2, 3, 4]}
consistent: True
after:  {'A': [1, 2], 'B': [2, 3], 'C': [1, 2, 3], 'D': [3, 4]}
solution: {'A': 1, 'B': 2, 'C': 3, 'D': 4}
solution: {'A': 1, 'B': 3, 'C': 2, 'D': 4}
solution: {'A': 2, 'B': 3, 'C': 1, 'D': 4}

Without placing anything, arc consistency rules out half the slots: A cannot be in slot 3 or 4, D must be in 3 or 4, and so on. But note what it keeps: D = 3 survives, though none of the three full solutions uses it. Arc consistency checks constraints in pairs, and D = 3 has a partner in every pair (B = 2, C = 2), just never all at once. Propagation shrinks the search; it does not replace it.

Going deeper

Stronger consistency, at a price

Arc consistency is one level of a ladder. Path consistency checks triples of variables, and -consistency checks groups of . Each level removes more impossible values and costs more to enforce. Global constraints offer a middle way: an "all different" constraint over 9 squares can detect that 3 squares sharing only 2 possible digits is impossible, which pairwise checks never see. Sudoku players know this trick as "naked pairs". Real solvers use specialised propagators for common global constraints.

Structure helps

If the constraint graph is a tree (no cycles), a CSP can be solved in time linear in the number of variables: make it arc consistent from the leaves up, then assign from the root down, and no backtracking is ever needed. Independent parts can be solved separately: Tasmania in Figure 1 shares no border with anything, so it is a separate, trivial problem. Solvers look for such structure and exploit it.

Local search for CSPs

For huge CSPs, local search from Local search and optimization also works. Start with a complete but inconsistent assignment and repeatedly change the variable involved in the most conflicts to the value that causes the fewest (the min-conflicts heuristic). It solves very large instances of some problems, such as placing a million queens on a chessboard so that none attack each other, remarkably fast, and it is a natural fit for rescheduling, where yesterday's plan is a good starting point.

Trade-offs

OptionWins whenLoses when
Plain backtracking Tiny problems, or as a baseline to check other solvers Discovers dead ends late; exponential on hard instances
Backtracking + forward checking + MRV Most practical puzzles and schedules; cheap and simple Only looks one step ahead
Maintaining arc consistency Tightly constrained problems where chains of deductions matter More work per node; still needs search for the rest
Min-conflicts local search Very large problems, and repairing an existing schedule Incomplete: cannot prove that no solution exists

Common mistakes

  • Treating a CSP as a general search problem and ignoring its structure. The win comes from looking inside the constraints.
  • Choosing variables in a fixed order. MRV alone often turns hours into milliseconds.
  • Forgetting to restore pruned domain values when backtracking. The solver then misses solutions.
  • Assuming that arc consistency solves the problem. It removes impossible values but can leave several candidates, some of which appear in no solution.
  • Encoding "all different" only as pairwise constraints when a global propagator is available, and losing deductions such as naked pairs.

In the wild

Where you will see this: timetabling for schools, hospitals and airlines, sports league fixtures, factory and cloud job scheduling, and configuration tools that check which product options are compatible are all built on constraint solvers. Open-source solvers such as Google's OR-Tools CP-SAT and MiniZinc-based tools combine propagation, smart search ordering and learning from conflicts. Package managers solving dependency versions face the same kind of problem, often handed to a SAT solver, a close relative that works on true/false variables.

Check yourself

  1. In a timetabling CSP, which part is 'exam X and exam Y cannot be at the same time because a student takes both'?

    Show answer

    C. A constraint Variables are the exams, domains their possible slots; a rule about which combinations of slots are allowed is a constraint.

  2. You assign WA = red with forward checking. What happens next?

    Show answer

    B. Red is removed from the domains of WA's unassigned neighbours Forward checking prunes the assigned value from each unassigned neighbour, and backtracks only if some domain becomes empty.

  3. Which variable does the minimum remaining values heuristic pick?

    Show answer

    B. The one with the fewest values left The most constrained variable is most likely to fail, so trying it first finds dead ends early.

  4. After AC-3, D's domain is 3 or 4, but no solution uses D = 3. What does that show?

    Show answer

    B. Arc consistency checks constraints in pairs and cannot see every combination Each pair of constraints has support for D = 3, but no single assignment satisfies them all. Search is still needed.

  5. Why can a CSP whose constraint graph is a tree be solved without backtracking?

    Show answer

    B. Making it arc consistent from the leaves up guarantees every root-down choice can be extended With no cycles, a value that is arc consistent with its parent can always be matched by the children, so assigning from the root down never hits a dead end.

Recap

  • A CSP is variables, domains and constraints; a solution satisfies every constraint.
  • Backtracking assigns one variable at a time and undoes choices at dead ends.
  • Forward checking prunes a new value from neighbours at once; arc consistency (AC-3) chains those deductions further.
  • Minimum remaining values picks the most constrained variable first, finding dead ends early.
  • Propagation shrinks the search but does not replace it; structure such as trees can remove it entirely.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy