Alphametric fun with Python

[Terry Reedy]

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.addvars("sendmory", range(10))
> p.addrule(lambda d,e,y: (d+e)%10 == y) # alternative syntax
> p.addrule("(n*10+d+r*10+e)%100 == e*10+y")

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

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

(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