Content deleted Content added
m Fixing the ___location of periods / full stops |
m Task 70: Update syntaxhighlight tags - remove use of deprecated <source> tags |
||
Line 118:
== Example ==
The syntax for expressing constraints over finite domains depends on the host language. The following is a [[Prolog]] program that solves the classical [[alphametic]] puzzle [[Verbal arithmetic|SEND+MORE=MONEY]] in constraint logic programming:
<
% This code works in both YAP and SWI-Prolog using the environment-supplied
% CLPFD constraint solver library. It may require minor modifications to work
Line 133:
#= 10000*M + 1000*O + 100*N + 10*E + Y,
label(Digits). % Start the search
</syntaxhighlight>
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.
| |||