# Extra material: Cryptarithms puzzle#

The July 1924 issue of the famous British magazine *The Strand* included a word puzzle by Henry E. Dudeney in his regular contribution âPerplexitiesâ. The puzzle is to assign a unique digit to each letter appearing in the equation

```
S E N D
+ M O R E
= M O N E Y
```

such that the arithmetic equation is satisfied, and the leading digit for M is non-zero. There are many more examples of these puzzles, but this is perhaps the most well-known.

```
# install dependencies and select solver
%pip install -q amplpy
SOLVER = "cbc"
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["cbc"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
```

## Modeling and Solution#

There are several possible approaches to modeling this puzzle in AMPL.

One approach would be to using a matrix of binary variables \(x_{a,d}\) indexed by letter \(a\) and digit \(d\) such that \(x_{a,d} = 1\) designates the corresponding assignment. The problem constraints can then be implemented by summing the binary variables along the two axes. The arithmetic constraint becomes a more challenging.

Another approach is to use integer variables indexed by letters, then setup an linear expression to represent the puzzle. If we use the notation \(n_a\) to represent the digit assigned to letter \(a\), the algebraic constraint becomes

The requirement that no two letters be assigned the same digit can be represented as a disjunction. Letting \(n_a\) and \(n_b\) denote the integers assigned to letters \(a\) and \(b\), the disjunction becomes

```
%%writefile cryptarithms.mod
set LETTERS;
set PAIRS within {LETTERS, LETTERS};
var n{LETTERS} integer >= 0, <= 9;
s.t. message:
1000*n['S'] + 100*n['E'] + 10*n['N'] + n['D']
+ 1000*n['M'] + 100*n['O'] + 10*n['R'] + n['E']
== 10000*n['M'] + 1000*n['O'] + 100*n['N'] + 10*n['E'] + n['Y'];
# leading digit must be non-zero
s.t. leading_digit_nonzero: n['M'] >= 1;
# assign a different number to each letter
s.t. unique_assignment{(a, b) in PAIRS}:
(n[a] >= n[b] + 1
or
n[b] >= n[a] + 1)
and not
(n[a] >= n[b] + 1
and
n[b] >= n[a] + 1);
```

```
Overwriting cryptarithms.mod
```

```
m = AMPL()
m.read("cryptarithms.mod")
LETTERS = ["S", "E", "N", "D", "M", "O", "R", "Y"]
PAIRS = [(a, b) for a in LETTERS for b in LETTERS if a < b]
m.set["LETTERS"] = LETTERS
m.set["PAIRS"] = PAIRS
m.option["solver"] = SOLVER
m.solve()
n = m.var["n"].to_dict()
def letters2num(s):
return " ".join(map(lambda s: f"{int(round(n[s], 0))}", list(s)))
print(" ", letters2num("SEND"))
print(" + ", letters2num("MORE"))
print(" ----------")
print("= ", letters2num("MONEY"))
```

```
cbc 2.10.7: cbc 2.10.7: optimal solution
9 simplex iterations
9 barrier iterations
Objective = find a feasible point.
9 5 6 7
+ 1 0 8 5
----------
= 1 0 6 5 2
```

## Suggested exercises#

AMPL includes Logic, Nonlinear & Constraint Programming Extensions. Rewrite the model with different combinations of logical operators and compare the performance with one obtained with the constraint solver

`gecode`

.There are many more examples of cryptarithm puzzles. Refactor this code and create a function that can be used to solve generic puzzles of this type.