Money Example [ISO]

The Jekejeke Prolog programming language provides the usual backtracking. The given example shows the solving of a small letter puzzle. The problem consists of finding distinct digits for the letters below so that they fit the below addition:

      S E N D
    + M O R E
    ---------
    M O N E Y

Many puzzles are formulated in a similar fashion, i.e. to find an exemplar from a collection that satisfies a certain condition. This leads to the programming pattern of generate and test. The pattern consists of defining goals G1, .., Gn that enumerate the exemplars of the collection and of defining goals T1, .., Tm that verify the condition. The problem is then solved by the following query:

    G1, .., Gn, T1, .., Tm

The interpreter will move between these goals via backtracking until a solution is found. The interpreter can also be used to return multiple solutions. Since modern Prolog systems and modern machines do more than 2 mega logical inferences per second many small problems can be solved in time. We also apply this method to our letter puzzle.

So that we don’t look too stupid we will enumerate intelligently. Simply enumerating all possible digit combinations would lead to 10^8 possibilities. What we will do, we will only enumerate permutations of the available digits which will lead to 8! possibilities. We do make use of the oneof/3 predicate which non-deterministically picks an element from a list. The generator for the permutations then reads as follows:

% assign(-List,+List)
assign([], _).
assign([X|Y], L) :- oneof(L, X, R), assign(Y, R).

The above predicate is then used to assign digits to the letters. More details about the generation phase can be found in the appendix. The test phase is now simply a code phrasing of the problem statement. We will look for a solution where M and S are non-zero. And we look for a solution where the addition holds. These conditions read as follows:

M =\= 0,
S =\= 0,
           1000*S + 100*E + 10*N + D +
           1000*M + 100*O + 10*R + E =:=
 10000*M + 1000*O + 100*N + 10*E + Y.

We can now run the Jekejeke Prolog interpreter to find the sole solution.

?- puzzle(X).
X = [9,5,6,7,1,0,8,2] ;
No

Comments