# Artificial intelligence

## 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:

• $X=\{X_{1},\ldots ,X_{n}\}$ is a set of variables,
• ${\displaystyle D=\{D_{1},\ldots ,D_{n}\}}D=\{D_{1},\ldots ,D_{n}\}$ is a set of their respective domains of values, and
• ${\displaystyle C=\{C_{1},\ldots ,C_{m}\}}C=\{C_{1},\ldots ,C_{m}\}$ is a set of constraints,

the goal of a CSP is to chose a label for each $X_i$ from its corresponding domain $D_i$ such that none of the constraints $C_k$ 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).