SEND + MORE = MONEYis satisfied. The unique solution of the problem is 9567 + 1085 = 10652.
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
Note that the modelling tools for S 0
0
The line branch (space, letters,
FD.B
If you now import for example the structure
Search
from the Gecode library with:
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 108
, FD.B
import structure Search from ``x-alice:/lib/Gecode/Search``
and you type in the command:
Search.searchAll smm
you 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(
)})