Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
A constraint satisfaction problem (CSP) asks for a state that satisfies a given set of constraints. Puzzles (8-queens, cryptarithmetic, sudoku, minesweeper, map colouring) and real problems (who teaches which class, timetabling, hardware configuration, transport and factory scheduling, floor planning) are CSPs.
Formulation
Three parts:
- variables
- domains , the values each variable may take
- constraints, which specify allowed combinations of values for subsets of variables (this is the goal test)
Definitions
Key terms:
- a state is an assignment of values to some or all variables
- a consistent (legal) assignment violates no constraint
- a complete assignment gives every variable a value
- a solution is a complete and consistent assignment
Examples
| Problem | Variables | Domain | Constraints |
|---|---|---|---|
| 8-queens | position of each queen (e.g. = row of queen in column 1) | squares, | no two queens share a row, column or diagonal |
| SEND + MORE = MONEY | D, E, M, N, O, R, S, Y | all different; column sums e.g. or ; , | |
| Minesweeper | the hidden cells | = {safe, mine} | each number equals the sum of its neighbouring cells |
| Map colouring | countries | {Red, Green, Blue} | neighbours differ, e.g. |
Types of constraint:
- unary: about one variable, e.g.
- binary: between two variables, e.g.
- constraints can be listed explicitly (allowed pairs like for two queens) or implicitly by a test function
As a Standard Search Problem
| Part | CSP version |
|---|---|
| States | values assigned so far |
| Initial state | all variables unassigned |
| Actions | assign a value to an unassigned variable |
| Goal test | all variables assigned, no constraint violated |
With variables, every solution is at depth exactly and the tree has depth , so depth-first search is the natural choice. Making it efficient is the job of Backtracking and CSP Heuristics.