Ctrl+K

Extra material: Cryptarithms puzzle

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.

Preamble: Install Pyomo and a solver#

The following cell sets and verifies a global SOLVER for the notebook. If run on Google Colab, the cell installs Pyomo and the HiGHS solver, while, if run elsewhere, it assumes Pyomo and HiGHS have been previously installed. It then sets to use HiGHS as solver via the appsi module and a test is performed to verify that it is available. The solver interface is stored in a global object SOLVER for later use.

import sys
 
if 'google.colab' in sys.modules:
    %pip install pyomo >/dev/null 2>/dev/null
    %pip install highspy >/dev/null 2>/dev/null
 
solver = 'appsi_highs'
 
import pyomo.environ as pyo
SOLVER = pyo.SolverFactory(solver)
 
assert SOLVER.available(), f"Solver {solver} is not available."

Modeling and Solution#

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

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 Pyomo integer variables indexed by letters, then set up a 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*}\]
import pyomo.environ as pyo
import pyomo.gdp as gdp

m = pyo.ConcreteModel("Cryptarithms Problem")

m.LETTERS = pyo.Set(initialize=["S", "E", "N", "D", "M", "O", "R", "Y"])
m.PAIRS = pyo.Set(initialize=m.LETTERS * m.LETTERS, filter=lambda m, a, b: a < b)
m.n = pyo.Var(m.LETTERS, domain=pyo.Integers, bounds=(0, 9))


@m.Constraint()
def message(m):
    return (
        1000 * m.n["S"]
        + 100 * m.n["E"]
        + 10 * m.n["N"]
        + m.n["D"]
        + 1000 * m.n["M"]
        + 100 * m.n["O"]
        + 10 * m.n["R"]
        + m.n["E"]
        == 10000 * m.n["M"]
        + 1000 * m.n["O"]
        + 100 * m.n["N"]
        + 10 * m.n["E"]
        + m.n["Y"]
    )


# leading digit must be non-zero
@m.Constraint()
def leading_digit_nonzero(m):
    return m.n["M"] >= 1


# assign a different number to each letter
@m.Disjunction(m.PAIRS)
def unique_assignment(m, a, b):
    return [m.n[a] >= m.n[b] + 1, m.n[b] >= m.n[a] + 1]


# assign a "dummy" constant objective to avoid solver errors
@m.Objective()
def dummy_objective(m):
    return 0


pyo.TransformationFactory("gdp.bigm").apply_to(m)
SOLVER.solve(m)

print("The solution of the puzzle is:")
for l in m.LETTERS:
    print(f"{l} = {int(m.n[l]())}")


def letters2num(s):
    return " ".join(map(lambda s: f"{int(m.n[s]())}", list(s)))


print("\n\n    ", letters2num("SEND"))
print("  + ", letters2num("MORE"))
print("  ----------")
print("= ", letters2num("MONEY"))

The solution of the puzzle is:
S = 9
E = 5
N = 6
D = 7
M = 1
O = 0
R = 8
Y = 2


     9 5 6 7
  +  1 0 8 5
  ----------
=  1 0 6 5 2

Suggested exercises#

  1. Pyomo includes a logic-based solver GDPopt for generalized disjunctive programming problems. Implement and test GDPopt using combinations of solution strategies and MIP solvers. Compare the performance of GDPopt to 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.

Contents