Efficient way of Solving Cryptarithms

Question

Hi i came across this puzzle which is a subset of famous kind of word and numbers based puzzles called Cryptarithms. Say you have an expression as

S E N D + M O R E = M O N E Y

Now the interesting part there is that, each alphabet is representing a unique digit from 0-9. I wanted to write a generalized solver, but i ended up writing a brute forced solution for it. Any takers as how can i solve it?

I think it can be solved using predicate logic or set theory. And i'm particularly interested in finding C# or Python based solutions. Any one.?

Answer 1

this may be of some help

Edit: the answer on the wiki link you posted is also useful!

Answer 2

This is such a small problem that a brute-force solution is not a bad method. Assuming that each letter must represent a unique digit (i.e. we won't allow the solution S = 9, M = 1, * = 0) we see that number of combinations to try is n!, where n is the number of unique letters in the cryptarithm. The theoretical max number of combinations to evaluate is 10! = 3 628 800, which is really small number for a computer.

If we allow several letters to represent the same number, the number of combinations to try will be bounded by 10^n, again where n is the number of unique letters. Assuming only capital English letters we have a theoretical max number of combinations of 10^26, so for that theoretical worst case we might need some heuristics. Most practical cryptarithms have a lot less than 26 unique letters though, so the normal case will probably be bounded by an n less than 10, which is again pretty reasonable for a computer.

Answer 3

On this year's PyCon Raymond Hettinger talked about AI programing in Python, and has covered Cryptarithms.

The video of entire talk can be seen here, and cookbook with solution can be found on this link.

Answer 4

Well, try writing it as a list of functions:

 SEND
 MORE
----+
MONEY

If I remember my lower school math, this should be:

Y = (D+E) mod 10
E = ((N+R) + (D+E)/10) mod 10
...