Solving Alphametics with Python

(See also: Solving Alphametics with Python, Part 2).

Many Enigma puzzles use Alphametics (or Cryptarithms — see the Wikipedia page on Verbal Arithmetic for other terms), where a sum (or other expression) is given with the numbers consistently substituted for letters (or sometimes other symbols).

For example, Enigma 63, consists of solving the following Alphametic sum:

LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL.

By the time I came to solving this puzzle I had got a bit bored with writing programs to solve specific Alphametic sum problems, and decided it would be more fun to write a generic solver that could be used to solve any such substituted sum problem. The result was the SubstitutedSum() class in the enigma.py library, which allows various variations on Alphametic sums to be solved in a fairly efficient way.

(The code itself considers the columns of the sum moving from right to left, and when dealing with each column it looks at the possible substitutions for the symbols remaining unassigned in that column, and when it finds a suitable assignment it moves on to the next column to the left).

Later, I added the ability to invoke it directly from the command line, so for simple problems (like Enigma 63) it is not even necessary to write a program:

% python -m enigma SubstitutedSum "LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL"
LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL
8308440 + 8333218 + 8302040 + 8333260 = 33276958 / B=3 E=2 G=5 K=7 L=8 M=9 Q=4 R=0 S=1 V=6

This runs in 0.14s, which was actually faster than my original programmed solution.

---

This is all very well (and fast) for Alphametic problems which are simple addition sums, but what about more complicated problems? Enigma 1530, for instance, is a multiplication problem, and while it can be solved using SubstitutedSum() by turning the multiplication sum into a repeated addition I was interested in a solver that will work on arbitrary Python expressions.

There is such a solver (originally by Raymond Hettinger) which appears in several places on the web. The gist of it is to generate all the possible assignments of letters to digits, then substitute them into the expression and call Python’s eval() function on it. In pseudo-code:

# solve <expr> as an alphametic expression
def solve(expr):

  # extract the letters from expr
  letters = <letters occurring in expr>

  # consider possible assignments for each letter
  for digits in permutations('0123456789', len(letters)):

    # replace letters with corresponding digits
    new_expr = <expr with <letters> replaced by <digits>>

    if eval(new_expr):
      # output the solution
      <output solution>

This is obviously much slower than a specialised solver, as it can consider up to 10! = 3,628,800 different assignments of letters to digits, and then it calls eval() on each one. Each call to eval() will involve a parsing, compiling and finally execution stage.

While this is undoubtedly a very concise piece of code, that does indeed allow for the solving of arbitrary Alphametic expressions there are a couple of problems with it in general use.

Firstly (as previously mentioned), it is a bit slow. Generally it takes about a minute to consider all the possible assignments of 10 different digits to 10 letters (depending on the complexity of the expression).

Usually, my first weapon of choice to speed up Python programs is to try running them using PyPy. Unfortunately programs that make heavy use of eval() don’t benefit from the speed increases of PyPy, and my test program ran about 2.5× faster under CPython than under PyPy.

Secondly it isn’t that easy to extend it to incorporate the additional features that I added in to SubstitutedSum() (like solving in a different base, or specifying which assignments are allowed (to allow solutions using leading zeros), etc).

The code as published removes leading zeros from consideration (and the way it is written it will also exclude 0 itself as a standalone digit, which may or may not be what you want). If you try to allow leading zeros you run into problems. A literal of the form 072 is a Syntax Error in Python 3, and in Python 2 it evaluates to 58 as it is assumed to be octal, neither of which is particularly helpful behaviour in this situation.

Instead my SubstitutedExpression() code takes the initial expression, and replaces the words in it with placeholder arguments. It then uses eval() once to parse and compile a function that takes the numerical values of each word in the original expression. It then generates all the possible letter-to-digit assignments, generates the numbers that correspond to the words in the expression and passes those to the compiled function to see if the original expression is satisfied.

The pseudo-code for this is:

