Example: Send More Money

We will now write a script for the Send More Money Puzzle.

Problem Specification

The Send More Money Problem consists in finding distinct digits for the letters D, E, M, N, O, R, S, Y such that S and M are different from zero (no leading zeros) and the equation
is satisfied. The unique solution of the problem is 9567 + 1085 = 10652.


We model the problem by having a variable for every letter, where the variable stands for the digit associated with the letter, i.e. every variable has the integer set {0, ..., 9} as domain. The constraints are obvious from the problem specification.

Branching Strategy

We branch on the variables for the letters with a first-fail strategy. The variables are ordered according to the alphabetic order of the letters. The strategy tries the least possible value of the selected variable.


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 =
    val letters as #[S,E,N,D,M,O,R,Y] = 
               fdtermVec (space, 8, [0`#9])
    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);

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 $ \rightarrow$ 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:

Posting of constraints

Posting of constraints is defined differently for basic and nonbasic constraints. Basic constraints are posted by telling them to the constraint store. Nonbasic constraints are posted by creating propagators implementing them.

Note that the modelling tools for S $ \neq$ 0 and M $ \neq$ 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$ \_SIZE$$ \_MIN$, FD.B$ \_MIN$) posts a branching that will branch on the vector letters with the first-fail strategy (specified by FD.B$ \_SIZE$$ \_MIN$ and FD.B$ \_MIN$). $\emph{FD.B\_SIZE\_MIN}$ controls which undetermined variable will be selected and FD.B$ \_MIN$ 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 smm
you obtain the list of all solutions and the result record (by depth-first search): list *
{D : term, E : term, M : term, N : term, O : term, R : term, S : term, Y : term} =
([$ \_val$],
{D = FD($ \_val$), E = FD($ \_val$), M = FD($ \_val$), N = FD($ \_val$),
O = FD($ \_val$), R = FD($ \_val$), S = FD($ \_val$), Y = FD($ \_val$)})

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 candidates a naive generate and test method would have to consider.

Figure 4: The search tree explored by smm
\includegraphics[scale=0.3, clip]{figs/fig5.eps}

Andreas Rossberg 2006-08-28