## SEND+MORE=MONEY

Let’s consider a rather simple puzzle:

```   SEND
+  MORE
= MONEY
```

where each letter is assigned a value from 0 to 9. How would you solve
it?

Well, it depends on the specific interpretation you’ll be making of the puzzle. If you’re willing to have any value assigned to any of the letters, that’s one interpretation, if you’re willing to have any value assigned to any of the letters except S and M that should not be zero, or if you’re willing to assign only the values 0 to 9 (8 of 10) exactly once, you’ve got three different interpretations.

The two first interpretations (any value, any value except S and M that should not be zero) will pretty much ask to explore $10^8=100000000$ (or $9^210^6=81000000$) combinations, which may take a while. The second interpretation will ask for much less, exactly $1814400$ (we’ll explain the weird-looking number later on). Let’s see what the first two interpretations look like in code.

Clearly, we need some kind of counter that explores all combinations from 00000000 to 99999999 and checks which ones correspond to a solution. The solution can be checked with something like:

```bool acceptable(int s, int e, int n, int d, int m, int o, int r, int y)
{
return (m>0)
&& (s>0)
&& (         ((s*1000)+(e*100)+(n*10)+d)
+ ((m*1000)+(o*100)+(r*10)+e)
== ((m*10000)+(o*1000)+(n*100)+(e*10)+y));
}
```

which can be optimized to use only small multipliers (which proves moderately faster):

```bool acceptable(int s, int e, int n, int d, int m, int o, int r, int y)
{
return (m>0)
&& (s>0)
&& (      (((s*10+e)*10+n)*10+d)
+ (((m*10+o)*10+r)*10+e)
== ((((m*10+o)*10+n)*10+e)*10+y));
}
```

The counter is most easily done:

```  for (int i=0;i<100000000;i++)
{
int digits[8];
for (int t=i,j=0;j<8;j++,t/=10)
digits[j]=t % 10;
...
```

Then we check if it’s a solution. The complete program looks like:

```#include <iostream>

////////////////////////////////////////
bool acceptable(int s, int e, int n, int d, int m, int o, int r, int y)
{
return (m>0)
&& (s>0)
&& (      (((s*10+e)*10+n)*10+d)
+ (((m*10+o)*10+r)*10+e)
== ((((m*10+o)*10+n)*10+e)*10+y));
}

////////////////////////////////////////
int main()
{
for (int i=0;i<100000000;i++)
{
int digits[8];
for (int t=i,j=0;j<8;j++,t/=10)
digits[j]=t % 10;

if (acceptable(digits[0], // s
digits[1], // e
digits[2], // n
digits[3], // d
digits[4], // m
digits[5], // o
digits[6], // r
digits[7])) // y
std::cout
<< " s=" << digits[0]
<< " e=" << digits[1]
<< " n=" << digits[2]
<< " d=" << digits[3]
<< " m=" << digits[4]
<< " o=" << digits[5]
<< " r=" << digits[6]
<< " y=" << digits[7]
<< " " << ((digits[0]*1000)+(digits[1]*100)+(digits[2]*10)+digits[3])
<< "+" << ((digits[4]*1000)+(digits[5]*100)+(digits[6]*10)+digits[1])
<< "=" << ((digits[4]*10000)+(digits[5]*1000)+(digits[2]*100)+(digits[1]*10)+digits[7])
<< std::endl;
}

return 0;
}
```

The program quickly outputs:

