Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

Examples of problems that can be modeled as a constraint satisfaction problem include:

These are often provided with tutorials of CP, ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include automated planning, lexical disambiguation, musicology, product configuration and resource allocation.

The existence of a solution to a CSP can be viewed as a decision problem. This can be decided by finding a solution, or failing to find a solution after exhaustive search (stochastic algorithms typically never reach an exhaustive conclusion, while directed searches often do, on sufficiently small problems). In some cases the CSP might be known to have solutions beforehand, through some other mathematical inference process.

Formally, a constraint satisfaction problem is defined as a triple ${\displaystyle \langle X,D,C\rangle }$, where

Each variable ${\displaystyle X_{i}}$ can take on the values in the nonempty domain ${\displaystyle D_{i}}$. Every constraint ${\displaystyle C_{j}\in C}$ is in turn a pair ${\displaystyle \langle t_{j},R_{j}\rangle }$, where ${\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}$ is a set of ${\displaystyle k}$ indices and ${\displaystyle R_{j}}$ is a ${\displaystyle k}$-ary relation on the corresponding product of domains ${\displaystyle \times _{i\in t_{j}}D_{i}}$ where the product is taken with indices in ascending order. An evaluation of the variables is a function from a subset of variables to a particular set of values in the corresponding subset of domains. An evaluation ${\displaystyle v}$ satisfies a constraint ${\displaystyle \langle t_{j},R_{j}\rangle }$ if the values assigned to the variables ${\displaystyle t_{j}}$ satisfy the relation ${\displaystyle R_{j}}$.

An evaluation is consistent if it does not violate any of the constraints. An evaluation is complete if it includes all variables. An evaluation is a solution if it is consistent and complete; such an evaluation is said to solve the constraint satisfaction problem.

Constraint satisfaction problems on finite domains are typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and local search. These techniques are also often combined, as in the VLNS method, and current research involves other technologies such as linear programming.