26th. March 1987
A common item in books devoted to "brain-teasers" or "mind-benders" is the arithmetical rebus, where a simple addition is represented by sets of letters, rather than digits, and a solution is sought which gives the value of each letter. For example
F O R T Y
T E N +
T E N +
---------
S I X T Y
---------
After fretting over this for some time, we can probably deduce that the correspondence is:
2 9 7 8 6
8 5 0 +
8 5 0 +
---------
3 1 4 8 6
---------
In other words, the correspondence between the letters in the rebus and the digits in the solution are F=2, O=9, R=7, T=8, Y=6, E=5, N=0, S=3, I=1 and X=4.
How can we tell whether there are any other solutions? One painless method is to write a program which runs through all the possible letter-digit combinations, checks the given sum, and prints the solutions it finds. We can see that any such program is going to have to check a large number of possibilities; in the FORTY+TEN+TEN=SIXTY example, there are ten different letters, meaning that there are 10! (factorial 10) possibilities. The program must work through all 3,628,800 of these before we can tell whether all the solutions have been found. If, on the other hand, two different letters can be equal to the same digit, then the number of possibilities is 10&S'10., (1,000,000,000). However, allowing two different letters to equal the same digit produces rather uninteresting solutions, such as:
0 0 0 0 0
0 0 0 +
0 0 0 +
---------
0 0 0 0 0
---------
i.e. where all the letters are made equal to zero !
Thus, given that no two letters may equal the same digit, we restrict the number of possible combinations to 10!. Having assigned each letter to a digit we of course have to check the addition.
A L P H A B E T 1 7 5 3 1 9 0 8
L E T T E R S + 7 0 8 8 0 6 2 +
--------------- ---------------
S C R A B B L E 2 4 6 1 9 9 7 0
--------------- ---------------
Another constraint often applied is to disallow a leading zero in any of the numbers. In the FORTY+TEN+TEN=SIXTY example, this would tell us that neither T nor F take the value zero.
We will choose as a further example the rebus:
S E N D
M O R E +
---------
M O N E Y
---------
and we will solve it using five different programs, each written in a different programming language, and see which we prefer. The route to finding all the solutions can be expanded into repetition of these three simple steps:
We repeat the steps until all possible combinations have been tried. We will implement these steps in similar ways for each language.
Fortran is probably one of the last languages a computer scientist would choose if he were setting out to solve SEND MORE MONEY! However, it has been said that "anything can be programmed in Fortran!" and short of a few rather specialised features which are not in the language definition (such as recursion), it certainly looks that way. What is lost in readabilty of the code is certainly gained in efficiency of the machine code, as we shall see later.
Below is the Fortran program that solves the problem:
PROGRAM SOLVE
IMPLICIT INTEGER (A-Z)
DO 1 S=1,9
DO 1 E=0,9
IF(E.EQ.S) GOTO 1
DO 1 N=0,9
IF(N.EQ.E.OR.N.EQ.S) GOTO 1
DO 1 D=0,9
IF(D.EQ.N.OR.D.EQ.E.OR.D.EQ.S) GOTO 1
DO 1 M=1,9
IF(M.EQ.D.OR.M.EQ.N.OR.M.EQ.E.OR.M.EQ.S)
& GOTO 1
DO 1 O=0,9
IF(O.EQ.M.OR.O.EQ.D.OR.O.EQ.N.OR.O.EQ.E.
& OR.O.EQ.S) GOTO 1
DO 1 R=0,9
IF(R.EQ.O.OR.R.EQ.M.OR.R.EQ.D.OR.R.EQ.N.
& OR.R.EQ.E.OR.R.EQ.S) GOTO 1
DO 1 Y=0,9
IF(Y.EQ.R.OR.Y.EQ.O.OR.Y.EQ.M.OR.Y.EQ.D.
& OR.Y.EQ.N.OR.Y.EQ.E.OR.Y.EQ.S) GOTO 1
SEND = D+10*N+100*E+1000*S
MORE = E+10*R+100*O+1000*M
MONEY = Y+10*E+100*N+1000*O+10000*M
IF(SEND+MORE.NE.MONEY) GOTO 1
WRITE(6,100) S,E,N,D,M,O,R,E,M,O,N,E,Y
100 FORMAT(1X,' SEND ',4I1,/,1X,'+MORE ',4I1,
& /,1X,'----- ',/,1X,'MONEY ',5I1,/)
1 CONTINUE
END
Rexx is an interpreted language that runs under the VM operating system of IBM. It is thus going to be rather slower in finding all the solutions to the rebus than a compiled language such as Fortran. Where it does gain is in the clarity of the code; it is very plain to see exactly what is being done. A pleasing feature of the Rexx code is the formation of the numbers SEND, MORE and MONEY from their constituent digits, as there is no need to multiply by powers of 10 and add; the number is just interpreted as the concatenated string of all the letters.
/* REXX Exec to solve SEND+MORE=MONEY */ do s = 1 to 9 do e = 0 to 9 ; if e=s then iterate e do n = 0 to 9 ; if n=e|n=s then iterate n do d = 0 to 9 ; if d=n|d=e|d=s then iterate d do m = 1 to 9 ; if m=d|m=n|m=e|m=s then iterate m do o = 0 to 9 ; if o=m|o=d|o=n|o=e|o=s then iterate o do r = 0 to 9 ; if r=o|r=m|r=d|r=n|r=e|r=s then iterate r do y = 0 to 9 ; if y=r|y=o|y=m|y=d|y=n|y=e|y=s then iterate y more = m||o||r||e ; send = s||e||n||d sendmore = send + more if sendmore^=m||o||n||e||y then iterate y say "send + more = money" say send "+" more "=" sendmore end; end; end; end; end; end; end; end; exit
The Prolog version of the program is written in PDPROLOG, which is available free of charge on the Public Domain. The "facts" that digits are numbers 0 to 9 are first given. Then the "rule" that a valid combination of digits arises when all letters take a different digit, and the sum is correct is given. The sum "rule" takes a true value when SEND plus MORE is equal to money. When a combination satisfying the good predicate is found, Prolog shows the values of each letter, and asks whether the user wants to find more solutions. So we have to answer "yes" until Prolog finally decides there are no more.
As with Rexx, PDPROLOG is an interpreted language, so the execution speed is rather slow. You can download a copy of PDPROLOG by Robert Morein here: pdprolog.exe.
digit(1).
digit(2).
digit(3).
digit(4).
digit(5).
digit(6).
digit(7).
digit(8).
digit(9).
digit(0).
good(S,E,N,D,M,O,R,Y) :- digit(S),S\=0,
digit(E),E\=S,
digit(N),N\=E,N\=S,
digit(D),D\=N,D\=E,D\=S,
digit(M),M\=D,M\=N,M\=E,M\=S,M\=0,
digit(O),O\=M,O\=D,O\=N,O\=E,O\=S,
digit(R),R\=O,R\=M,R\=D,R\=N,R\=E,R\=S,
digit(Y),Y\=R,Y\=O,Y\=M,Y\=D,Y\=N,Y\=E,Y\=S,
sum(S,E,N,D,M,O,R,Y).
sum(S,E,N,D,M,O,R,Y) :- N1 is 1000*S+100*E+10*N+D,
N2 is 1000*M+100*O+10*R+E,
N3 is 10000*M+1000*O+100*N+10*E+Y,
N3 is N1+N2.
?????????????????????????????????????????????????