AdamTBradley.net

minizinc

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”, 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 (NB: Besides pymzn, there's also an official Python minizinc module). 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}]

#minizinc #python