|
The interpreter creates a variable for each letter in the puzzle. The operator <code>ins</code> is used to specify the domains of these variables, so that they range over the set of values {0,1,2,3, ..., 9}. The constraints <code>S#\=0</code> and <code>M#\=0</code> means that these two variables cannot take the value zero. When the interpreter evaluates these constraints, it reduces the domains of these two variables by removing the value 0 from them. Then, the constraint <code>all_different(Digits)</code> is considered; it does not reduce any ___domain, so it is simply stored. The last constraint specifies that the digits assigned to the letters must be such that "SEND+MORE=MONEY" holds when each letter is replaced by its corresponding digit. From this constraint, the solver infers that M=1. All stored constraints involving variable M are awakened: in this case, [[constraint propagation]] on the <code>all_different</code> constraint removes value 1 from the ___domain of all the remaining variables. Constraint propagation may solve the problem by reducing all domains to a single value, it may prove that the problem has no solution by reducing a ___domain to the empty set, but may also terminate without proving satisfiability or unsatisfiability. The '''label''' literals are used to actually perform search for a solution.
==Constraint programming libraries for general-purpose programming languages==
Constraint programming is often realized in imperative programming via a separate library. Some popular libraries for constraint programming are:
* [http://www.artelys.com/en/optimization-tools/kalis Artelys Kalis], [[C++]], [[Java (programming language)|Java]], [[Python (programming language)|Python]] library, [http://www.fico.com/en/products/fico-xpress-optimization-suite/ FICO Xpress] module (proprietary)
* [[Cassowary (software)|Cassowary]], Smalltalk, C++, Java, Python, JavaScript, Ruby library (LGPL)
* [[CHIP (programming language)|CHIP V5]], C++ and C libraries (proprietary)
* [http://choco-solver.org/ Choco], Java library ([[BSD licenses|BSD license]])
* [[Comet (programming language)|Comet]], [[C (programming language)|C]] style language for constraint programming, constraint-based local search and mathematical programming (free binaries available for academic use)
* [http://bach.istc.kobe-u.ac.jp/cream/ Cream], Java library (LGPL)
* [http://research.microsoft.com/apps/pubs/default.aspx?id=64335 Disolver], [[C++]] library (proprietary)
* [https://ocaml.github.io/platform-dev/packages/facile/ Facile], OCaml library (CC0 1.0)
* [https://github.com/dmoverton/finite-___domain finite-___domain], Haskell library (MIT)
* [[Gecode]], C++ library, Python bindings ([[X11]]-style free software)
* [https://github.com/google/or-tools Google OR-Tools], [[C++]], [[Python (programming language)|Python]], [[Java (programming language)|Java]], [[.NET Framework|.NET]] library ([[Apache License]] 2.0)
* [[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}}</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|author1=Francesca 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]], Java library (open source)
* [http://jopt.sourceforge.net/ JOpt], Java library (free software)
* [http://jcp.org/en/jsr/detail?id=331 JSR-331], Java constraint programming API, JCP standard
* Koalog Constraint Solver, Java library (proprietary)
* [[LINDO]] (proprietary)
* [https://hackage.haskell.org/package/monadiccp MonadicCP], Haskell library (BSD-3-Clause)
* [http://numberjack.ucc.ie/ Numberjack], Python platform (LGPL)
* [[Minion (solver)|Minion]], C++ program (GPL)
* [http://labix.org/python-constraint python-constraint], Python library (GPL)
* [https://bitbucket.org/oscarlib/oscar/wiki/Home OscaR], [[Scala (programming language)|Scala]] library (LGPL)
* [https://github.com/TakehideSoh/Scarab Scarab], Scala library (BSD license)
* [https://github.com/osxhacker/smocs SMOCS], Scala [[Monad (functional programming)|Monadic]] library (BSD license)
* [https://www.optaplanner.org OptaPlanner], Java library (that also works in Kotlin, Scala, JRuby and Groovy) and toolkit (benchmarker, server and workbench) ([[Apache license]])
*[http://imae.udg.edu/recerca/lap/simply/ WSimply]
* [https://github.com/Z3Prover/z3 Z3], C++ solver with C, Java, C#, and Python bindings ([[MIT license]])
==Some languages that support constraint programming==
* [[AIMMS]], an [[algebraic modeling language]] with support for constraint programming.<ref>{{cite web |url=http://images.aimms.com/aimms/download/presentations/cp_aimms_capd_2012.pdf |title=The AIMMS Interface to Constraint Programming |last1=van Hoeve |first1=Willem-Jan |last2=Hunting |first2=Marcel |last3=Kuip |first3=Chris |date=2012 |website=[[AIMMS]]}}
</ref>
* [[Alma-0]], a small, [[Strong and weak typing|strongly]] [[Type system|typed]], constraint language with a limited number of features inspired by logic programming, supporting [[imperative (programming)|imperative]] programming.
* [[AMPL]], an [[algebraic modeling language]] with support for constraint programming.<ref>
{{cite journal
| author1 = Robert Fourer
| author2 = David M. Gay
| title = Extending an Algebraic Modeling Language to Support Constraint Programming
| journal = INFORMS Journal on Computing
| volume = 14
| issue = 4
| pages = 322–344
| year = 2002
| doi=10.1287/ijoc.14.4.322.2825| citeseerx = 10.1.1.8.9699
}}
</ref>
* [https://github.com/babelsberg Babelsberg], a family of object-constraint programming languages for Ruby, JavaScript, Squeak, and Python.<ref>
{{cite journal
| author1 = Tim Felgentreff
| author2 = Alan Borning
| author3 = Robert Hirschfeld
| title = Specifying and Solving Constraints on Object Behavior
| journal = Journal of Object Technology
| volume = 13
| issue = 4
| pages = 1–38
| year = 2014
| doi=10.5381/jot.2014.13.4.a1}}
</ref>
* [[Bertrand (programming language)|Bertrand]], a language for building constraint programming systems.
* [[Common Lisp]] via [https://web.archive.org/web/20081121170638/http://www.cl-user.net/asp/libs/screamer Screamer], a free software library which provides backtracking and CLP(R), CHiP features.
* [[Constraint Handling Rules]]
* [https://savilerow.cs.st-andrews.ac.uk Essence'], a high-level solver independent modelling language (GPL)
* [http://www.minizinc.org/ MiniZinc], a high-level constraint programming system ([[Mozilla Public License|Mozilla Public License version 2.0]] license)<ref>https://www.minizinc.org/</ref>
* [[Kaleidoscope (programming language)|Kaleidoscope]], an object-oriented imperative constraint programming language.
* [[Oz (programming language)|Oz]]
* [[Claire (programming language)|Claire]]
* [[Curry (programming language)|Curry]], [[Haskell (programming language)|Haskell]]-based language with [[Free software|free]] implementations.
* The [[SystemVerilog]] computer hardware simulation language has a built in constraint solver.
* [[Wolfram Language]]
* [http://www.xcsp.org/ XCSP3], an XML-based intermediate integrated format that can represent each instance separately while preserving its structure. ([[BSD licenses|BSD-style license]])
===Logic programming based constraint logic languages===
* [[B-Prolog]], [[Prolog]]-based (proprietary)
* [[CHIP (programming language)|CHIP V5]],<ref>[http://www.cosytec.com/production_scheduling/chip/optimization_product_chip.htm CHIP V5] ''COSYTEC''</ref> Prolog-based, also includes C++ and C libraries (proprietary)
* [[Ciao (programming language)|Ciao]], Prolog-based (GPL/LGPL)
* [[CLP(R)]], Constraint logic programming language over real constraints
* [[ECLiPSe]], Prolog-based (open source)
*[http://minikanren.org/ miniKanren]<ref>{{Cite web|url=https://mitpress.mit.edu/books/reasoned-schemer-second-edition|title=The Reasoned Schemer, Second Edition|last=Press|first=The MIT|website=The MIT Press|language=en|access-date=2019-02-19}}</ref>, Scheme-based (open source)
* [[SICStus Prolog|SICStus]], Prolog-based (proprietary)
* [[GNU Prolog]] (free software)
* [http://picat-lang.org/ Picat] (open C source)
* [[YAP (Prolog)]]
* [[SWI-Prolog]], a [[free software|free]] Prolog system containing several libraries for constraint solving
* [http://www.jekejeke.ch/ Jekejeke Logic Programming], Prolog-based (proprietary)
* [http://www.f1compiler.com/ F1 Compiler], a no-cost software (proprietary)
==See also==
| 