# Alphametics

Alphametics are puzzles in which letters are substituted for the digits in an arithmetic calculation, and the words formed by the operands and answer produce a sensible phrase. The goal is to find the digits that can be substituted for the letters to produce a correct addition statement.

Consider the program demonstrated to the right. It decomposes each command line argument into its constituent characters, sorts the characters, goes through all permutations of all combinations of 10 digits taken 4 at a time in search of the solution, reports each solution, and the total number of permutations tested.

How does a person solve this puzzle?

How should a program go about solving this puzzle?

Is it possible and desirable to enumerate and test all combinations of the digits '0' through '9'?

Do you need to test all permutations of each combination?

Can you compute the total number of permutations and combinations that will need to be tested?   For example: is there a formula that will give you the total number of permutations of all combinations of 10 digits taken 4 at a time?

The following class is available upon request.

```int*  digits = new int[ number_of_letters ];
// Enumerate all combinations of 10 digits taken
//   "number_of_letters" at a time
Combinations combos( 10, number_of_letters );
while (combos.next( digits ))
{
...
}
```
The standard library of C++ provides the function "```bool next_permutation(array)```". It allows the user to enumerate all permutations of the supplied array.

What indirection (e.g. data structures) would offer interesting leverage?

Notice the "three three two two one" puzzle below – in addition to the normal puzzle dimension, the numbers named actually add up to "eleven" as well.

Here is a skeleton you might consider ...

```  // Find all the letters, and put them in a sorted
//   list
map<char,int>  letters;
// Create an array of digits that is the same size
//   as the array of letters
int*  digits = new int[ letters.size() ];
// Report the array of letters
// Iterate through all combinations, and all
//   permutations of each combination
Combinations combos( 10, number_of_letters );
while (combos.next( digits ))
do {
.
.
// Test each permutation & report the answer
.
.
} while (next_permutation( digits ));
```
impl

```
% alphametics i did too
d i o t
1 9 0 2

i      9
did    191
---    ---
too    200

count is 5040

% alphametics hes the best
b e h s t
1 2 4 6 8

hes     426
the     842
----    ----
best    1268

count is 30240

% alphametics no no too late
a e l n o t
0 2 1 7 4 9

no      74
no      74
too     944
----    ----
late    1092

count is 151200

% alphametics base ball games
a b e g l m s
4 7 3 1 5 9 8

base     7483
ball     7455
-----    -----
games    14938

count is 604800

% alphametics usa ussr peace
a c e p r s u
2 7 0 1 8 3 9

usa      932
ussr     9338
-----    -----
peace    10270

count is 604800

% alphametics send more money
d e m n o r s y
7 5 1 6 0 8 9 2

send     9567
more     1085
-----    -----
money    10652

count is 1814400

% alphametics three three two two one
e h l n o r t v w                 eleven
1 4 7 9 3 6 8 2 0

three     84611
three     84611
two       803
two       803
one       391
------    ------
eleven    171219

count is 3628800

% alphametics double double toil trouble
b d e i l o r t u
0 7 4 3 6 9 5 1 8

double     798064
double     798064
toil       1936
-------    -------
trouble    1598064

count is 3628800

a c d e l n o r t w
0 1 4 2 8 9 3 6 7 5

world     53684
------    ------
center    129726

count is 3628800

% alphametics this isa great time waster
a e g h i m r s t w
0 4 9 6 2 3 7 8 5 1

this      5628
isa       280
great     97405
time      5234
------    ------
waster    108547

count is 3628800

```