# solve <expr> as an alphametic expression
def solve(expr):

  # replace the words in expr with placeholders
  (body, words) = replace_words(expr)

  # make an executable function from <body>
  fn = eval("lambda <args>: <body>")

  # extract the letters in the words
  letters = <letters in <words>>

  # consider possible assignments for each letter
  for digits in permutations(irange(0, 9), len(letters)):

    # map the words to numbers using the digits
    args = list((<word> with <letters> replaced by <digits>) for <word> in <words>)

    # compute the result of the expression
    if fn(args):
      <output solution>

This works well, and allows us to use PyPy to gain a speed increase, and also to consider numbers in bases other than 10 and to allow leading zeros, as well as supporting the other bells and whistles carried over from the SubstitutedSum() solver.

It is however still slower than it needs to be in many cases. For instance, in Enigma 1530, we need to solve the (partial) Alphametic multiplication sum: TOM × 13 = DALEY. The whole expression has 8 letters that need to be substituted for digits, potentially requiring us to look at 10×9×8×7×6×5×4×3 = 1,814,400 possible assignments. But if we look at just the left hand side of the sum, there are only 3 letters in: TOM × 13, which only requires looking at 10×9×8 = 720 possible assignments. For each of those assignments we can look at the resulting product and then try and match it against the Alphametic result of: DALEY. Thereby reducing the number of possibilities we need to consider by a factor of 2,520.

The pseudo-code now looks something like this:

# solve <expr> = <value> as an alphametic equation
def solve(expr, value):

  # replace the words in expr with placeholders
  (body, words) = replace_words(expr)

  # make an executable function from <body>
  fn = eval("lambda <args>: <body>")

  # extract the letters in the words
  letters = <letters in <words>>

  # consider possible assignments for each letter
  for digits in permutations(irange(0, 9), len(letters)):

    # map the words to numbers using the digits
    args = list((<word> with <letters> replaced by <digits>) for <word> in <words>)

    # compute the result of the expression
    result = fn(args)

    # does the result match <value>
    solution = match(value, result)
    if solution:
      <output solution>

(While this approach appears to limit us to only considering Alphametic expressions of the form: <expr> = <value>, where <value> is a single literal (either an Alphametic “word” or an integer literal), this is not really a restriction, since boolean expressions evaluate to 0 or 1 we can treat any expression that doesn’t follow this pattern as: bool(<expr>) = 1, and we are back to an expression of the form: <expr> = <value>).

This is basically the approach I have used in the implementation of the SubstitutedExpression() solver in the enigma.py library (and I’ve allowed Alphametic() to be used as an alias for it to save typing). It can be invoked directly from the command line, so for many problems it is not necessary to write a separate program.

I have also allowed for several Alphametic expressions to be solved simultaneously. The solution (mapping from letters to digit values) that is generated from the first is used as a starting point for the second expression, and so on until all of the expressions are satisfied. The solver includes a heuristic algorithm to decided what order the expressions should be evaluated to try and minimise the number of possible assignments considered. (Although you can turn off the reordering if you prefer).

These are the command line arguments that can be used:

% python -m enigma Alphametic --help
usage: SubstitutedExpression [<opts>] <expression> [<expression> ...]
options:
 --symbols=<string> (or -s<string>) = symbols to replace with digits
 --base=<n> (or -b<n>) = set base to <n>
 --assign=<letter>,<digit> (or -a<l>,<d>) = assign digit to letter
 --digits=<digit>,... or --digits=<digit>-<digit> (or -d...) = available digits
 --invalid=<digit>,<letters> (or -i<d>,<ls>) = invalid digit to letter assignments
 --first (or -1) = stop after the first solution
 --reorder=<n> (or -r<n>) = allow reordering of expressions (0 = off, 1 = on)
 --verbose[=<n>] (or -v[<n>]) = verbosity (0 = off, 1 = solutions, 2 = more)
 --help (or -h) = show command-line usage

Here are some examples of Alphametic Enigma problems that can be solved directly using the SubstitutedExpression() solver from the command line. (I use the Alphametic alias to make the command line more compact):

---

First we solve a simple Alphametic sum — Enigma 63:

LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL.

