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.