Constraint programming: Difference between revisions

Revision as of 18:14, 22 April 2021

Revision as of 19:25, 6 May 2021

Line 136:

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.

==Solvers==

{| class="wikitable"

|-

!Name

!License

!Brief info

|-

| [https://choco-solver.org/ Choco]||[https://spdx.org/licenses/BSD-4-Clause.html BSD 4-Clause]||Java library for constraint programming

|-

| [https://github.com/chuffed/chuffed Chuffed]||[https://github.com/chuffed/chuffed/blob/master/LICENSE MIT]||Lazy clause generation solver

|-

| [https://developers.google.com/optimization/cp/cp_solver CP-SAT]||[https://github.com/google/or-tools/blob/stable/LICENSE-2.0.txt Apache]||Google's open source solver for constraint programming

|-

| [https://www.gecode.org/ Gecode]||[https://www.gecode.org/license.html MIT]||C++ toolkit for developing constraint-based systems and applications

|-

| [https://www.ibm.com/analytics/cplex-cp-optimizer ILOG CP Optimizer]||Commercial||IBM's solver for scheduling and combinatorial optimization

|-

| [[JaCoP (solver)|JaCoP]]||[https://osolpro.atlassian.net/wiki/spaces/JACOP/pages/24248325/JaCoP+Licence dual-license]||Constraint solver written in Java and focused on ease of use

|-

| [http://picat-lang.org/ Picat]||[http://mozilla.org/MPL/2.0/ MPL 2.0]||Logic-based multi-paradigm programming language aimed for general-purpose applications

|}

==See also==