% pypy -m enigma Alphametic "LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL"
(LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL)
(8308440 + 8333218 + 8302040 + 8333260 = 33276958) / B=3 E=2 G=5 K=7 L=8 M=9 Q=4 R=0 S=1 V=6

This runs in 4.8s, so the SubstitutedSum() solver is over 30× faster in this case.

---

A more complex problem, consisting of two simultaneous Alphametic sums is given in Enigma 5:

HMPDM + BHPHM = RCDHA,
RBAD + PQHD = AADD.

% pypy -m enigma Alphametic "HMPDM + BHPHM = RCDHA" "RBAD + PQHD = AADD"
(HMPDM + BHPHM = RCDHA) (RBAD + PQHD = AADD)
(24504 + 12524 = 37028) (3180 + 5620 = 8800) / A=8 B=1 C=7 D=0 H=2 M=4 P=5 Q=6 R=3

This runs in 0.46s. The same problem can be handled by the SubstitutedSum() solver in 0.045s, which is 10× faster.

---

Enigma 1407 has an Alphametic sum and an additional condition:

SAND + SUN + SEX + SEA = IBIZA,
SAND > SUN > SEX > SEA.

% pypy -m enigma Alphametic "SAND + SUN + SEX + SEA = IBIZA" "SAND > SUN > SEX > SEA"
(SAND + SUN + SEX + SEA = IBIZA) (SAND > SUN > SEX > SEA)
(9304 + 970 + 956 + 953 = 12183) (9304 > 970 > 956 > 953) / A=3 B=2 D=4 E=5 I=1 N=0 S=9 U=7 X=6 Z=8
(9306 + 970 + 954 + 953 = 12183) (9306 > 970 > 954 > 953) / A=3 B=2 D=6 E=5 I=1 N=0 S=9 U=7 X=4 Z=8

This takes 4.1s vs. 0.34s for my programmed solution.

---

Enigma 1664 is a similar problem:

PAY + ASP + YES + ERR + RYE + SPA = YAPS,
P < A < Y < E < R < S.

% pypy -m enigma Alphametic "PAY + ASP + YES + ERR + RYE + SPA = YAPS" "P < A < Y < E < R < S"
(PAY + ASP + YES + ERR + RYE + SPA = YAPS) (P < A < Y < E < R < S)
(123 + 291 + 369 + 688 + 836 + 912 = 3219) (1 < 2 < 3 < 6 < 8 < 9) / A=2 E=6 P=1 R=8 S=9 Y=3

This runs in 0.9s vs. 0.03s for my programmed solution.

---

Enigma 1530 is a multiplication problem:

TOM × 13 = DALEY.

% python -m enigma Alphametic "TOM * 13 = DALEY"
(TOM * 13 = DALEY)
(796 * 13 = 10348) / A=0 D=1 E=4 L=3 M=6 O=9 T=7 Y=8

This takes 0.08s vs. 0.04s for a programmed solution using SubstitutedSum(), so it is only 2× faster.

---

Enigma 323 has two Alphametic sums, although the exact answer is not given for the second one:

CUT + UTC + TCU = MEDS,
RIO + IOR + ORI = <missing>,
MEDS × <missing> = OMTTOUI.

% pypy -m enigma Alphametic "CUT + UTC + TCU = MEDS" "(RIO + IOR + ORI) * MEDS = OMTTOUI"
(CUT + UTC + TCU = MEDS) ((RIO + IOR + ORI) * MEDS = OMTTOUI)
(487 + 874 + 748 = 2109) ((563 + 635 + 356) * 2109 = 3277386) / C=4 D=0 E=1 I=6 M=2 O=3 R=5 S=9 T=7 U=8

This runs in 0.25s, compared to 0.04s for my programmed solution.

---

Enigma 253 has a sum, a product and a condition.

ENI + GMA = SUM,
ENI × GMA = ??MES,
I > 2 × U.

This one is faster if we order the expressions ourselves.

