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._addends = Counter()
self._result = result
self._carry_in = None
self._carry_to = None
self._carry = 0
def add(self, var: 'Variable') -> None:
"""
Add a digit addend to the digit sum.
"""
self._addends[var] += 1
def sub(self, var: 'Variable') -> None:
"""
Subtract a digit subtrahend from the digit sum.
"""
self._addends[var] -= 1
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"
for var, count in self._addends.items():
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.
"""
unknowns = Counter(self._addends)
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
for var, count in self._addends.items())
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
for var, count in self._addends.items())
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
def _solve_for_addend(self, addend: 'Variable'):
"""
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]:
addend._value = 0
result = sum(count * var._value
for var, count in self._addends.items())
if self._carry_in:
result += self._carry_in._carry
multiplier = self._addends[addend] # +/- 1
digit = (self._result._value - result) * multiplier
digit %= self._base
result += digit * multiplier
carry = result // self._base
allowed = addend._allowed - used
if digit in allowed and (carry == 0 or self._carry_to):
addend._value = digit
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,
use the solve_for_addend solver.
Returns None if no specialized solver exists.
"""
if unknown == self._result:
if self._addends[unknown] == 0:
return self._solve_for_result
elif abs(self._addends[unknown]) == 1:
return self._solve_for_addend(unknown)
return None
#---------------------------------------------------------------------------
def __init__(self, puzzle: str, base: int = 10, leading_zeros: bool = False):
self._puzzle = puzzle
self._base = base
self._leading_zeros = leading_zeros
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
if not self._leading_zeros:
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
operators.pop() # Discard "=" operator
# 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 == '+':
column.add(var)
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
