Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 46 ยท Constraint Satisfaction

Constraint Satisfaction Problems

Learn to model puzzles as constraint satisfaction problems: variables, domains, constraints and constraint graphs, with map colouring, Sudoku and scheduling and a reusable Python CSP class.

In the search lessons a state was a black box: the algorithm knew how to expand it and test it for the goal, and nothing else. That generality is a strength, but it throws away useful structure. Many problems are really "fill in these blanks without breaking any rules": colour a map, fill a Sudoku grid, schedule exams, assign nurses to shifts. For these, a more specific representation lets the solver reason about the rules, and that makes a huge difference in speed.

That representation is the constraint satisfaction problem (CSP). In this lesson you will learn its three ingredients, how to draw the constraint graph, how to model three classic problems, and how to write a small Python CSP class that the next two lessons will build on.

The three ingredients

A CSP consists of:

  • a set of variables X1 ... Xn,
  • a domain for each variable: the set of values it may take,
  • a set of constraints: rules that restrict which combinations of values are allowed.

An assignment gives values to some or all variables. It is consistent (or legal) if it violates no constraint, complete if every variable has a value, and a solution if it is both. A partial assignment leaves some variables unassigned.

The constraints are where the power lies. A constraint over two variables is binary (for example "A and B must differ"), one over a single variable is unary ("Q is not Monday"), and one over three or more is higher-order (for example "these five cells are all different"). Any higher-order constraint on finite domains can be rewritten as binary ones, so many solvers work with binary constraints only. We will do the same.

The constraint graph

For binary CSPs there is a handy picture. Draw one node per variable and one edge for every constraint between two variables. This is the constraint graph, and it shows the problem's structure at a glance: which variables interact, and which are independent.

Example 1: map colouring

Colour the regions of Australia so that neighboring regions get different colours, using three colours. The variables are the regions, the domain of each is {red, green, blue}, and the constraints say that each pair of adjacent regions must differ.

graph TD
    WA --- NT
    WA --- SA
    NT --- SA
    NT --- Q
    SA --- Q
    SA --- NSW
    SA --- V
    Q --- NSW
    NSW --- V

The constraint graph for the mainland Australian regions. Tasmania (T) has no neighbors, so it is an isolated node and a completely independent sub-problem.

Notice that Tasmania is not connected to anything. A solver that sees the graph can solve it separately. A black-box search algorithm would never notice.

A Python CSP class

Let us encode this. We store the domains, the binary constraints (each is a function of two values), and precompute each variable's neighbors, because the next lessons need them constantly.

Python A reusable CSP class and map colouring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Brute force works here because the space is tiny: 3^7 = 2,187 complete assignments. The program finds 18 solutions. That is 6 colourings of the connected mainland (the three colours can be permuted, and the mainland forces most of the rest) times 3 free choices for Tasmania. In the next lesson you will see how a smarter search avoids looking at almost all of those assignments.

Why the arrangement a < b in conflicts? We store every constraint in both directions so lookups are easy. Checking only the pairs where a < b makes sure each constraint is tested once.

Example 2: Sudoku

Sudoku fits the CSP template perfectly.

  • Variables: the 81 cells.
  • Domains: {1, ..., 9}, or just the single given digit for cells that are pre-filled.
  • Constraints: the nine cells of each row, each column and each 3x3 box must be all different. That is 27 all-different groups.

Every all-different group of 9 cells expands into 36 binary "not equal" constraints. A cell sees 8 cells in its row, 8 in its column and 4 more in its box (the other 4 box cells are already in its row or column), which makes 20 neighbors.

Python Sudoku as a CSP: count variables and constraints

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output confirms 81 variables, 27 groups, 810 distinct binary constraints and 20 neighbors per cell. The numbers 81 * 20 / 2 = 810 agree.

Example 3: scheduling

Imagine a school has five exams, and some students sit more than one of them. Two exams that share a student cannot take place in the same time slot. This is a colouring problem in disguise: variables are exams, values are slots, and an edge links every pair of exams with a common student.

Python Exam scheduling as a CSP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With three slots there are 12 valid timetables; with two slots there are none, because Math, History and Music form a triangle of conflicts (Ben takes Math and History, Dev takes History and Music, Eli takes Music and Math) and three mutually conflicting exams need three different slots. A problem with no solutions is over-constrained; one with very many is under-constrained. A well-posed puzzle such as a published Sudoku has exactly one solution.

Why model things this way?

A generic search treats a state as a lump. A CSP exposes three kinds of reasoning that the following lessons exploit:

  1. Order does not matter. Assigning WA=red then NT=green gives exactly the same partial assignment as NT=green then WA=red. A CSP search can therefore pick any variable to assign next, whichever is smartest, without losing solutions. This is the idea behind backtracking search.
  2. Early failure detection. If any constraint is already violated by a partial assignment, you can abandon it immediately, long before it becomes a complete assignment.
  3. Inference. Removing impossible values from domains (see constraint propagation) can shrink the search drastically or solve the problem outright.

Real-world CSPs include timetabling, resource allocation, configuration of products (which options are compatible), register allocation in compilers, and crossword compilation. Industrial constraint programming solvers such as OR-Tools CP-SAT and Gecode build on exactly these ideas, adding rich global constraints and better inference.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which three things define a CSP?

    A CSP is a set of variables, a domain of values for each, and constraints that restrict which combinations are allowed.
  2. 2. What does an edge in a constraint graph represent?

    Nodes are variables and an edge joins two variables that appear together in a constraint. The graph shows how the problem is connected.
  3. 3. In the Sudoku CSP, how many neighbors does each cell have?

    A cell shares a constraint with 8 cells in its row, 8 in its column and 4 more cells in its box that are not already in its row or column, making 20.
  4. 4. Why can a CSP solver choose any variable to assign next?

    Assigning variables in a different order reaches the same partial assignment, so the solver can use the order that detects failures soonest without losing any solution.
  5. 5. An assignment that gives values to every variable but violates a constraint is...

    Complete means every variable has a value; consistent means no constraint is violated. A solution needs both.

Summary

  • A CSP has variables, domains and constraints; a solution is a complete, consistent assignment.
  • Binary constraints can be drawn as a constraint graph, which reveals independent sub-problems.
  • Map colouring, Sudoku (81 variables, 810 binary constraints, 20 neighbors per cell) and scheduling are all CSPs.
  • A small CSP class with domains, constraint functions and a neighbor table is enough to start experimenting.
  • Because assignment order is irrelevant, CSP solvers can choose smart variable orders and detect failures early.

Next: Backtracking Search for CSPs.