Download An Introductory Course on Constraint Logic Programming

1.7. AN EXAMPLE: SEND + MORE = MONEY
9
Constraint Programming Language
Programming
Language
Constraint
Solver
Figure 1.2: Language with extended semantics
they already provide logical variables and implicit search) are the ones more amenable to this
approach: their mathematical foundation and independence from the machine oer leeway to
for adapting their semantics self-congruently.
Regardless of the approach taken towards the construction of a constraint language, there
are some essential services that such a language must provide:
A solver, which solves equations or communicates their non-solvability (the way this is
done depends on the actual interface with the host language).
Means to express constraints, formulas, etc. from the language.
An interface to the solver, which allows constraints to be passed to it, and, upon successful constraint solving, asking for the values assigned to the constraint variables.
1.7 An Example: SEND + MORE = MONEY
the variables S E N D M O R Y
represent digits between 0 and 9, and the task is nding values for then such that the following
arithmetic operation is correct:
SEND + MORE = MONEY is a classical \crypto-arithmetic" puzzle:
+
M
S
M
O
E
O
N
N
R
E
D
E
Y
Moreover, all variables must take unique values, and all the numbers must be well-formed
(which implies that M > 0 and S > 0. Conventional programming needs to express an
explicit search in general (though in this particular case nested loops can be used). Logic
languages, such as Prolog, will use directly a built-in search: the programming is easy, but it
might not be highly ecient (of course, rened programs can achieve good performance, but
advanced skills and an eort in time is needed to write them).
This is, in fact, a typical problem for nite domains: all variables take values from a nite
set of numbers, the constraints to satisfy can be easily expressed, and there is some amount
of search to perform. Finite domain variables always have as values a set of integers, taken