``` s=9 e=0 n=0 d=0 m=1 o=0 r=0 y=0 9000+1000=10000
s=9 e=8 n=9 d=2 m=1 o=0 r=8 y=0 9892+1088=10980
s=9 e=7 n=8 d=3 m=1 o=0 r=8 y=0 9783+1087=10870
s=9 e=6 n=7 d=4 m=1 o=0 r=8 y=0 9674+1086=10760
s=9 e=5 n=6 d=5 m=1 o=0 r=8 y=0 9565+1085=10650
s=9 e=4 n=5 d=6 m=1 o=0 r=8 y=0 9456+1084=10540
s=9 e=3 n=4 d=7 m=1 o=0 r=8 y=0 9347+1083=10430
s=9 e=2 n=3 d=8 m=1 o=0 r=8 y=0 9238+1082=10320
s=9 e=1 n=2 d=9 m=1 o=0 r=8 y=0 9129+1081=10210
s=9 e=9 n=0 d=1 m=1 o=1 r=8 y=0 9901+1189=11090
s=9 e=0 n=1 d=0 m=1 o=0 r=9 y=0 9010+1090=10100
s=9 e=1 n=1 d=0 m=1 o=0 r=0 y=1 9110+1001=10111
s=9 e=0 n=0 d=1 m=1 o=0 r=0 y=1 9001+1000=10001
s=9 e=8 n=9 d=3 m=1 o=0 r=8 y=1 9893+1088=10981
s=9 e=7 n=8 d=4 m=1 o=0 r=8 y=1 9784+1087=10871
s=9 e=6 n=7 d=5 m=1 o=0 r=8 y=1 9675+1086=10761
s=9 e=5 n=6 d=6 m=1 o=0 r=8 y=1 9566+1085=10651
s=9 e=4 n=5 d=7 m=1 o=0 r=8 y=1 9457+1084=10541
s=9 e=3 n=4 d=8 m=1 o=0 r=8 y=1 9348+1083=10431
s=9 e=2 n=3 d=9 m=1 o=0 r=8 y=1 9239+1082=10321
s=9 e=9 n=0 d=2 m=1 o=1 r=8 y=1 9902+1189=11091
s=9 e=1 n=2 d=0 m=1 o=0 r=9 y=1 9120+1091=10211
s=9 e=0 n=1 d=1 m=1 o=0 r=9 y=1 9011+1090=10101
s=9 e=2 n=2 d=0 m=1 o=0 r=0 y=2 9220+1002=10222
s=9 e=1 n=1 d=1 m=1 o=0 r=0 y=2 9111+1001=10112
s=9 e=0 n=0 d=2 m=1 o=0 r=0 y=2 9002+1000=10002
s=9 e=8 n=9 d=4 m=1 o=0 r=8 y=2 9894+1088=10982
s=9 e=7 n=8 d=5 m=1 o=0 r=8 y=2 9785+1087=10872
s=9 e=6 n=7 d=6 m=1 o=0 r=8 y=2 9676+1086=10762
s=9 e=5 n=6 d=7 m=1 o=0 r=8 y=2 9567+1085=10652
s=9 e=4 n=5 d=8 m=1 o=0 r=8 y=2 9458+1084=10542
s=9 e=3 n=4 d=9 m=1 o=0 r=8 y=2 9349+1083=10432
s=9 e=9 n=0 d=3 m=1 o=1 r=8 y=2 9903+1189=11092
s=9 e=2 n=3 d=0 m=1 o=0 r=9 y=2 9230+1092=10322
s=9 e=1 n=2 d=1 m=1 o=0 r=9 y=2 9121+1091=10212
s=9 e=0 n=1 d=2 m=1 o=0 r=9 y=2 9012+1090=10102
s=9 e=3 n=3 d=0 m=1 o=0 r=0 y=3 9330+1003=10333
s=9 e=2 n=2 d=1 m=1 o=0 r=0 y=3 9221+1002=10223
s=9 e=1 n=1 d=2 m=1 o=0 r=0 y=3 9112+1001=10113
s=9 e=0 n=0 d=3 m=1 o=0 r=0 y=3 9003+1000=10003
s=9 e=8 n=9 d=5 m=1 o=0 r=8 y=3 9895+1088=10983
s=9 e=7 n=8 d=6 m=1 o=0 r=8 y=3 9786+1087=10873
s=9 e=6 n=7 d=7 m=1 o=0 r=8 y=3 9677+1086=10763
s=9 e=5 n=6 d=8 m=1 o=0 r=8 y=3 9568+1085=10653
s=9 e=4 n=5 d=9 m=1 o=0 r=8 y=3 9459+1084=10543
s=9 e=9 n=0 d=4 m=1 o=1 r=8 y=3 9904+1189=11093
s=9 e=3 n=4 d=0 m=1 o=0 r=9 y=3 9340+1093=10433
s=9 e=2 n=3 d=1 m=1 o=0 r=9 y=3 9231+1092=10323
s=9 e=1 n=2 d=2 m=1 o=0 r=9 y=3 9122+1091=10213
s=9 e=0 n=1 d=3 m=1 o=0 r=9 y=3 9013+1090=10103
s=9 e=4 n=4 d=0 m=1 o=0 r=0 y=4 9440+1004=10444
s=9 e=3 n=3 d=1 m=1 o=0 r=0 y=4 9331+1003=10334
s=9 e=2 n=2 d=2 m=1 o=0 r=0 y=4 9222+1002=10224
s=9 e=1 n=1 d=3 m=1 o=0 r=0 y=4 9113+1001=10114
s=9 e=0 n=0 d=4 m=1 o=0 r=0 y=4 9004+1000=10004
s=9 e=8 n=9 d=6 m=1 o=0 r=8 y=4 9896+1088=10984
s=9 e=7 n=8 d=7 m=1 o=0 r=8 y=4 9787+1087=10874
s=9 e=6 n=7 d=8 m=1 o=0 r=8 y=4 9678+1086=10764
s=9 e=5 n=6 d=9 m=1 o=0 r=8 y=4 9569+1085=10654
s=9 e=9 n=0 d=5 m=1 o=1 r=8 y=4 9905+1189=11094
s=9 e=4 n=5 d=0 m=1 o=0 r=9 y=4 9450+1094=10544
s=9 e=3 n=4 d=1 m=1 o=0 r=9 y=4 9341+1093=10434
s=9 e=2 n=3 d=2 m=1 o=0 r=9 y=4 9232+1092=10324
s=9 e=1 n=2 d=3 m=1 o=0 r=9 y=4 9123+1091=10214
s=9 e=0 n=1 d=4 m=1 o=0 r=9 y=4 9014+1090=10104
s=9 e=5 n=5 d=0 m=1 o=0 r=0 y=5 9550+1005=10555
s=9 e=4 n=4 d=1 m=1 o=0 r=0 y=5 9441+1004=10445
s=9 e=3 n=3 d=2 m=1 o=0 r=0 y=5 9332+1003=10335
s=9 e=2 n=2 d=3 m=1 o=0 r=0 y=5 9223+1002=10225
s=9 e=1 n=1 d=4 m=1 o=0 r=0 y=5 9114+1001=10115
s=9 e=0 n=0 d=5 m=1 o=0 r=0 y=5 9005+1000=10005
s=9 e=8 n=9 d=7 m=1 o=0 r=8 y=5 9897+1088=10985
s=9 e=7 n=8 d=8 m=1 o=0 r=8 y=5 9788+1087=10875
s=9 e=6 n=7 d=9 m=1 o=0 r=8 y=5 9679+1086=10765
s=9 e=9 n=0 d=6 m=1 o=1 r=8 y=5 9906+1189=11095
s=9 e=5 n=6 d=0 m=1 o=0 r=9 y=5 9560+1095=10655
s=9 e=4 n=5 d=1 m=1 o=0 r=9 y=5 9451+1094=10545
s=9 e=3 n=4 d=2 m=1 o=0 r=9 y=5 9342+1093=10435
s=9 e=2 n=3 d=3 m=1 o=0 r=9 y=5 9233+1092=10325
s=9 e=1 n=2 d=4 m=1 o=0 r=9 y=5 9124+1091=10215
s=9 e=0 n=1 d=5 m=1 o=0 r=9 y=5 9015+1090=10105
s=9 e=6 n=6 d=0 m=1 o=0 r=0 y=6 9660+1006=10666
s=9 e=5 n=5 d=1 m=1 o=0 r=0 y=6 9551+1005=10556
s=9 e=4 n=4 d=2 m=1 o=0 r=0 y=6 9442+1004=10446
s=9 e=3 n=3 d=3 m=1 o=0 r=0 y=6 9333+1003=10336
s=9 e=2 n=2 d=4 m=1 o=0 r=0 y=6 9224+1002=10226
s=9 e=1 n=1 d=5 m=1 o=0 r=0 y=6 9115+1001=10116
s=9 e=0 n=0 d=6 m=1 o=0 r=0 y=6 9006+1000=10006
s=9 e=8 n=9 d=8 m=1 o=0 r=8 y=6 9898+1088=10986
s=9 e=7 n=8 d=9 m=1 o=0 r=8 y=6 9789+1087=10876
s=9 e=9 n=0 d=7 m=1 o=1 r=8 y=6 9907+1189=11096
s=9 e=6 n=7 d=0 m=1 o=0 r=9 y=6 9670+1096=10766
s=9 e=5 n=6 d=1 m=1 o=0 r=9 y=6 9561+1095=10656
s=9 e=4 n=5 d=2 m=1 o=0 r=9 y=6 9452+1094=10546
s=9 e=3 n=4 d=3 m=1 o=0 r=9 y=6 9343+1093=10436
s=9 e=2 n=3 d=4 m=1 o=0 r=9 y=6 9234+1092=10326
s=9 e=1 n=2 d=5 m=1 o=0 r=9 y=6 9125+1091=10216
s=9 e=0 n=1 d=6 m=1 o=0 r=9 y=6 9016+1090=10106
s=9 e=7 n=7 d=0 m=1 o=0 r=0 y=7 9770+1007=10777
s=9 e=6 n=6 d=1 m=1 o=0 r=0 y=7 9661+1006=10667
s=9 e=5 n=5 d=2 m=1 o=0 r=0 y=7 9552+1005=10557
s=9 e=4 n=4 d=3 m=1 o=0 r=0 y=7 9443+1004=10447
s=9 e=3 n=3 d=4 m=1 o=0 r=0 y=7 9334+1003=10337
s=9 e=2 n=2 d=5 m=1 o=0 r=0 y=7 9225+1002=10227
s=9 e=1 n=1 d=6 m=1 o=0 r=0 y=7 9116+1001=10117
s=9 e=0 n=0 d=7 m=1 o=0 r=0 y=7 9007+1000=10007
s=9 e=8 n=9 d=9 m=1 o=0 r=8 y=7 9899+1088=10987
s=9 e=9 n=0 d=8 m=1 o=1 r=8 y=7 9908+1189=11097
s=9 e=7 n=8 d=0 m=1 o=0 r=9 y=7 9780+1097=10877
s=9 e=6 n=7 d=1 m=1 o=0 r=9 y=7 9671+1096=10767
s=9 e=5 n=6 d=2 m=1 o=0 r=9 y=7 9562+1095=10657
s=9 e=4 n=5 d=3 m=1 o=0 r=9 y=7 9453+1094=10547
s=9 e=3 n=4 d=4 m=1 o=0 r=9 y=7 9344+1093=10437
s=9 e=2 n=3 d=5 m=1 o=0 r=9 y=7 9235+1092=10327
s=9 e=1 n=2 d=6 m=1 o=0 r=9 y=7 9126+1091=10217
s=9 e=0 n=1 d=7 m=1 o=0 r=9 y=7 9017+1090=10107
s=9 e=8 n=8 d=0 m=1 o=0 r=0 y=8 9880+1008=10888
s=9 e=7 n=7 d=1 m=1 o=0 r=0 y=8 9771+1007=10778
s=9 e=6 n=6 d=2 m=1 o=0 r=0 y=8 9662+1006=10668
s=9 e=5 n=5 d=3 m=1 o=0 r=0 y=8 9553+1005=10558
s=9 e=4 n=4 d=4 m=1 o=0 r=0 y=8 9444+1004=10448
s=9 e=3 n=3 d=5 m=1 o=0 r=0 y=8 9335+1003=10338
s=9 e=2 n=2 d=6 m=1 o=0 r=0 y=8 9226+1002=10228
s=9 e=1 n=1 d=7 m=1 o=0 r=0 y=8 9117+1001=10118
s=9 e=0 n=0 d=8 m=1 o=0 r=0 y=8 9008+1000=10008
s=9 e=9 n=0 d=9 m=1 o=1 r=8 y=8 9909+1189=11098
s=9 e=8 n=9 d=0 m=1 o=0 r=9 y=8 9890+1098=10988
s=9 e=7 n=8 d=1 m=1 o=0 r=9 y=8 9781+1097=10878
s=9 e=6 n=7 d=2 m=1 o=0 r=9 y=8 9672+1096=10768
s=9 e=5 n=6 d=3 m=1 o=0 r=9 y=8 9563+1095=10658
s=9 e=4 n=5 d=4 m=1 o=0 r=9 y=8 9454+1094=10548
s=9 e=3 n=4 d=5 m=1 o=0 r=9 y=8 9345+1093=10438
s=9 e=2 n=3 d=6 m=1 o=0 r=9 y=8 9236+1092=10328
s=9 e=1 n=2 d=7 m=1 o=0 r=9 y=8 9127+1091=10218
s=9 e=0 n=1 d=8 m=1 o=0 r=9 y=8 9018+1090=10108
s=9 e=9 n=9 d=0 m=1 o=0 r=0 y=9 9990+1009=10999
s=9 e=8 n=8 d=1 m=1 o=0 r=0 y=9 9881+1008=10889
s=9 e=7 n=7 d=2 m=1 o=0 r=0 y=9 9772+1007=10779
s=9 e=6 n=6 d=3 m=1 o=0 r=0 y=9 9663+1006=10669
s=9 e=5 n=5 d=4 m=1 o=0 r=0 y=9 9554+1005=10559
s=9 e=4 n=4 d=5 m=1 o=0 r=0 y=9 9445+1004=10449
s=9 e=3 n=3 d=6 m=1 o=0 r=0 y=9 9336+1003=10339
s=9 e=2 n=2 d=7 m=1 o=0 r=0 y=9 9227+1002=10229
s=9 e=1 n=1 d=8 m=1 o=0 r=0 y=9 9118+1001=10119
s=9 e=0 n=0 d=9 m=1 o=0 r=0 y=9 9009+1000=10009
s=9 e=8 n=9 d=1 m=1 o=0 r=9 y=9 9891+1098=10989
s=9 e=7 n=8 d=2 m=1 o=0 r=9 y=9 9782+1097=10879
s=9 e=6 n=7 d=3 m=1 o=0 r=9 y=9 9673+1096=10769
s=9 e=5 n=6 d=4 m=1 o=0 r=9 y=9 9564+1095=10659
s=9 e=4 n=5 d=5 m=1 o=0 r=9 y=9 9455+1094=10549
s=9 e=3 n=4 d=6 m=1 o=0 r=9 y=9 9346+1093=10439
s=9 e=2 n=3 d=7 m=1 o=0 r=9 y=9 9237+1092=10329
s=9 e=1 n=2 d=8 m=1 o=0 r=9 y=9 9128+1091=10219
s=9 e=0 n=1 d=9 m=1 o=0 r=9 y=9 9019+1090=10109
s=9 e=9 n=0 d=0 m=1 o=1 r=9 y=9 9900+1199=11099
```

