# Constraint Satisfaction Problems — Artificial Intelligence

Source: https://www.skillbyai.com/en/artificial-intelligence/g-csp

> Find values that satisfy every rule.

## 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.

```python
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.

**Quiz:** Which heuristic picks the next variable in backtracking?

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

*Answer:* Most constrained variable first. Tackle the hardest choice early to fail fast.