% pypy -m enigma Alphametic --reorder=0 "(ENI * GMA) % 1000 = MES" "ENI + GMA = SUM" "I > 2 * U"
(ENI + GMA = SUM) ((ENI * GMA) % 1000 = MES) (I > 2 * U)
(279 + 156 = 435) ((279 * 156) % 1000 = 524) (9 > 2 * 3) / A=6 E=2 G=1 I=9 M=5 N=7 S=4 U=3

This runs in 1.2s. If we let the solver choose the ordering of the clauses it takes 2.2s. My programmed solution (which uses SubstitutedSum()) takes 0.09s.

---

Enigma 1261 has an Alphametic sum with several additional conditions:

ALPHA + BETA + GAMMA = DELTA,
24 and 26 divide ALPHABET,
3 divides GAMMA.

Again, we get a faster solution if we order the clauses ourselves:

% pypy -m enigma Alphametic --reorder=0 "ALPHABET % 26 = 0" "ALPHABET % 24 = 0" "ALPHA + BETA + GAMMA = DELTA" "GAMMA % 3 = 0"
(ALPHABET % 26 = 0) (ALPHABET % 24 = 0) (ALPHA + BETA + GAMMA = DELTA) (GAMMA % 3 = 0)
(56375904 % 26 = 0) (56375904 % 24 = 0) (56375 + 9045 + 15225 = 80645) (15225 % 3 = 0) / A=5 B=9 D=8 E=0 G=1 H=7 L=6 M=2 P=3 T=4

This takes 8.6s. If we let the solver choose the ordering of the clauses it take 13s. These compare with 0.06s for my programmed solution.

---

Enigma 245 uses some symbols that are not standard capital letters. We use “e”, “n” and “g” to stand for the reversed capitals, and we can specify these on the command line argument:

ENIG × MA = AM × gIne,
E − N − M = M − n − e,
N = n + n,
IN = nI + nI.

% pypy -m enigma Alphametic --symbols=ENIGMAeng "ENIG * MA == AM * gIne" "E - N - M == M - n - e" "N == n + n" "IN == nI + nI"
(ENIG * MA == AM * gIne) (E - N - M == M - n - e) (N == n + n) (IN == nI + nI)
(6895 * 12 == 21 * 3940) (6 - 8 - 1 == 1 - 4 - 0) (8 == 4 + 4) (98 == 49 + 49) / A=2 E=6 G=5 I=9 M=1 N=8 e=0 g=3 n=4

It runs in 0.2s compared with 0.03s for my programmed solution.

---

We can solve problems in number bases other than 10, e.g. Enigma 1581: 

THOMAS − DALEY = GOLD (in base 11).

I’ve rearranged the expression into an addition sum to reduce the number of free symbols on the left hand side of the expression (GOLD + DALEY only has 7 free symbols, THOMAS − DALEY has 10).

% pypy -m enigma Alphametic --base=11 "GOLD + DALEY = THOMAS"
(GOLD + DALEY = THOMAS)
(639A + A7985 = 103274) / A=7 D=10 E=8 G=6 H=0 L=9 M=2 O=3 S=4 T=1 Y=5

This runs in 9.5s vs. 0.33s using SubstitutedSum() (which can also solve problems in different bases).

Note that the letter A appears both as a symbol to be substituted and a digit in base 11 numbers, so there is the possibility of confusion. We could eliminate it completely by using lowercase letters for the symbols:

% pypy -m enigma Alphametic --base=11 --symbols=adeghlmosty "gold + daley = thomas"
(gold + daley = thomas)
(639A + A7985 = 103274) / a=7 d=10 e=8 g=6 h=0 l=9 m=2 o=3 s=4 t=1 y=5

---

A similar approach works for Enigma 1663:

FAREWELL + FREDALO = FLINTOFF (in base 11).

% pypy -m enigma Alphametic --symbols=adefilnortw --base=11 "farewell + fredalo = flintoff"
(farewell + fredalo = flintoff)
(6157A788 + 6573189 = 68042966) / a=1 d=3 e=7 f=6 i=0 l=8 n=4 o=9 r=5 t=2 w=10
(61573788 + 657A189 = 68042966) / a=1 d=10 e=7 f=6 i=0 l=8 n=4 o=9 r=5 t=2 w=3

