• ArithmoGraph

An arithmograph is a kind of a numeric crossword puzzle, where instead of filling the rows and columns with words, digits must be found that give numbers that fit the equations. In this example a following arithmograph has been used:

ABC - BBD = DEF
 /     +     -
 GH *  GD = BGC
 =     =     =
 DI + BJI = BIF

Each letter corresponds to a digit, always the same one, and different digits for different letters

To check all possibilities, 10! = 3628800 permutations would have to be checked. A brief analysis of the equation system allows us to reduce this number significantly.

First, we can see from III-down that C = 0. From II-down, I is even, non-zero. from I-down and II-down, H = 5. Further, we can see that some digits are no greater than a certain number, like from II-across we can see that (10*G)² < 1000, hence G² < 10, hence G <= 3, and since we already know that 0 is taken by C, G is in (1, 2, 3), etc.

All resulting constraints are specified in the CONSTRAINTS array. As a result, we now have less than 294912 permutations to check.

from operator import add, sub, mul

def DigitPoly(letterdigits):
    """Creates polynomial from digit IDs specified as abc..."""
    # 'abc' = 10*(10*a + b) + c
    orda = ord('a')
    digids = [ord(x.lower()) - orda for x in letterdigits]
    def tmp(values):
        val = 0
        for x in digids:
            val = 10*val + values[x]
        return val
    return tmp

def Equation(eqndata):
    """Creates equation test function from eqndata."""
    exp1 = DigitPoly(eqndata[0])
    exp2 = DigitPoly(eqndata[2])
    exp3 = DigitPoly(eqndata[3])
    def tmp(digits):
        return eqndata[1](exp1(digits), exp2(digits)) == exp3(digits)
    return tmp

def check_permutations(constraints, equations, digits):
    """Recursively checks all permutations in constraints on equations."""
    if constraints:
        for x in constraints[0]:
            if x in digits:
                continue
            check_permutations(constraints[1:], equations, digits+[x])
    else:
        for x in equations:
            if not x(digits):
                return
        print "Successful set of digits:", digits

NZ_EVEN = (2, 4, 6, 8)
CONSTRAINTS = ((1, 2, 3, 4, 6, 7, 8, 9),
               (1, 2, 3, 4),
               (0,),
               NZ_EVEN,
               (1, 2, 3, 4, 6, 7, 8, 9),
               NZ_EVEN,
               (1, 2, 3),
               (5,),
               NZ_EVEN,
               (1, 2, 3, 4, 6, 7))

EQUATIONS = (('abc', sub, 'bbd', 'def'),
             ('gh', mul, 'gd', 'bgc'),
             ('di', add, 'ji', 'if'),
             ('di', mul, 'gh', 'abc'),
             ('bd', add, 'gd', 'ji'),
             ('de', sub, 'bg', 'bi'))

if __name__ == "__main__":
    eqns = [Equation(x) for x in EQUATIONS]
    check_permutations(CONSTRAINTS, eqns, [])