# Alphametric fun with Python

Terry Reedy tjreedy at udel.edu
Fri Jan 16 02:28:38 CET 2009

```bearophileHUGS at lycos.com wrote:
> Raymond Hettinger:
>> for simple programs that take minutes to write and get the job done.

Thank you for posting this.  It illustrates well the point you intended.

> For fun here's a specific example:
>
> from csp import Problem, timing
> print "SEND+MORE=MONEY problem:"
> p = Problem("recursivebacktracking")
> p.addrule(lambda d,e,y: (d+e)%10 == y) # alternative syntax

This effectively include the first rule and makes it redundant in a way.
Better, I expect (but leave to you to check), would be

(n*10+d+r*10+e)%100 / 10 == e

(e*100+n*10+d+o*100+r*10+e)%1000 / 100 == n

> p.addrule("1000*s+100*e+10*n+d + 1000*m+100*o+10*r+e == 10000*m+1000*o
> +100*n+10*e+y")

temp = 1000*s+100*e+10*n+d + 1000*m+100*o+10*r+e
temp%10000 / 1000 == o
temp / 10000 == m

> p.notin([0], "sm")
> p.alldifferent()
> solutions, time = timing(p.solutions)
> print "Computing time:", time, "s"
> for s in solutions:
>     print "%(s)d%(e)d%(n)d%(d)d + %(m)d%(o)d%(r)d%(e)d = %(m)d%(o)d%(n)
> d%(e)d%(y)d" % s
> print

Given 'expression == char' for each column, the equalities could be
turned into assignments (or checks).
For every possible assignment to d and e, let y = (d+e) % 10.
For every possible assignment of unused numbers to unbound chars in
the second column expression, let e = (n*10+d+r*10+e)%100 / 10

To generalize, 0 pad all lines to match the sum.  Then each nested loop
can be expressed in more detail as

for each possible assignment of unused numbers to unbound chars
in column_i: # break if none possible
div = 10**i
num = column_0_to_i_sum % (10*div) / div
if sum[i]_char is not bound:

> Probably it's not too much difficult to write a code able to solve a
> more general alphametric problem:

Hmm.  For alphametric problems specifically, 'expression == char' for
each column could be turned into assignments (or checks).

0 pad all lines to match the sum. Then nest column loops right to left.

for each possible assignment of unused numbers to unbound chars
in column_i: # include non-zero constraint and break if none possible
div = 10**i
num = column_0_to_i_sum % (10*div) / div
if sum[i]_char is not bound: bind to num
else: check that is num and break if not
if last (leftmost) column: print solution
else loop on column to left

Terry Jan Reedy

```