I4 · Problem Solving and Reasoning: Classical AI

Constraint Satisfaction Problems

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.

12 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

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

ProblemVariablesDomainsConstraints
Map colouringEach state{red, green, blue, yellow}Neighbouring states differ
SudokuEach empty square{1, …, 9}No repeats in any row, column or 3 × 3 box
Exam timetableEach examAvailable time slotsExams sharing students get different slots; room capacity
N-queensThe 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

  1. List the variables, their domains and the constraints.
  2. Choose the next variable with MRV.
  3. Try values, least constraining first.
  4. After each assignment, propagate: remove values that can no longer work.
  5. If a domain empties, backtrack and try the next value.

In code

map_colouring.py
# 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: 7

Try 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

Question 1

1. In map colouring, what are the constraints?

Question 2

2. What does forward checking do?

Question 3

3. Which variable does MRV choose next?

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 activity

Finished reading?

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · UC Berkeley CS188: Introduction to Artificial Intelligence