Constraint programming is a programming paradigm in which a set of constraints that a solution must meet are specified rather than set of steps to obtain such a solution.
Constraint programming is related to logic programming and, since both are Turing-complete, any logic program can be translated into an equivalent constraint program and vice versa. This is sometimes useful in practice, since a constraint solving program may find an answer faster than a logic derivation program, and it might be desirable to perform this translation before executing a logic program.
The difference between the two is largely in their styles and approaches to modeling the world. Some problems are more natural (and thus, simpler) to write as logic programs, while some are more natural to write as constraint programs.
The constraint programming approach is to search for a state of the world in which a large number of constraints are satisfied at the same time. A problem is typically stated as a state of the world containing a number of unknown variables. The constraint program searches for values for all the variables.
Temporal concurrent constraint programming (TCC) and non-deterministic temporal concurrent constraint programming (NTCC) are variants of constraint programming that can deal with time.
Some popular application domains for constraint programming are:
- boolean domains, where only true/false constraints apply
- Integer domains, rational domains
- linear domains, where only linear functions are described and analyzed (although approaches to non-linear problems do exist)
- finite domains, where constraints are defined over countable sets
- Mixed domains, involving two or more of the above
Constraint laguages are typically embedded in a host language. The first host language used was a logic language (Prolog), so the field was initially called Constraint Logic Programming. The two paradigms share many important features, like logical variables (i.e., once a variable is assigned a value, it cannot be changed), backtracking. Nowadays, most Prolog implementations include one or more libraries for constraint logic programming.
Some popular constraint languages are:
- B-Prolog (Prolog based)
- Choco (Java based)
- Ciao Prolog (Prolog based)
- ECLiPSe (Prolog based)
- ILOG Solver (C++ based)
- Mozart (Oz based)
- SICStus (Prolog based)
- Koalog Constraint Solver (Java based)
Finite ___domain solvers are useful for solving Constraint satisfaction problems, and are often based on Arc-Consistency (see AC-3 algorithm), or one of its approximations.
References
 | This computing article is a stub. You can help Wikipedia by expanding it. |