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

SEND + MORE = MONEY

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

Viewpoint

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.

Script

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

• The fields of the vector letters are pairwise distinct. This is realized with the predefined propagator
  distinct : space * term vector * conlevel $\rightarrow$ 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.

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):

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

Figure 4: The search tree explored by smm