A couple of entries in the AMS Page a Day Calendar so far have been cryptarithms. I most recently encountered these in the Coursera course on ("Basic Modeling for Discrete Optimization")](https://www.coursera.org/learn/basic-modeling), which uses them as an early example to teach MiniZinc. It's fairly easy to adapt existing code to solve this problem:
ZEROES + ONES = BINARY:
%From the AMS page-a-day calendar
var 0..9: Z;
var 0..9: E;
var 0..9: R;
var 0..9: O;
var 0..9: S;
var 0..9: N;
var 0..9: B;
var 0..9: I;
var 0..9: A;
var 0..9: Y;
constraint Z != 0;
constraint O != 0;
constraint B != 0;
constraint
100000 * Z + 10000 * E + 1000 * R + 100 * O + 10 * E + S
+ 1000 * O + 100 * N + 10 * E + S
= 100000 * B + 10000 * I + 1000 * N + 100 * A + 10 * R + Y;
include "alldifferent.mzn";
constraint alldifferent([Z,E,R,O,S,N,B,I,A,Y]);
%solve maximize (10000 * V + 1000 * E + 100 * R + 10 * S + E);
It's probably fairly easy to make a MiniZinc script that reads the problem from a data file instead of having it hardcoded, but I'm not that good with MiniZinc (I haven't finished the course). But this does seem like a good excuse to tinker with pymzn
, a Python interface to MiniZinc. Here's my Python script to build a MiniZinc cryptarithm-solver script, run it, and return the results:
import io
import json
import re
import pymzn
def cryptarithm(problem):
mznscript = io.StringIO('')
prob = problem.replace(' ', '')
(facs, solution) = prob.split('=')
facs = facs.split('+')
#Set of all unique letters in the problem
letters = set(re.sub('[+=\s]', '', prob))
#All letters at the beginning of a "number"
initials = set([fac[0] for fac in facs]+[solution[0]])
#declare all variables.
#First letters != 0.
print(*[f'var 1..9: {l};' for l in initials], sep="\n", file=mznscript)
print(*[f'var 0..9: {l};' for l in letters.difference(initials)], sep="\n", end="\n\n", file=mznscript)
#Each letter stands for a different number.
print('include "alldifferent.mzn";', file=mznscript)
print(f'constraint alldifferent([{",".join(letters)}]);', file=mznscript)
#Add the main constraint.
print('\nconstraint', file=mznscript)
#This is ugly. Don't do this in actually-useful code.
print(' '+'\n + '.join([' + '.join(f'{10**n} * {l}' for n,l in enumerate(reversed(tuple(fac)))) for fac in facs]), file=mznscript)
print(' = '+' + '.join([f'{10**n} * {l}' for n,l in enumerate(reversed(tuple(solution)))])+';', end="\n\n", file=mznscript)
print('solve satisfy;', file=mznscript)
mznscript.seek(0)
script = mznscript.read()
return (script, [dict(sorted(json.loads(sol).items(), key=lambda x: problem.index(x[0])))
for sol
in pymzn.minizinc(script, output_mode='json')])
And some use examples:
>>> script, solutions = cryptarithm('ZEROES + ONES = BINARY')
>>> print(solutions)
[{'Z': 6, 'E': 9, 'R': 8, 'O': 3, 'S': 2, 'N': 1, 'B': 7, 'I': 0, 'A': 5, 'Y': 4}]
>>> script, solutions = cryptarithm('SEND+MORE=MONEY')
>>> print(solutions)
[{'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O': 0, 'R': 8, 'Y': 2}]
>>> script, solutions = cryptarithm('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')
>>> print(solutions)
[{'T': 9, 'A': 7, 'O': 1, 'M': 2, 'H': 5, 'S': 3, 'E': 0, 'N': 6, 'Y': 4, 'R': 8}]
>>> script, solution = cryptarithm('TWO + TWO = FOUR')
>>> print(solution)
[{'F': 1, 'T': 7, 'W': 3, 'R': 8, 'U': 6, 'O': 4}]