Editing Constraint satisfaction (section)

==Constraint programming==
{{main|Constraint programming}}

Constraint programming is the use of constraints as a programming language to encode and solve problems. This is often done by embedding constraints into a [[programming language]], which is called the host language. Constraint programming originated from a formalization of equalities of [[term (logic)|term]]s in [[Prolog II]], leading to a general framework for embedding constraints into a [[logic programming]] language. The most common host languages are [[Prolog]], [[C++]], and [[Java (programming language)|Java]], but other languages have been used as well.

===Constraint logic programming===
{{main|Constraint logic programming}}

A constraint logic program is a [[Logic programming|logic program]] that contains constraints in the bodies of clauses. As an example, the clause <code>A(X):-X>0,B(X)</code> is a clause containing the constraint <code>X>0</code> in the body. Constraints can also be present in the goal. The constraints in the goal and in the clauses used to prove the goal are accumulated into a set called [[constraint store]]. This set contains the constraints the interpreter has assumed satisfiable in order to proceed in the evaluation. As a result, if this set is detected unsatisfiable, the interpreter backtracks. Equations of terms, as used in logic programming, are considered a particular form of constraints, which can be simplified using [[unification (computing)|unification]]. As a result, the constraint store can be considered an extension of the concept of [[substitution (logic)|substitution]] that is used in regular logic programming. The most common kinds of constraints used in constraint logic programming are constraints over integers/rational/real numbers and constraints over finite domains.

[[Concurrent constraint logic programming]] languages have also been developed. They significantly differ from non-concurrent constraint logic programming in that they are aimed at programming [[concurrent process]]es that may not terminate. [[Constraint handling rules]] can be seen as a form of concurrent constraint logic programming, but are also sometimes used within a non-concurrent constraint logic programming language. They allow for rewriting constraints or to infer new ones based on the truth of conditions.

===Constraint satisfaction toolkits===

Constraint satisfaction toolkits are [[Software library|software libraries]] for [[imperative programming language]]s that are used to encode and solve a constraint satisfaction problem.

* [[Cassowary constraint solver]], an [[open source]] project for constraint satisfaction (accessible from C, Java, Python and other languages).
* Comet, a commercial programming language and toolkit
* [[Gecode]], an open source portable toolkit written in C++ developed as a production-quality and highly efficient implementation of a complete theoretical background.
* [[Gelisp]], an open source portable wrapper of [[Gecode]] to [[Lisp (programming language)|Lisp]].<ref>Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "[http://www.jatit.org/volumes/Vol86No2/17Vol86No2.pdf GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES] {{Webarchive|url=https://web.archive.org/web/20241006110337/http://www.jatit.org/volumes/Vol86No2/17Vol86No2.pdf |date=2024-10-06 }}." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327-331.</ref> http://gelisp.sourceforge.net/
* [[IBM]] [[ILOG]] [http://www.ibm.com/analytics/cplex-cp-optimizer CP Optimizer]: C++, [https://pypi.python.org/pypi/docplex Python], Java, .NET libraries (proprietary, [https://ibm.biz/COS_Faculty free for academic use]).<ref name="CPOptimizer2018">{{cite journal|vauthors=Laborie P, Rogerie J, Shaw P, Vilim P|date=2018|title=IBM ILOG CP optimizer for scheduling|journal=Constraints|volume=23|issue=2|pages=210–250|doi=10.1007/s10601-018-9281-x|s2cid=4360357}}</ref> Successor of ILOG Solver/Scheduler, which was considered the market leader in commercial constraint programming software as of 2006<ref name="RossiBeek2006">{{cite book|first1=Francesca|last1=Rossi|author1-link=Francesca Rossi|author2=Peter Van Beek|author3=Toby Walsh|title=Handbook of constraint programming|url=https://books.google.com/books?id=Kjap9ZWcKOoC&pg=PA157|year=2006|publisher=Elsevier|isbn=978-0-444-52726-4|page=157}}</ref>
* [[JaCoP (solver)|JaCoP]], an open source Java constraint solver.
* [[Koalog]], a commercial Java-based constraint solver.
* [[logilab-constraint]], an open source constraint solver written in pure Python with constraint propagation algorithms.
* [[Minion (solver)|Minion]], an open-source constraint solver written in C++, with a small language for the purpose of specifying models/problems.
* ZDC, an open source program developed in the [[Computer-Aided Constraint Satisfaction Project]] for modelling and solving constraint satisfaction problems.

===Other constraint programming languages===

Constraint toolkits are a way for embedding constraints into an [[imperative programming language]]. However, they are only used as external libraries for encoding and solving problems. An approach in which constraints are integrated into an imperative programming language is taken in the [[Kaleidoscope programming language]].

Constraints have also been embedded into [[Functional programming|functional programming languages]].