[1] A solution is therefore an assignment of values to the variables that satisfies all constraints—that is, a point in the feasible region.
Constraint propagation methods are also used in conjunction with search to make a given problem simpler to solve.
Constraint satisfaction as a general problem originated in the field of artificial intelligence in the 1970s (see for example (Laurière 1978)).
However, when the constraints are expressed as multivariate linear equations defining (in)equalities, the field goes back to Joseph Fourier in the 19th century: George Dantzig's invention of the simplex algorithm for linear programming (a special case of mathematical optimization) in 1946 has allowed determining feasible solutions to problems containing hundreds of variables.
As originally defined in artificial intelligence, constraints enumerate the possible values a set of variables may take in a given world.
In some circumstances, there may exist additional requirements: one may be interested not only in the solution (and in the fastest or most computationally efficient way to reach it) but in how it was reached; e.g. one may want the "simplest" solution ("simplest" in a logical, non-computational sense that has to be precisely defined).
One of the most-used constraints is the (obvious) one establishing that the values of the affected variables must be all different.
Arithmetic equations and inequalities are often not considered within the definition of a "constraint satisfaction problem", which is limited to finite domains.
It can be shown that the arithmetic inequalities or equations present in some types of finite logic puzzles such as Futoshiki or Kakuro (also known as Cross Sums) can be dealt with as non-arithmetic constraints (see Pattern-Based Constraint Satisfaction and Logic Puzzles[4]).
Constraint satisfaction problems on finite domains are typically solved using a form of search.
Equations of terms, as used in logic programming, are considered a particular form of constraints, which can be simplified using unification.
As a result, the constraint store can be considered an extension of the concept of substitution that is used in regular logic programming.