Skip to content

Artificial intelligence

Textbooks

Constraint satisfaction problems (CSPs)

https://en.wikipedia.org/wiki/Constraint_satisfaction_problem

The input to a CSP are a set of nodes, a set of constraints between those nodes, and domains of labels that can be assigned to those nodes. The goal of a CSP is to assign labels to the nodes such that the constraints are not violated.

For example, given:

  • is a set of variables,
  • is a set of their respective domains of values, and
  • is a set of constraints,

the goal of a CSP is to chose a label for each from its corresponding domain such that none of the constraints are violated.

A programming paradigm (Constraint programming) has been developed for solving CSPs. For an example, see the Google OR-tools package.

Boolean satisfiability problems (SAT) can be throught of as a subset of CSPs, and it is often possible to represent a CSP as a SAT problem and vice versa (see Principles and Practice of Constraint Programming – CP 2000 and SAT v CSP).