Alphametric fun with Python

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Thu Jan 15 20:51:42 CET 2009


Raymond Hettinger:
> for simple programs that take minutes to write and get the job done.

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")
p.addrule("(e*100+n*10+d+o*100+r*10+e)%1000 == n*100+e*10+y")
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")
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

Probably it's not too much difficult to write a code able to solve a
more general alphametric problem: you can write it more or less like
yours, but it leads to a single equation, that is slow to solve. To
give the solver engine a chance to speed up the computation you have
to split the single equation into many equations. This allows the
solver to prune that large search space in a faster way (the search
space may have 3+ millions items so it's not huge anyway).

Bye,
bearophile



More information about the Python-list mailing list