Cryptarithms

Cryptarithms, or Verbal arithmetic, are substitution puzzles where letters represent unique digits:

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


The goal is to find the digit-letter mapping which will translate the puzzle into a valid mathematical computation.

My goal was to write a Python script which will find the solution(s).

Method

Using the above puzzle, the solution finder breaks the puzzle down into a series of digit-sum columns. Starting at the left (carry in & carry out from columns not shown)

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


Starting at the 1's column (D+E=Y), the solver tries D=0 and E=1, and computes Y=1. This solution is discarded, since duplicate 1 is already used by E. After several more iterations, it eventual tries D=1, E=2 and directly computes 1+2=Y and determines Y=3 with no carry into the tens column.

With a valid ones column digit-sum, it advances to the tens column: N+R=E. Since E has already been assigned a value from the ones-column, it is "known". The first available digit for N is 4, so the column solver evaluates 4+R=2, and determines R=8 with a carry of 1 into the hundreds column.

It descends deeper into the hundreds column, and possibly deeper still to the thousands column, as it continues its exploration. When it reaches impossibilities, it unwinds the stack, and explores different branches.

Since the solution is generated using yield and yield from statements, when the first solution is found, it returns that solution, and pauses the search, until the next solution is requested.

The test code actually tries to generate all solutions, to ensure the solutions to the given puzzles are unique. Some of the example puzzles are taken from Cryptarithms.com.

Code

All feedback welcome.

import re

from collections import Counter
from time import perf_counter
from typing import Callable, Iterator, NewType

Term = NewType('Term', str)
Operator = NewType('Operator', str)

Solution = dict[str, int]
Solver = Callable[[set[int]], Iterator[Solution]]

TRACE = False

#===============================================================================

class CryptArithm:
"""
Solver for a "word math" puzzle

S E N D        9 5 6 7
+ M O R E      + 1 0 8 5
=========      =========
M O N E Y      1 0 6 5 2
"""

SUPPORTED_OPS = {'=', '+', '-'}

#---------------------------------------------------------------------------

class Variable:
"""
A letter-variable in the word-math puzzle.

Holds the letter, the allowed digits for the letter, and its
current candidate value.
"""

__slots__ = ('_letter', '_allowed', '_value')

def __init__(self, solver: 'CryptArithm', letter: str):
self._letter = letter
self._allowed = set(solver._digits)
self._value = 0

def exclude(self, *values):
"""
Specified one or more verboten values for the variable.

Used primarily to prevent terms with leading zeros.
"""
self._allowed -= set(values)

def solver(self, solver: Solver) -> Solver:
"""
The solver for a variable simply tries each allowable digit,
in turn, provided the digit is not currently used by another
letter.

For each valid possible digit, yield solutions from the
next solver, passed in as an argument.
"""

def solve(used: set[int]) -> Iterator[Solution]:
"""
The solve for a variable by trying each allowable digit,
in turn, provided the digit is not currently in use.
Digits in use are passed as an argument

For each valid possible digit, yield solutions from the
next solver, passed in as an argument to the wrapper.
"""

for digit in self._allowed - used:
self._value = digit
yield from solver(used | {digit})

return solve

def __str__(self):
value = self._value
if value is None:
value = '{' + ''.join(map(str, self._allowed)) + '}'
return f"{self._letter}={value}"

def __repr__(self):
return f"<{self._letter}>"

#---------------------------------------------------------------------------

class Column:
"""
A digit-sum column in the word-puzzle.

For example, with SEND+MORE=MONEY, the last column of digits
expresses the digit sum D+E=Y.

A digit-sum will include a carry-in from a "smaller" column, if
present, and a carry-out to a "larger" column, if present.
"""

def __init__(self, solver: 'CryptArithm', result: 'Variable'):
self._base = solver._base
self._result = result
self._carry_in = None
self._carry_to = None
self._carry = 0

def add(self, var: 'Variable') -> None:
"""
"""

def sub(self, var: 'Variable') -> None:
"""
Subtract a digit subtrahend from the digit sum.
"""

def carry_from(self, other: 'Column') -> None:
"""
Indicate this digit-sum has a carry-in from another column.
"""
self._carry_in = other
other._carry_to = self

def __str__(self):
exp = f"{self._result._letter}=" if self._result else "0="
if self._carry_in:
exp += "carry"
if count == 1:
exp += f"+{var._letter}"
elif count == -1:
exp += f"-{var._letter}"
elif count != 0:
exp += f"{count:+d}{var._letter}"
return exp