The program examined $10^8$ in about 1.4s on an i5-3470 CPU @ 3.20GHz. That’s kind long for this simple-looking problem, but it produced all possible solutions.

*
* *

For the last interpretation, that the numbers 0 to 9 are used exactly once, we have to enumerate all the way of choosing 8 out of 10 items, and that’s $\binom{10}{8}=45$ different ways. For each of these, we will have to check all $8!=40320$ permutations, for a total of $45*8!=1814400$ (whence the weird number). But how do we generate all permutations? We’re not specially interested in generating the permutations in lexicographical order, just generating
all of them. However, the shuttle algorithm is simple and generates the
permutations in lexicographical order:

```////////////////////////////////////////
//
// ref: Rosen, 2nd ed, p. 284
// (slightly modified to accommodate
// repeated symbols)
//
void next(int a[],int n)
{
int j=n-2;
// > if all distinct,
// >= if some same
while (j && a[j]>=a[j+1]) j--;

int k=n-1;
while (k && a[j]>=a[k]) k--;

std::swap(a[j],a[k]);

int r=n-1;
int s=j+1;
while (r>s)
{
std::swap(a[r],a[s]);
r--;
s++;
}
}
```

(I modified the algorithm to deal with repeated symbols, so what we can use it on the string 0011111111 to generate all 45 10-choose-8 combinations.) Once we have the 0-1 combinations, we can use it as a

