## Cryptarithms with MiniZinc, Python, and pymzn

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 for fac in facs]+[solution]) #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))) 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}]```