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

ProblemVariablesDomainConstraints
8-queensposition of each queen (e.g. = row of queen in column 1)squares, no two queens share a row, column or diagonal
SEND + MORE = MONEYD, E, M, N, O, R, S, Yall different; column sums e.g. or ; ,
Minesweeperthe hidden cells = {safe, mine}each number equals the sum of its neighbouring cells
Map colouringcountries {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

PartCSP version
Statesvalues assigned so far
Initial stateall variables unassigned
Actionsassign a value to an unassigned variable
Goal testall 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.