Definition
Colour a map of India's states so that no two neighbouring states share a colour, using only four colours. Or fill a Sudoku. Or schedule exams so no student has two at once. These puzzles share one structure.
A constraint satisfaction problem (CSP) has a set of variables, a domain of possible values for each, and constraints restricting which combinations of values are allowed. A solution assigns a value to every variable so that all constraints are satisfied. CSPs are solved by backtracking search combined with constraint propagation, which removes impossible values early, and with heuristics for choosing which variable to assign next.
In simple words
In a Sudoku, each empty square is a variable, the digits 1 to 9 are its possible values, and the rules, no repeat in any row, column or box, are the constraints. Writing small pencil marks of what is still possible in each square is constraint propagation; trying a digit and rubbing it out when it leads to a contradiction is backtracking.
Overview
- A constraint satisfaction problem (CSP) has variables, a domain of values for each and constraints on combinations.
- A solution assigns a value to every variable so that all constraints hold.
- Backtracking search assigns variables one at a time and undoes choices that break constraints.
- Constraint propagation removes impossible values early and shrinks the search dramatically.
- Heuristics such as minimum remaining values decide which variable to assign next.
- Timetables, Sudoku, map colouring and seating plans are all CSPs.
Why it matters
Many real problems are CSPs: timetabling, staff rostering, assigning frequencies to mobile towers, configuring products and scheduling factory machines. Describing a problem as a CSP lets general, powerful solvers handle it.
Key terms
- Variable
- Something that needs a value, such as a Sudoku square or an exam's time slot.
- Domain
- The set of values a variable may take.
- Constraint
- A rule restricting combinations, such as "neighbouring regions differ".
- Backtracking
- Assigning values one variable at a time and undoing an assignment when it causes a contradiction.
- Forward checking and arc consistency
- Propagation methods that remove values from neighbours' domains which can no longer work.
- MRV heuristic
- Minimum remaining values: assign next the variable with the fewest legal values left.
Types
Constraints come in several types, and CSPs are solved with several types of technique. Both are described here.
1. Unary, binary and global constraints
Unary constraints involve one variable, binary two, and global constraints any number.
- How it works: Unary constraints shrink a domain directly; binary constraints link pairs; global constraints such as AllDifferent cover many variables at once.
- Example: "Maths cannot be on Monday" (unary); "Maths and Physics not at the same time" (binary); "all nine digits in a Sudoku row differ" (global).
- When to use it: Use global constraints where possible; solvers handle them much more efficiently than many binary ones.
2. Hard and soft constraints
Hard constraints must be satisfied; soft constraints are preferences with a cost if broken.
- How it works: Problems with soft constraints become optimisation problems that minimise the total penalty.
- Example: "No teacher in two rooms at once" is hard; "Teachers prefer no classes after 4 p.m." is soft.
- When to use it: Use both when modelling real schedules, which are full of preferences.
3. Backtracking search
Depth-first assignment of variables with undoing on failure.
- How it works: Choose a variable, try each value consistent with constraints, recurse, and backtrack when a variable has no valid value left.
- Example: Filling a Sudoku cell by cell, erasing when a row clashes.
- When to use it: Use it as the core algorithm, improved with the heuristics and inference below.
4. Constraint propagation (forward checking and arc consistency)
Inferring which values are now impossible and removing them.
- How it works: Forward checking removes values from neighbours of the assigned variable; AC-3 makes every pair of variables arc-consistent before or during search.
- Example: Placing a 5 in a Sudoku cell removes 5 from every cell in its row, column and box.
- When to use it: Use it to detect dead ends early; easy Sudokus are solved by propagation alone.
5. Variable and value ordering heuristics
Rules for choosing which variable to assign next and which value to try first.
- How it works: Minimum remaining values picks the most constrained variable; the degree heuristic breaks ties; least-constraining value tries the value that leaves the most options for others.
- Example: In map colouring, colour the region with the fewest colours left first.
- When to use it: Use them to make backtracking practical on large problems.
Explained in detail
Formulating CSPs
| Problem | Variables | Domains | Constraints |
|---|---|---|---|
| Map colouring | Each state | {red, green, blue, yellow} | Neighbouring states differ |
| Sudoku | Each empty square | {1, …, 9} | No repeats in any row, column or 3 × 3 box |
| Exam timetable | Each exam | Available time slots | Exams sharing students get different slots; room capacity |
| N-queens | The column of the queen in each row | {1, …, N} | No two queens share a column or diagonal |
Backtracking plus propagation
Plain backtracking picks an unassigned variable, tries each value, and moves on if no constraint is broken, undoing the choice and trying the next value if it gets stuck. On its own this can be slow, because it may discover a dead end only many steps later. Forward checking speeds it up: after each assignment, remove now-impossible values from neighbouring variables' domains, and backtrack at once if any domain becomes empty. Arc consistency, used in the AC-3 algorithm published by Alan Mackworth in 1977, propagates further, repeatedly removing values that have no compatible value in a neighbour. Easy Sudokus can be solved by propagation alone, with no guessing at all.
Choosing what to try next
- Minimum remaining values (MRV): assign the variable with the fewest options first; it fails fast if it is going to fail.
- Degree heuristic: break ties by choosing the variable involved in the most constraints.
- Least constraining value: try first the value that rules out the fewest options for neighbours.
- With these heuristics, problems such as a million queens on a million-by-million board become solvable.
The four-colour theorem, that any map can be coloured with at most four colours so that neighbours differ, was proved by Kenneth Appel and Wolfgang Haken in 1976 with the help of a computer, one of the first major proofs to rely on one. Today industrial constraint solvers, such as Google's OR-Tools, schedule airline crews, sports leagues and delivery fleets.
CSPs also connect to modern AI: language-model systems that must produce outputs obeying strict rules, such as valid timetables or JSON, increasingly combine the model's suggestions with a constraint solver that guarantees the rules are met.
Many CSPs also have preferences, not just rules, such as a teacher who would rather not teach first period.
How it works
- List the variables, their domains and the constraints.
- Choose the next variable with MRV.
- Try values, least constraining first.
- After each assignment, propagate: remove values that can no longer work.
- If a domain empties, backtrack and try the next value.
In code
# Colour some southern Indian states so that neighbours differ.
neighbours = {
"Kerala": ["Karnataka", "Tamil Nadu"],
"Tamil Nadu": ["Kerala", "Karnataka", "Andhra Pradesh"],
"Karnataka": ["Kerala", "Tamil Nadu", "Andhra Pradesh", "Telangana", "Goa", "Maharashtra"],
"Andhra Pradesh": ["Tamil Nadu", "Karnataka", "Telangana"],
"Telangana": ["Karnataka", "Andhra Pradesh", "Maharashtra"],
"Goa": ["Karnataka", "Maharashtra"],
"Maharashtra": ["Goa", "Karnataka", "Telangana"],
}
colours = ["red", "green", "blue"]
steps = 0
def consistent(state, colour, assignment):
return all(assignment.get(n) != colour for n in neighbours[state])
def backtrack(assignment, domains):
global steps
if len(assignment) == len(neighbours):
return assignment
state = min((s for s in neighbours if s not in assignment), key=lambda s: len(domains[s])) # MRV
for colour in domains[state]:
steps += 1
if consistent(state, colour, assignment):
pruned = {n: [c for c in domains[n] if c != colour] if n in neighbours[state] else domains[n] for n in domains}
if all(pruned[n] for n in neighbours if n not in assignment and n != state): # forward checking
result = backtrack({**assignment, state: colour}, pruned)
if result:
return result
return None
solution = backtrack({}, {s: list(colours) for s in neighbours})
for state, colour in solution.items():
print(f"{state:>15}: {colour}")
print("Assignments tried:", steps)Output
Kerala: red
Tamil Nadu: green
Karnataka: blue
Andhra Pradesh: red
Telangana: green
Maharashtra: red
Goa: green
Assignments tried: 7Try it yourself
Timetabling exams
A college must place 8 exams into 4 time slots so that no student has two exams at once.
Match the CSP part
For Sudoku, what is each part?
- Variable
- Domain
- Constraint
- Propagation
Common mistakes
- Using plain backtracking without propagation on large problems.
- Choosing variables in a fixed order instead of by MRV.
- Leaving out a real-world constraint, so the solution is unusable.
Check yourself
Summary
- A CSP has variables, domains and constraints; a solution satisfies them all.
- Backtracking with propagation such as forward checking and arc consistency solves them efficiently.
- Heuristics such as MRV choose the next variable wisely; timetables and rosters are real CSPs.
Read it. Now try it yourself.
Open the interactive activityFinished reading?
Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · UC Berkeley CS188: Introduction to Artificial Intelligence