alice
constraint
tutorial.

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 = 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); end

• 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.

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 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``

Search.searchAll smm

Space.space list * =

([ ],
< 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.