def __repr__(self):
return f"Col[{self}]"

def unknowns(self, knowns: set['Variable']) -> list['Variable']:
"""
Given a set of known variables, determine the list of
unknown variables in this digit-sum column, ordered in
decreasing usage.
"""
if self._result:
unknowns[self._result] -= 1

unknowns = [(var, abs(count)) for var, count in unknowns.items()]
unknowns = sorted(unknowns, key=lambda vc: vc[1], reverse=True)
return [var for var, _ in unknowns if var not in knowns]

def validator(self, solver: Solver) -> Solver:
"""
When all digits are "known" in a digit-sum column, verify the
correct result digit is obtained and compute the carry to the
next column.  If the digit-sum is correct, and a carry out is
allowed or the carry is determined to be zero, yield solutions
from the next solver, passed in as an argument.
"""

def validate(used: set[int]) -> Iterator[Solution]:
"""
When all digits are "known" in a digit-sum column, verify the
correct result digit is obtained and compute the carry to the
next column.  If the digit-sum is correct, and a carry out is
allowed or the carry is determined to be zero, yield solutions
from the next solver, passed in as an argument to the wrapper.
"""
result = sum(count * var._value
if self._carry_in:
result += self._carry_in._carry

carry, result = result // self._base, result % self._base

if (result == self._result._value and
(carry == 0 or self._carry_to)):
self._carry = carry
yield from solver(used)

return validate

def _solve_for_result(self, solver: Solver) -> Solver:
"""
When all digits but the result digit are known in a digit-sum
column, compute the result digit and carry to the next column.
If the result digit is allowed (and not currently used by
another variable), yield solutions from the next solver,
passed in as an argument.
"""

def solve(used: set[int]) -> Iterator[Solution]:
"""
When all digits but the result digit are known in a digit-sum
column, compute the result digit and carry to the next column.
If the result digit is allowed (and not in the used set),
yield solutions from the next solver, passed in as an argument
to the wrapper function.
"""
result = sum(count * var._value
if self._carry_in:
result += self._carry_in._carry

carry, digit = result // self._base, result % self._base

allowed = self._result._allowed - used
if digit in allowed and (carry == 0 or self._carry_to):
self._result._value = digit
self._carry = carry
yield from solver(used | {digit})

return solve

"""
One unknown digit in the digit-sum column, but not the digit-sum's
result digit.

Use modular arithmetic to compute the unique digit that satisfies
the digit-sum column.  If the digit is allowed (and not used),
yield solutions from the subsequent solver.
"""
def solver(solver: Solver) -> Solver:
def solve(used: set[int]) -> Iterator[Solution]:
result = sum(count * var._value
if self._carry_in:
result += self._carry_in._carry

digit = (self._result._value - result) * multiplier
digit %= self._base

result += digit * multiplier
carry = result // self._base

if digit in allowed and (carry == 0 or self._carry_to):
self._carry = carry
yield from solver(used | {digit})

return solve
return solver

def solver(self, unknown: 'Variable'):
"""
Determine which specialized solver to used for a digit sum column.

If the only unknown is the result digit,
use the solve_for_result solver.
If the only unknown is not a repeated digit,

Returns None if no specialized solver exists.
"""
if unknown == self._result:
return self._solve_for_result

return None

#---------------------------------------------------------------------------

def __init__(self, puzzle: str, base: int = 10, leading_zeros: bool = False):
self._puzzle = puzzle
self._base = base

self._digits = range(base)
self._variables = self._create_variables(puzzle)
self._columns = self._create_columns(puzzle)

def _create_variables(self, puzzle: str) -> dict[str, Variable]:
"""
Create a variable for each unique letter in the puzzle.
"""

letters = set(ch for ch in puzzle if ch.isalpha())
if len(letters) > self._base:
raise ValueError(f"Puzzle has too many variables for base-{base}")

return {letter: self.Variable(self, letter) for letter in letters}

@classmethod
def _parse(cls, puzzle: str) -> tuple[list[Operator], list[Term]]:
"""
Parse the puzzle into tokens.

* Remove all spaces
* Replace multiple equal signs with a single equals character
* Split into word and non-word tokens
* Validate proper term/operator sequence
* Return operators and terms separately.
"""

equation = re.sub('=+', '=', re.sub(r'\s+', '', puzzle))
tokens = re.split(r'(\W+)', equation)
terms = [token for token in tokens if token.isalpha()]
operators = [token for token in tokens if not token.isalpha()]

# Validation
if len(tokens) < 5 or len(terms) != len(operators) + 1:
raise ValueError("Expected 'term op term op term [op term]...'")

if (unsupported := set(operators) - cls.SUPPORTED_OPS):
raise NotImplementedError(f"Unsupported: {repr(unsupported)[1:-1]}")

if operators.count('=') != 1:
raise ValueError("Only one equals operator allowed")

if operators[-1] != '=':
raise ValueError("Last operator expected to be equals")

return operators, terms

def _create_columns(self, puzzle: str) -> list[Column]:
"""
Parse the puzzle into a list of digit-sum columns.
"""
operators, terms = self._parse(puzzle)

# Leading zeros are not allowed
for term in terms:
if len(term) > 1:
self._variables[term[0]].exclude(0)

num_columns = max(map(len, terms))      # Maximum columns
terms = [term[::-1] for term in terms]  # Reverse individual terms
operators.insert(0, '+')                # First term is "added"
result = terms.pop()                    # Extract result

# Extract into columns
columns = []
for col_num in range(num_columns):
if col_num < len(result):
var = self._variables[result[col_num]]
else:
var = None

column = self.Column(self, var)
for op, term in zip(operators, terms):
if col_num < len(term):
var = self._variables[term[col_num]]
if op == '+':
elif op == '-':
column.sub(var)
else:
raise RuntimeError(f"Unexpected operator: {op}")

columns.append(column)

for to, frm in zip(columns[1:], columns[:-1]):
to.carry_from(frm)

return columns

def _strategize(self):
"""
Determine a solving strategy.

Returns a list of strategy functions.
"""

strategies = []
knowns = set()

# For each column, starting at the ones-column...
for column in self._columns:
unknowns = column.unknowns(knowns)
if TRACE:
print(f"{column}: {unknowns}")

# If the column has unknowns...
if unknowns:
# if it has more than one uknown ...
for var in unknowns[:-1]:
strategies.append(var.solver)

# For the last unknown, attempt to find a specialized solver
last = unknowns[-1]
solver = column.solver(last)
if solver:
strategies.append(solver)
else:
# Failing that, try every possible value ...
strategies.append(last.solver)
# ... and validate the column
strategies.append(column.validator)

knowns |= set(unknowns)
else:
# No unknowns!  Just validate the column
strategies.append(column.validator)

return strategies

def solutions(self) -> Iterator[Solution]:
"""
Create a solver strategy, and then generate all possible
solutions.
"""

strategies = self._strategize()
solver = self._emitter()
for strategy in reversed(strategies):
solver = strategy(solver)

yield from solver(set())

def solve(self) -> Solution:
"""
Find the unique solution to the puzzle.
"""
solutions = self.solutions()
try:
solution = next(solutions)
except StopIteration:
raise ValueError("No solution found") from None

try:
solution = next(solutions)
raise ValueError("Multiple solutions!")
except StopIteration:
return solution

def _emitter(self) -> Solver:
def solver(used: set[int]) -> Iterator[Solution]:
yield {var._letter: var._value for var in self._variables.values()}
return solver

def substitute(self, solution: dict[str, int]) -> str:
"""
Translate the puzzle using the given solution, into a numeric
version of the puzzle.
"""
if self._base > 10:
raise NotImplementedError("Not yet implemented.")

puzzle = self._puzzle
for key, val in solution.items():
puzzle = puzzle.replace(key, str(val))

return puzzle

#===============================================================================

if __name__ == '__main__':

puzzles = [
"""\
S E N D
+ M O R E
=========
M O N E Y""",

"""\
F O R T Y
+   T E N
+   T E N
=========
S I X T Y""",

"""\
T I L E S
+ P U Z Z L E S
===============
P I C T U R E""",

"""\
D O U B L E
+ D O U B L E
+     T O I L
=============
T R O U B L E""",

"""\
T H R E E
+ T H R E E
+     T W O
+     T W O
+     O N E
===========
E L E V E N""",

"""\
SO+MANY+MORE+MEN+SEEM+TO+SAY+THAT+
THEY+MAY+SOON+TRY+TO+STAY+AT+HOME+
SO+AS+TO+SEE+OR+HEAR+THE+SAME+ONE+
MAN+TRY+TO+MEET+THE+TEAM+ON+THE+
MOON+AS+HE+HAS+AT+THE+OTHER+TEN
=TESTS
"""
]

for puzzle in puzzles:
start = perf_counter()
ca = CryptArithm(puzzle)
solution = ca.solve()
stop = perf_counter()

print(f"{stop-start:.3f} sec")
print(ca.substitute(solution))
print()


Output

0.006 sec
9 5 6 7
+ 1 0 8 5
=========
1 0 6 5 2

0.007 sec
2 9 7 8 6
+   8 5 0
+   8 5 0
=========
3 1 4 8 6

0.003 sec
9 1 5 4 2
+ 3 0 7 7 5 4 2
===============
3 1 6 9 0 8 4

0.002 sec
7 9 8 0 6 4
+ 7 9 8 0 6 4
+     1 9 3 6
=============
1 5 9 8 0 6 4

0.007 sec
8 4 6 1 1
+ 8 4 6 1 1
+     8 0 3
+     8 0 3
+     3 9 1
===========
1 7 1 2 1 9

3.398 sec
31+2764+2180+206+3002+91+374+9579+
9504+274+3116+984+91+3974+79+5120+
31+73+91+300+18+5078+950+3720+160+
276+984+91+2009+950+9072+16+950+
2116+73+50+573+79+950+19508+906
=90393


Bugs

This code will crash:

        raise ValueError(f"Puzzle has too many variables for base-{base}")


since base is not defined. You likely meant to write self._base.

Quality of life

Consider expressing your output durations in milliseconds instead of seconds and include one or two decimals for more precision; and showing the original puzzle along with its output.

Scoped main

It's not enough to have a __main__ guard - all of those symbols are still going to be in global scope and visible to the rest of your CryptArithm code unless you move the main code into a function.

Such namespace pollution can have surprising effects, so it's best to avoid it altogether and limit the scope of your main symbols.

Early constraints

I think you're doing the right thing by declaring leading_zeros as a constructor argument defaulting to False. I find it odd, however, that at one point during construction the instance is effectively in an incorrect/inconsistent state, because the leading variable's _allowed still includes zero. It's possible to prune zero from this variable on construction without requiring storage of the leading_zeros member. That said, this is somewhat chicken-and-egg, because you're setting up your variables before you parse. If you set up your variables during or after parse this inconsistency can be avoided.

Alternate algorithms

I wrote an alternate approach to this that:

• Forms a linear discrete system of polynomial order 1
• Attempts to solve the system with a recursive root-finding loop
• Performs tree pruning based on the knowledge that the polynomial, when sorted in decreasing order of its coefficients, will produce a monotonically increasing sum given a lexicographically sorted permutation

This approach scales quite differently from yours. In most cases it's slower, but in others it's able to yield a result very quickly.


def by_coeff(kv):
return kv[1]

class CryptRoots:
__slots__ = ('puzzle_desc', 'coeffs', 'names', 'zero_pos')

RE_WS = re.compile('\s*')
RE_EQN = re.compile(
r'^([^=]+?)'
r'=+'
r'([^=]+?)\$'
)
RE_TERMS = re.compile(
r'([+-])\s*([ A-Z]+)'
)

def __init__(self, puzzle_desc: str):
self.puzzle_desc = puzzle_desc
puzzle_desc = self.RE_WS.sub('', puzzle_desc)
left, right = self.RE_EQN.search(puzzle_desc).groups()
variables = defaultdict(int)
terms = self.RE_TERMS.findall('+' + left)

for op, term in terms:
fac = 10**(len(term) - 1)
if op == '-':
fac = -fac

for c in term:
variables[c] += fac
fac //= 10

fac = 10**(len(right) - 1)
for c in right:
variables[c] -= fac
fac //= 10

variables = sorted(variables.items(), key=by_coeff, reverse=True)
self.coeffs = tuple(v for name, v in variables)
self.names = tuple(name for name, v in variables)
self.zero_pos = next(i for i, v in enumerate(self.coeffs) if v <= 0)

def recurse(
self,
remain: Tuple[int, ...],
chosen: Tuple[int, ...],
total: int=0,
depth: int=0,
) -> Iterable[Tuple[int, ...]]:
global node_visits
node_visits += 1

coeffs = self.coeffs[depth:]
coeff = coeffs[0]
n = len(coeffs)

# We have a certain total that we need to reduce to zero
# If the current total plus the potential upper and lower bounds does
# not produce an interval that covers zero, reject this candidate
#      t+lb  <=    0    <=    t+ub
#      lb    <=    -t   <=    ub

if coeff != 0:
x_needed = -total / coeff

if n == 1:
x_int = int(x_needed)
if 0 <= x_int < 10 and x_needed == x_int:
yield chosen + (x_int,)
return

remain_asc = sorted(remain)
zero_pos = self.zero_pos - depth

if zero_pos > 0:
upper_x = remain_asc[-1: -zero_pos-1: -1] + remain_asc[n-zero_pos-1:: -1]
else:
upper_x = remain_asc[n-1::-1]

# This is effectively np.dot, but numpy arrays are much slower in this
# method - possibly due to the number of appends and deletes
upper = sum(
x*c for x, c in zip(upper_x, coeffs)
)
if -total > upper:
return

if zero_pos > 0:
lower_x = remain_asc[:zero_pos] + remain_asc[zero_pos-n:]
else:
lower_x = remain_asc[-n:]

lower = sum(
x*c for x, c in zip(lower_x, coeffs)
)
if lower > -total:
return

# We can sort in order of increasing error from x_needed, but that ends
# up offering no performance advantage

for i, x in enumerate(remain):
yield from self.recurse(
remain[:i] + remain[i+1:],
chosen + (x,),
total + x*coeff,
depth+1,
)

def solve(self) -> Tuple[int, ...]:
return next(self.recurse(tuple(range(10)), ()))

def substitute(self, solution: Tuple[int, ...]) -> str:
res = self.puzzle_desc
for value, name in zip(solution, self.names):
res = res.replace(name, str(value))
return res

def main():
puzzles = [
"""\
F O R T Y
+   T E N
+   T E N
=========
S I X T Y""",

"""\
S E N D
+ M O R E
=========
M O N E Y""",

"""\
T I L E S
+ P U Z Z L E S
===============
P I C T U R E""",

"""\
D O U B L E
+ D O U B L E
+     T O I L
=============
T R O U B L E""",

"""\
T H R E E
+ T H R E E
+     T W O
+     T W O
+     O N E
===========
E L E V E N""",

"""\
SO+MANY+MORE+MEN+SEEM+TO+SAY+THAT+
THEY+MAY+SOON+TRY+TO+STAY+AT+HOME+
SO+AS+TO+SEE+OR+HEAR+THE+SAME+ONE+
MAN+TRY+TO+MEET+THE+TEAM+ON+THE+
MOON+AS+HE+HAS+AT+THE+OTHER+TEN
=TESTS
"""
]

for i, puzzle in enumerate(puzzles):
for solver in (CryptArithm, CryptRoots):
global node_visits
node_visits = 0
start = perf_counter()
ca = solver(puzzle)
solution = ca.solve()
stop = perf_counter()

print(f"{i}. {solver.__name__}: {1e3*(stop - start):.1f} ms, {node_visits} nodes")

print()


On my "nothing-special" laptop this yields

0. CryptArithm: 4.4 ms, 2204 nodes
0. CryptRoots: 508.8 ms, 285762 nodes

1. CryptArithm: 3.0 ms, 356 nodes
1. CryptRoots: 18.7 ms, 12774 nodes

2. CryptArithm: 2.0 ms, 1365 nodes
2. CryptRoots: 32.4 ms, 16883 nodes

3. CryptArithm: 1.1 ms, 153 nodes
3. CryptRoots: 1091.3 ms, 659674 nodes

4. CryptArithm: 4.6 ms, 1870 nodes
4. CryptRoots: 209.4 ms, 122197 nodes

5. CryptArithm: 2719.1 ms, 832613 nodes
5. CryptRoots: 25.4 ms, 13305 nodes


Since I was focusing on performance exploration and not cleanliness, this doesn't validate the input as thoroughly as yours.

• Good catch with the self._base. Fair point about the scoped main. I'll have to give some more thought to the early constraint point. Regarding quality of life's seconds & milliseconds, the 3 second case at the end would not benefit from sub-millisecond resolution, but if you've got performance ideas, it would definitely be required for comparison purposes for the other cases; I look forward to seeing them. Commented Dec 26, 2020 at 5:42
• @AJNeufeld Alternate posted. If I figure out some Diophantine fanciness I might have another alternate coming. Commented Dec 30, 2020 at 21:49
• Interesting alternative, cool! I see you're cheating by finding only the first solution, and not exhaustively checking if there are multiple solutions. If I do that (solution = next(ca.solutions())), my solution times range from 0.6ms (THREE+THREE+TWO+TWO+ONE=ELEVEN and TILES+PUZZLE=PICTURE) to 4.8ms (SEND+MORE=MONEY), with 204.9ms for the last puzzle. Still your solution is eight times faster for the last puzzle and mine is eight times faster for the second last; for a programming contest, the ideal solution would need to choose between the strategies somehow. Interesting problem. Commented Dec 31, 2020 at 17:34