Constraint Satisfaction Problems

AI · Intermediate

Definition

CSPs assign values to variables so all constraints hold, e.g. map coloring or Sudoku.

General framework for scheduling and puzzles.

Diagram

Flowchart

Example: Map coloring

nb = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}
col = {}
def go(vs):
    if not vs: return True
    v = vs[0]
    for c in 'RGB':
        if all(col.get(u) != c for u in nb[v]):
            col[v] = c
            if go(vs[1:]): return True
            del col[v]
    return False
go(list(nb)); print(col)

Output: {'A': 'R', 'B': 'G', 'C': 'B'}

Key points

MRV heuristic picks the most constrained variable
Arc consistency (AC-3) prunes domains

Interview questions

What is forward checking?

After assigning a variable, remove inconsistent values from neighbors' domains.