Constraint satisfaction problems

Intermediate

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])
Open in compiler

Line by line

  1. The map has seven districts; neighbours lists the districts that touch each one, and there are three colours.
  2. fixed_order colours the districts in a poor order: North and South first, so both get red, which later traps East and Centre.
  3. It hits a dead end at Centre, backs up to West and East, and finds a colouring after 9 assignments.
  4. mrv_forward always picks the district with the fewest colours left, preferring the most connected, and removes each chosen colour from the neighbours' domains.
  5. 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

1. What is a solution to a CSP?
2. Which variable does MRV choose next?
3. What does forward checking do after an assignment?
4. What happens when backtracking finds no consistent value for a variable?

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.