Verbal Arithmetic and Mastermind

Two puzzles of deduction sit comfortably inside the same small frame of integer programming. The first is verbal arithmetic, where the digits of a sum have been hidden behind letters and the solver must read them back. The second is Mastermind, where a secret number is hunted through guesses and the scored replies they draw. Both are problems of assigning digits under constraints, the alphametic by the arithmetic of carrying, Mastermind by the bookkeeping of which guessed digits landed and where, and both fall to a handful of linear constraints. The pairing follows John Simon’s note in the INFORMS Transactions on Education puzzle column.

Verbal arithmetic

In an alphametic, each letter stands for a digit, distinct letters take distinct digits, and no number begins with a zero. The most famous is Henry Dudeney’s, $$\texttt{SEND} + \texttt{MORE} = \texttt{MONEY},$$ on the eight letters $S, E, N, D, M, O, R, Y$.

Variables and constraints

Let each letter be an integer variable in $\{0, \ldots, 9\}$, with the eight constrained all different, and $S, M \ge 1$ so neither four-digit number has a leading zero. The arithmetic is read one column at a time, right to left, carrying a $0$ or $1$ into the next. With carries $c_1, \ldots, c_4$, $$\begin{align} D + E &= Y + 10\,c_1, & c_1 + N + R &= E + 10\,c_2, \\ c_2 + E + O &= N + 10\,c_3, & c_3 + S + M &= O + 10\,c_4, \end{align}$$ and the final carry is the leading digit, $c_4 = M$. The column identities are exactly the schoolbook addition, made into linear equations.

The solver

from ortools.sat.python import cp_model

def send_more_money():
    m = cp_model.CpModel()
    S, E, N, D, M, O, R, Y = (m.NewIntVar(0, 9, c) for c in "SENDMORY")
    m.AddAllDifferent([S, E, N, D, M, O, R, Y])
    m.Add(S >= 1); m.Add(M >= 1)
    c1, c2, c3, c4 = (m.NewIntVar(0, 1, f"c{k}") for k in range(4))
    m.Add(D + E == Y + 10 * c1)          # units
    m.Add(c1 + N + R == E + 10 * c2)     # tens
    m.Add(c2 + E + O == N + 10 * c3)     # hundreds
    m.Add(c3 + S + M == O + 10 * c4)     # thousands
    m.Add(c4 == M)                       # the final carry is M
    s = cp_model.CpSolver()
    s.Solve(m)
    return {ch: s.Value(v)
            for ch, v in zip("SENDMORY", (S, E, N, D, M, O, R, Y))}

The puzzle has a single solution, $M = 1$, $O = 0$, and the rest falling into place to give $$9567 + 1085 = 10652.$$

Mastermind

In the numerical Mastermind played here, a secret is a five-digit number with all digits different. A guess is another such number, and the reply scores it two ways: $P$, the count of digits that are correct and in the correct position, and $D$, the count of guessed digits that appear somewhere in the secret, in place or not, so $P \le D$. In the familiar pegboard, $P$ is the black pegs and $D - P$ the white. After a run of guesses, each scored, the question is which secret is consistent with every reply, and that consistency is an integer program.

Variables and constraints

Let $p_1, \ldots, p_5$ be the secret’s digits, constrained all different, and let the boolean $h_d$ record whether digit $d$ occurs in the secret. For a guess $g$ scored $(P, D)$, the count of positions where the secret matches the guess must equal $P$, and the count of the guess’s (distinct) digits that the secret contains must equal $D$: $$\sum_{i = 1}^{5} [\,p_i = g_i\,] = P, \qquad \sum_{d \in g} h_d = D.$$ Each guess contributes one such pair of equations. Solving the accumulated system returns a secret consistent with all the evidence; when only one survives, the secret is found.

The solver

from ortools.sat.python import cp_model

def mastermind(clues):           # clues: list of (guess, P, D)
    m = cp_model.CpModel()
    p = [m.NewIntVar(0, 9, f"p{i}") for i in range(5)]
    m.AddAllDifferent(p)
    has = [m.NewBoolVar(f"h{d}") for d in range(10)]
    for d in range(10):
        occ = []
        for i in range(5):
            b = m.NewBoolVar("")
            m.Add(p[i] == d).OnlyEnforceIf(b)
            m.Add(p[i] != d).OnlyEnforceIf(b.Not())
            occ.append(b)
        m.Add(has[d] == sum(occ))            # digits distinct, so 0 or 1
    for guess, P, D in clues:
        exact = []
        for i in range(5):
            b = m.NewBoolVar("")
            m.Add(p[i] == guess[i]).OnlyEnforceIf(b)
            m.Add(p[i] != guess[i]).OnlyEnforceIf(b.Not())
            exact.append(b)
        m.Add(sum(exact) == P)               # right digit, right place
        m.Add(sum(has[d] for d in set(guess)) == D)  # right digit, any place
    s = cp_model.CpSolver()
    s.Solve(m)
    return tuple(s.Value(pi) for pi in p)

Figure 21.1 works one secret through six guesses. The first guess, $12345$, already scores one black peg and four whites; by the sixth the integer program has only one number left to report, the secret $47135$. The model never guesses, it only deduces: each reply is a constraint, and the constraints tighten until a single five-digit number satisfies them all.

Sources. Both formulations follow John T. Simon, Puzzle—Verbal Arithmetic and Mastermind, INFORMS Transactions on Education volume $17$, number $1$ ($2016$), pages $39$–$41$. The alphametic SEND $+$ MORE $=$ MONEY is Henry E. Dudeney’s, from Strand Magazine ($1924$). Mastermind was devised by Mordecai Meirowitz around $1970$; the optimal-strategy analysis of the classic pegs-and-colours version is Donald Knuth’s The Computer as Master Mind (Journal of Recreational Mathematics, $1976$). The deduction instance solved here is constructed so that six scored guesses determine the secret uniquely.