- Algorithms for Decision Making: https://algorithmsbook.com/.
Constraint satisfaction problems (CSPs)
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.
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).