Constraint Satisfaction Problems

Variables, domains, constraints

A constraint satisfaction problem (CSP) has variables, each with a domain of possible values, and constraints that restrict combinations. Map colouring, timetabling, Sudoku and resource allocation are CSPs. Backtracking search assigns variables one at a time and undoes choices that violate constraints. Heuristics make it fast: choose the most constrained variable first, try the least constraining value, and propagate constraints (forward checking, arc consistency) to prune impossible values early.

Colouring a map with three colours, run

I ran this with plain Python 3 (standard library only), with fixed random seeds where randomness is used. Backtracking with a most-constrained-variable heuristic colours seven regions so that no neighbours share a colour, trying only 11 colour assignments, and the solution is verified valid.

neighbours = {  # a small map: regions that share a border cannot share a colour
    "WA": ["NT", "SA"], "NT": ["WA", "SA", "Q"], "SA": ["WA", "NT", "Q", "NSW", "V"],
    "Q": ["NT", "SA", "NSW"], "NSW": ["Q", "SA", "V"], "V": ["SA", "NSW"], "T": []}
colours = ["red", "green", "blue"]
steps = 0
def backtrack(assign):
    global steps
    if len(assign) == len(neighbours): return assign
    # most-constrained variable first: the region with the fewest legal colours left
    var = min((v for v in neighbours if v not in assign),
              key=lambda v: sum(all(assign.get(n) != c for n in neighbours[v]) for c in colours))
    for c in colours:
        steps += 1
        if all(assign.get(n) != c for n in neighbours[var]):
            result = backtrack({**assign, var: c})
            if result: return result
    return None
solution = backtrack({})
print(solution)
print("colour assignments tried:", steps)
print("valid:", all(solution[a] != solution[b] for a in neighbours for b in neighbours[a]))

Output:

{'WA': 'red', 'NT': 'green', 'SA': 'blue', 'Q': 'red', 'NSW': 'green', 'V': 'red', 'T': 'red'}
colour assignments tried: 11
valid: True

Use a solver library

For real scheduling problems, model them for a constraint or integer programming solver (such as OR-Tools) rather than writing backtracking yourself.

Quick check: Which heuristic picks the next variable in backtracking?

• Most constrained variable first
• Alphabetical order always
• The variable with the most values left
• A random variable each time, ignoring constraints