Share this: Google+

## CryptArithmetic Problem: SEND + MORE = MONEY

The following puzzle is probably the most well-known CryptArithmetic Problem:

How to solve the above challenge?

We put the letter as equality constraints

Expression1 = 1000*S + 100*E + 10*N + D

Expression2 = 1000*M + 100*O + 10*R + E

Expression3 = 10000*M + 1000*O + 100*N + 10*E + Y

If (Expression3 ==Expression1 + Expression2) then

Report the value of {S, E, N, D, M, O, R, Y}

The simplest (not the fastest) way is to do permutation of digit 0 to 9 and then compute the above expression. Matlab code below gives all the possible solutions.

**
function report=SENDMOREMONEY
**

digit=0:9;

P=perms(digit);

k=0;

for i=1:size(P,1)

v=P(i,:);

% evaluate expression

exp1=v(1)*1000+v(2)*100+v(3)*10+v(4); % SEND

exp2=v(5)*1000+v(6)*100+v(7)*10+v(2); % MORE

exp3=v(5)*10000+v(6)*1000+v(3)*100+v(2)*10+v(8); % MONEY

if exp1+exp2==exp3,

k=k+1;

report(k,:)=v(1:8); % = [s, e, n, d, m, o, r, y]

end

end

report=unique(report,'rows');

## Solutions:

If M is allowed to be zero, the solutions are not unique. Below are all the 25 possible solutions.

{S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2}

{S=8, E=5, N=4, D=2, M=0, O=9, R=1, Y=7}

{S=8, E=4, N=3, D=2, M=0, O=9, R=1, Y=6}

{S=8, E=3, N=2, D=4, M=0, O=9, R=1, Y=7}

{S=7, E=6, N=4, D=9, M=0, O=8, R=1, Y=5}

{S=7, E=6, N=4, D=3, M=0, O=8, R=2, Y=9}

{S=7, E=5, N=3, D=4, M=0, O=8, R=2, Y=9}

{S=7, E=5, N=3, D=9, M=0, O=8, R=1, Y=4}

{S=7, E=5, N=3, D=1, M=0, O=8, R=2, Y=6}

{S=7, E=4, N=2, D=9, M=0, O=8, R=1, Y=3}

{S=7, E=3, N=1, D=6, M=0, O=8, R=2, Y=9}

{S=6, E=8, N=5, D=3, M=0, O=7, R=2, Y=1}

{S=6, E=8, N=5, D=1, M=0, O=7, R=3, Y=9}

{S=6, E=5, N=2, D=4, M=0, O=7, R=3, Y=9}

{S=6, E=4, N=1, D=9, M=0, O=7, R=2, Y=3}

{S=6, E=4, N=1, D=5, M=0, O=7, R=3, Y=9}

{S=5, E=8, N=4, D=9, M=0, O=6, R=3, Y=7}

{S=5, E=7, N=3, D=2, M=0, O=6, R=4, Y=9}

{S=5, E=7, N=3, D=1, M=0, O=6, R=4, Y=8}

{S=3, E=8, N=2, D=9, M=0, O=4, R=5, Y=7}

{S=3, E=8, N=2, D=1, M=0, O=4, R=6, Y=9}

{S=3, E=7, N=1, D=9, M=0, O=4, R=5, Y=6}

{S=3, E=7, N=1, D=2, M=0, O=4, R=6, Y=9}

{S=2, E=8, N=1, D=9, M=0, O=3, R=6, Y=7}

{S=2, E=8, N=1, D=7, M=0, O=3, R=6, Y=5}

If M has to be non-zero digit, the solution is unique. The reason is because S and M are the leading digit, they cannot become 0. Their domain is 1 to 9. All other letters {E, O, N, R, D, Y} has domain of 0 to 9. In this case the solution is unique, that is {S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2}.

9567 SEND

1085 MORE

--------- + ----------- +

10652 MONEY

We can see this problem from another perspective of linear equations and linear algebra.

We can derive equations:

D + E = Y + 10C1

N + R + C1 = E + 10C2

E + O + C2 = N + 10C3

S + M + C3 = O + 10C4

C4 = M

Where Ci is the carry for the summation. There are 5 equations with 12 unknowns. The solution is not unique. We can put into matrix equation

Inputting one of the solution is {S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2} in which the carries are {C1=1, C2=1, C3=0, C4=1} evaluates the same expressions above. This may be useful to evaluate the expressions to all the possible solutions at once.