SEND + MORE = MONEYis satisfied. The unique solution of the problem is 9567 + 1085 = 10652.

Branching Strategy

import structure FD from "x-alice:/lib/gecode/FD" import structure Modeling from "x-alice:/lib/gecode/Modeling" import structure Explorer from "x-alice:/lib/tools/Explorer" open Modeling fun money space = let val letters as #[S,E,N,D,M,O,R,Y] = fdtermVec (space, 8, [0`#9]) in distinct (space, letters, FD.DOM); post (space, S `<> `0, FD.DOM); post (space, M `<> `0, FD.DOM); post (space, `1000`*S `+ `100`*E `+ `10`*N `+ D `+ `1000`*M `+ `100`*O `+ `10`*R `+ E `= `10000`*M `+ `1000`*O `+ `100`*N `+ `10`*E `+ Y, FD.DOM); branch (space, letters, FD.B_SIZE_MIN, FD.B_MIN); {S,E,N,D,M,O,R,Y} end

Listing 1 shows a script realizing the model and
branching strategy just discussed. In the first three lines of
the script the structures FD, Modeling and Explorer
are imported. This is important to be able to use the methods of the
respective structures. In the following scripts these imports are omitted
for the sake of readability. Be sure not to forget them when testing
the example scripts.^{}The script first declares a vector of finite domain variables,one for every letter.
This is done via
the function fdtermVec: space * int * domain
term vector
included in the structure
Modeling
from the Gecode
library. The function fdtermVec(s,i,d) creates a
new vector of finite domain variables
with lenght i
and every variable has to range over a finte
set of integers specified by
d ( so it is a basic constraint).
Then the script posts the
following constraints:

- The fields of the vector letters are pairwise
distinct. This is
realized with the predefined propagator

distinct : space * term vector * conlevel unit, also included in the Modeling library. Conlevel refers to the strength of propagation, i.e. for most propagators you can select interval propagation (FD.BND) or domain propagation (FD.DOM). This constraint is nonbasic. - The values of the variables S and M are different from zero (no leading zeros). These constraints are basic.
- The digits for the letters satisfy the equation SEND + MORE = MONEY. This constraint is nonbasic.

Note that the modelling tools for *S* 0 and *M* 0 can
immediately write their complete information into the constraint
store since the store already knows domains for S and M.

The line branch (space, letters,
*FD*.*B*, *FD*.*B*) posts
a branching that will branch on the vector letters with the
first-fail strategy (specified by
*FD*.*B* and *FD*.*B*).
controls which undetermined variable will be
selected and *FD*.*B* determines which value of that variable
will be selected.

If you now import for example the structure Search from the Gecode library with:

import structure Search from ``x-alice:/lib/Gecode/Search``and you type in the command:

Search.searchAll smmyou obtain the list of all solutions and the result record (by depth-first search):

Space.space list *{D : term, E : term, M : term, N : term, O : term, R : term, S : term, Y : term} =([],

{D=FD(),E=FD(),M=FD(),N=FD(),

O=FD(),R=FD(),S=FD(),Y=FD()})

The actual solutions could now be extracted from the result record using the functions from the FD.Reflect library structure.

To understand the search process defined by smm, we need more information than just the list of solutions found. Obviously, it would be useful to see a graphical representation of the search tree. It would also be nice if we could see for every node of the search tree what information about the solution was accumulated in the constraint store when the respective space became stable. Finally, it would be nice to see for every arc of the tree with which constraint it was branched.

Figure 4 shows the search tree explored by smm together
with the information just mentioned. This gives us a good
understanding of the search process defined by smm. Note that the
search tree is quite small compared to the 10^{8} candidates a naive
generate and test method would have to consider.

Andreas Rossberg 2006-08-28