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

\[\begin{split} \begin{align*} 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 \end{align*} \end{split}\]

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

\[ \begin{align*} \begin{bmatrix}n_a \lt n_b\end{bmatrix} \ \veebar\ & \begin{bmatrix}n_b \lt n_a\end{bmatrix} & \forall a \lt b \end{align*}\]
%%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#

  1. 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.

  2. 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.