```int digits[8];
for (int b=0,d=0;b<10;b++)
if (bits[b])
digits[d++]=b;
```

So now we generate the 45 (distinct) permutations of 0011111111 and the 8! combinations of 10-choose-8 digits, and find the unique solution (essentially instantaneously):

s=9 e=5 n=6 d=7 m=1 o=0 r=8 y=2, or 9567+1085=10652

The complete code (click to expand):

```#include <iostream>
#include <vector>

////////////////////////////////////////
bool acceptable(int s, int e, int n, int d, int m, int o, int r, int y)
{
return (m>0)
&& (s>0)
&& (           (((s*10+e)*10+n)*10+d)
+ (((m*10+o)*10+r)*10+e)
== ((((m*10+o)*10+n)*10+e)*10+y));
}

////////////////////////////////////////
//
// ref: Rosen, 2nd ed, p. 284
// (slightly modified to accommodate
// repeated symbols)
//
void next(int a[],int n)
{
int j=n-2;
// > if all distinct,
// >= if some same
while (j && a[j]>=a[j+1]) j--;

int k=n-1;
while (k && a[j]>=a[k]) k--;

std::swap(a[j],a[k]);

int r=n-1;
int s=j+1;
while (r>s)
{
std::swap(a[r],a[s]);
r--;
s++;
}
}

////////////////////////////////////////
int main()
{
int bits[10]={0,0,1,1,1,1,1,1,1,1};
for (int i=0;i<45;i++)
{
// for(int b=0;b<10;b++)
//  std::cout << bits[b];
// std::cout << std::endl;

int digits[8];
for (int b=0,d=0;b<10;b++)
if (bits[b])
digits[d++]=b;

// 8!=40320
for (int p=0;p<40320;p++)
{
if (acceptable(digits[0], // s
digits[1], // e
digits[2], // n
digits[3], // d
digits[4], // m
digits[5], // o
digits[6], // r
digits[7])) // y
std::cout
<< " s=" << digits[0]
<< " e=" << digits[1]
<< " n=" << digits[2]
<< " d=" << digits[3]
<< " m=" << digits[4]
<< " o=" << digits[5]
<< " r=" << digits[6]
<< " y=" << digits[7]
<< " " << ((digits[0]*1000)+(digits[1]*100)+(digits[2]*10)+digits[3])
<< "+" << ((digits[4]*1000)+(digits[5]*100)+(digits[6]*10)+digits[1])
<< "=" << ((digits[4]*10000)+(digits[5]*1000)+(digits[2]*100)+(digits[1]*10)+digits[7])
<< std::endl;

next(digits,8);
}

next(bits,10);
}

return 0;
}
```

*
* *

That’s quite a bit of code to some something as simple as this. Maybe we can use a different language? Prolog maybe? Since it has this built-in capability for backtracking. Here’s a version I lifted (sources included) from the ‘net:

smm :-
X = [S,E,N,D,M,O,R,Y],
Digits = [0,1,2,3,4,5,6,7,8,9],
assign_digits(X, Digits),
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,
write(X), !.

select(X, [X|R], R).
select(X, [Y|Xs], [Y|Ys]):- select(X, Xs, Ys).

assign_digits([], _List).
assign_digits([D|Ds], List):-
select(D, List, NewList),
assign_digits(Ds, NewList).

### One Response to SEND+MORE=MONEY

1. […] and yield the next one in lexicographical order. We’ve already met this algorithm in a previous entry. We start with the initial permutation 0,0,0,0,1,1,1,1,1,1. The next will be 0,0,0,1,0,1,1,1,1,1. […]