2. Constraint Satisfaction Problems

Constraint Satisfaction Problem

We can break down a Constraint Satisfaction Problem (CSP) into:

• a finite set of variables $X\{x^1\dots x^n\}$ defines all elements that need to be given a value in the problem
• a set of domains $D\{D^1\dots D^i\}$ defines what possible values can be assigned to each variable $[v^1\dots v^j]$
• a set of constraints $C\{C^1\dots C^k\}$ rules that dictate a relation between variables in $X$ each constraint $C^i$ is a pairing of scope and relation

A CSP solution is an instance of all variables in $X$ using vales in $D$ that satisfies all constraints in $C$.

Link to original

Example: Map Colouring

In this example, we want to colour all the regions of this map with a different colour.

Example: $n$-Queens CSP

None of the queens can be in a position where they can be captured by another queen on a $n\times n$ board.

We can pick a finite set of variables $X=\{x_{i,j}\}$ which are all possible cells. A set of domains $D$ of either $1$ or $0$, whether there is a queen or not. And a set of constraints $C$ that define no adjacent / diagonal cells can both contain a queen.