The Constraint Satisfaction Problem (CSP) is a well-known framework [1]} for modelling and solving search problems, which received
considerably attention in the literature due to its applicability in various areas.
Informally, a CSP instance is defined by singling out the variables of interest, and by listing the allowed combinations of values for groups
of them, according to the constraints arising in the application at hand. The solutions for this instance are the assignments of domain values
to variables that satisfy all such constraints. Many apparently unrelated problems from disparate areas actually turn out to be equivalent to
the CSP and can be accommodated within the CSP framework. Examples are puzzles, conjunctive queries over relational databases, graph
colorability,
and checking whether there is a homomorphism between two finite structures.
