MiniZinc cryptarithms improved

(published and tagged

Previously, I posted an experiment in solving cryptarithms with Python and MiniZinc. I've just put an improved version on GitHub, since I figured out how to generalize the problem somewhat--Python now just converts your problem into a dictionary and feeds that to an existing script that doesn't have to change. This new model still has some rough edges--artifacts of the learning process--but it works well enough.

Cryptarithms with MiniZinc, Python, and pymzn

(published and tagged

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}]

About Me

Developer at Brown University Library specializing in instructional design and technology, Python-based data science, and XML-driven web development.

Tags