This runs in 55s. The SubstitutedSum() solver takes 0.08s.

---

Enigma 1361 gives us one of the assignments to start with:

ELGAR + ENIGMA = NIMROD.

We can add the assignment as an additional clause:

% pypy -m enigma Alphametic "ELGAR + ENIGMA = NIMROD" "O = 0"
(ELGAR + ENIGMA = NIMROD) (O = 0)
(71439 + 785463 = 856902) (0 = 0) / A=3 D=2 E=7 G=4 I=5 L=1 M=6 N=8 O=0 R=9

This runs in 2.6s.

Or we can solve it in a single expression and assign the letter O using a command line option:

% pypy -m enigma Alphametic --assign=O,0 "ELGAR + ENIGMA = NIMROD"
(ELGAR + ENIGMA = NIMROD)
(71439 + 785463 = 856902) / A=3 D=2 E=7 G=4 I=5 L=1 M=6 N=8 O=0 R=9

Which also runs in 2.6s.

The –assign option also works in the SubstitutedSum() solver, which solves this problem in 0.07s.

---

We can specify which digit are available — in Enigma 1272 the digit 9 is not used:

JONNY = WILKI + NSON.

We also re-order the sum so that the expression is on the left hand side of the equals sign.

% pypy -m enigma Alphametic --digits=0,1,2,3,4,5,6,7,8 "WILKI + NSON = JONNY"
(WILKI + NSON = JONNY)
(48608 + 3723 = 52331) / I=8 J=5 K=0 L=6 N=3 O=2 S=7 W=4 Y=1
(48708 + 3623 = 52331) / I=8 J=5 K=0 L=7 N=3 O=2 S=6 W=4 Y=1

This runs in 1.3s compared to 0.05s using the SubstitutedSum() solver.

---

Enigma 171 is a problem that uses numbers for symbols, but the numbers cannot stand for themselves:

1939 + 1079 = 6856.

We can handle this directly in the solver:

% pypy -m enigma Alphametic -s01356789 -i0,016 -i1,1 -i3,3 -i5,5 -i6,6 -i7,7 -i8,8 -i9,9 "1939 + 1079 = 6856"
(1939 + 1079 = 6856)
(2767 + 2137 = 4904) / 0=1 1=2 3=6 5=0 6=4 7=3 8=9 9=7

This runs in 0.5s vs. 0.08s using the SubstitutedSum() solver.

However there is possible ambiguity here. The value on the right hand side of the expression is interpreted either as a “word” (composed of symbols) or an integer literal (composed of numbers). In this case we could interpret the value in either way. The solver will interpret it as a “word” if it is entirely composed of symbols, otherwise it will try and parse it as a number (in the specified base). If both these approaches fail it will raise an error.

It might be better to rename the symbols to avoid any clash. Here is the same problem with the letters abcdefgh used instead of the digits 01356789.

% pypy -m enigma Alphametic -sabcdefgh -i0,abe -i1,b -i3,c -i5,d -i6,e -i7,f -i8,g -i9,h "bhch + bafh = egde"
(bhch + bafh = egde)
(2767 + 2137 = 4904) / a=1 b=2 c=6 d=0 e=4 f=3 g=9 h=7

---

Enigma 94 has an Alphametic sum and an additional condition.

BRAIN + STRAIN + AGAIN = ENIGMA,
ATE is a perfect cube.

Any of the functions defined in enigma.py is available for use in expressions.

% pypy -m enigma Alphametic "BRAIN + STRAIN + AGAIN = ENIGMA" "is_cube(ATE)"
(BRAIN + STRAIN + AGAIN = ENIGMA) (is_cube(ATE))
(98234 + 518234 + 27234 = 643702) (is_cube(216)) / A=2 B=9 E=6 G=7 I=3 M=0 N=4 R=8 S=5 T=1

This runs in 0.6s, compared to 0.04s for my programmed solution using SubstitutedSum().

---

Enigma 1627 has an Alphametic sum and some additional conditions.

ETA + BETA + THETA = DELTA,
PHI is prime,
PSI is prime.

% pypy -m enigma Alphametic "ETA + BETA + THETA = DELTA" "is_prime(PHI)" "is_prime(PSI)"
(ETA + BETA + THETA = DELTA) (is_prime(PHI)) (is_prime(PSI))
(250 + 8250 + 54250 = 62750) (is_prime(149)) (is_prime(139)) / A=0 B=8 D=6 E=2 H=4 I=9 L=7 P=1 S=3 T=5

This runs in 2.5s, compared with 0.045s for my programmed solution.

---

Enigma 1180 has a subtraction sum, and then several constraints on various numbers formed from substituted words:

SEVEN − THREE = FOUR,
SEVEN is prime,
FOUR is prime,
RUOF is prime,
TEN is square.

% pypy -m enigma Alphametic "SEVEN - THREE = FOUR" "is_prime(SEVEN)" "is_prime(FOUR)" "is_prime(RUOF)" "is_square(TEN)"
(SEVEN - THREE = FOUR) (is_prime(SEVEN)) (is_prime(FOUR)) (is_prime(RUOF)) (is_square(TEN))
(62129 - 58722 = 3407) (is_prime(62129)) (is_prime(3407)) (is_prime(7043)) (is_square(529)) / E=2 F=3 H=8 N=9 O=4 R=7 S=6 T=5 U=0 V=1

This runs in 0.72s compared with 0.06s for my programmed solution.

---

Enigma 1000 is a division sum:

ENIGMA ÷ M = TIMES.

We can specify this as a full expression (using == as the right hand side of the expression is not a “word” or an integer literal):

% pypy -m enigma Alphametic --invalid=0,EMT "divmod(ENIGMA, M) == (TIMES, 0)"
(divmod(ENIGMA, M) == (TIMES, 0))
(divmod(180426, 2) == (90213, 0)) / A=6 E=1 G=4 I=0 M=2 N=8 S=3 T=9

This runs in 7.8s.

Or we can re-write the expression to make it more friendly for the solver:

% pypy -m enigma Alphametic --invalid=0,EMT "M * TIMES = ENIGMA"
(M * TIMES = ENIGMA)
(2 * 90213 = 180426) / A=6 E=1 G=4 I=0 M=2 N=8 S=3 T=9

This runs in 0.45s, which compares to 0.042s for my programmed solution.

---

Here’s the solver let loose on a couple of recent Sunday Times Teaser puzzles:

Sunday Times Teaser 2796

SAINT + GEORGE = DRAGON,
GEORGE is even.

% pypy -m enigma Alphametic "SAINT + GEORGE = DRAGON" "E % 2 = 0"
(SAINT + GEORGE = DRAGON) (E % 2 = 0)
(72415 + 860386 = 932801) (6 % 2 = 0) / A=2 D=9 E=6 G=8 I=4 N=1 O=0 R=3 S=7 T=5

This runs in 8.8s, compared with 0.1s for a programmed solution.

---

Sunday Times Teaser 2803

AB × CDE = FGHIJ,
AB + CD + EF + GH + IJ = CCC.

% pypy -m enigma Alphametic "AB * CDE = FGHIJ" "AB + CD + EF + GH + IJ = CCC"
(AB * CDE = FGHIJ) (AB + CD + EF + GH + IJ = CCC)
(52 * 367 = 19084) (52 + 36 + 71 + 90 + 84 = 333) / A=5 B=2 C=3 D=6 E=7 F=1 G=9 H=0 I=8 J=4

This runs in 0.5s vs. 0.15s for my programmed solution.

---

We can see, then, that many Enigma puzzles (and other similar puzzles) can be solved directly using the SubstitutedSum() and SubstitutedExpression() solvers, often with only a few seconds of run time, and while that may be slower in execution time than writing a custom program to solve the puzzle, the amount of time saved in not writing a custom program is more than made up for.

The Alphametic solvers are available as part of the enigma.py library for solving puzzles in Python, and will be kept up to date with improvements there. I will try and keep the calling interface to the solvers the same as that described above.

Enjoy.