# Enigmatic Code

Programming Enigma Puzzles

## Enigma 63: Addition: letters for digits

From New Scientist #1206, 19th June 1980 [link]

Below is an addition sum with letters substituted for digits. The same letter stands for the same digit wherever it appears, and different letters stand for different digits. Write the sum out with numbers substituted for letters.

Enigma 21 is also called “Addition: letters for digits”.

[enigma63]

### 4 responses to “Enigma 63: Addition: letters for digits”

1. Jim Randell 8 January 2013 at 9:13 am

The following Python program tries all permutations. It runs in 1.1s.

```from itertools import permutations
from enigma import irange, nconcat, split, printf

ds = set(irange(0, 9))
for (L, B, R, Q, E, S, V) in permutations(ds, 7):
if L == 0 or B == 0: continue
s1 = nconcat(L, B, R, L, Q, Q, R)
s2 = nconcat(L, B, B, B, E, S, L)
s3 = nconcat(L, B, R, E, R, Q, R)
s4 = nconcat(L, B, B, B, E, V, R)
r = str(s1 + s2 + s3 + s4)
if len(r) != 8: continue
(b1, b2, e1, K, v1, M, G, l1) = split(r, int)
if not(b1 == b2 == B): continue
if not(e1 == E and v1 == V and l1 == L): continue
s = set((K, M, G))
if len(s) != 3 or s.intersection((L, B, R, Q, E, S, V)): continue

printf("{s1} + {s2} + {s3} + {s4} = {r}")
```

Solution: The sum is 8308440 + 8333218 + 8302040 + 8333260 = 33276958.

• Jim Randell 8 January 2013 at 9:19 am

Having done a couple of these sums with letters substituted for digits recently I thought it would be fun to write a general solver for them.

The following code takes a straightforward right-to-left approach on the columns of the sum, recursively examining the possibilities for each column. There are three interfaces to it: `_substituted_sum()` is the core of the algorithm, but it assumes its arguments are nicely formed. `substituted_sum()` is a friendlier way to run the algorithm, it makes sure the arguments are valid and fills out sensible default values. `SubstitutedSum()` wraps the previous function as a class so you don’t have to remember the terms in sum itself, and provides some handy functions for reporting solutions.

Gratifyingly this solution runs in 139ms, nearly 10× faster than the previous solution.

```from itertools import permutations
from enigma import uniq

# a substituted sum solver
# terms - list of summands of the sum (each the same length as result)
# result - the result of the sum (sum of the terms)
# digits - set of unallocated digits
# l2d - map from letters to allocated digits
# d2i - map from digits to letters that cannot be allocated to that digit
# n - column we are working on (string index in result)
# carry - carry from the column to the right
# base - base we are working in
# solutions are returned as assigments of letters to digits (the l2d dict)
def _substituted_sum(terms, result, digits, l2d, d2i, n, carry=0, base=10):
# are we done?
if n == 0:
if carry == 0:
l2d.pop('_', None)
yield l2d
return
# move on to the next column
n -= 1
# find unallocated letters in this column
u = list(uniq(t[n] for t in terms if t[n] not in l2d))
# and allocate them from the remaining digits
for ds in permutations(digits, len(u)):
_l2d = l2d.copy()
_l2d.update(zip(u, ds))
# sum the column
(c, r) = divmod(sum(_l2d[t[n]] for t in terms) + carry, base)
# is the result what we expect?
if result[n] in _l2d:
# the digit of the result is already allocated, check it
if _l2d[result[n]] != r: continue
allocated = ds
else:
# the digit in the result is one we haven't come across before
if r not in digits or r in ds: continue
_l2d[result[n]] = r
allocated = ds + (r,)
# check there are no invalid allocations
if any(any(_l2d[x] == d for x in ls if x in _l2d) for (d, ls) in d2i.items()): continue
# try the next column
for r in _substituted_sum(terms, result, digits.difference(allocated), _l2d, d2i, n, c, base):
yield r

# friendly interface to the substituted sum solver
# terms - list of summands in the sum
# result - result of the sum (sum of the terms)
# digits - digits to be allocated (default: 0 - base-1)
# l2d - initial allocation of digits (default: all digits unallocated)
# d2i - invalid allocations (default: leading digits cannot be 0)
# base - base we're working in (default: 10)
def substituted_sum(terms, result, digits=None, l2d=None, d2i=None, base=10):
# fill out the parameters
if digits is None: digits = range(base)
digits = set(digits)
if l2d is None: l2d = dict()
if d2i is None:
d2i = dict()
d2i = ''.join(uniq(x for x in terms + [result]))
# number of columns in sum
n = len(result)
# make sure the terms are the same length as the result
ts = list('_' * (n - len(t)) + t for t in terms)
l2d['_'] = 0
# call the solver
for r in _substituted_sum(ts, result, digits, l2d, d2i, n, 0, base):
yield r

# object interface to the substituted sum solver
class SubstitutedSum(object):

def __init__(self, terms, result, digits=None, l2d=None, d2i=None, base=10):
self.terms = terms
self.result = result
self.digits = digits
self.l2d = l2d
self.d2i = d2i
self.base = base
self.text = ' + '.join(terms) + ' = ' + result

def solve(self):
for r in substituted_sum(self.terms, self.result, digits=self.digits, l2d=self.l2d, d2i=self.d2i, base=self.base):
yield r

def substitute(self, l2d, text):
digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' # up to base 36
return ''.join((digits[l2d[c]] if c in l2d else c) for c in text)

def solution(self, l2d):
# output the assignments in letter order
print(' '.join(k + '=' + str(l2d[k]) for k in sorted(l2d.keys())))
# print the sum with digits substituted in
print(self.substitute(l2d, self.text))

p = SubstitutedSum(['LBRLQQR', 'LBBBESL', 'LBRERQR', 'LBBBEVR'], 'BBEKVMGL')
for s in p.solve():
p.solution(s)
```

I will probably clean this up, add some more documentation and put it in the enigma.py library for future use.

2. Naim Uygun 8 January 2013 at 4:06 pm
```from itertools import permutations
for c in permutations("9876543210"):
L,B,R,Q,E,S,V,K,M,G = c
if int(L)==0:continue
if int(B)==0: continue
if int(B)>3: continue
n1=L+B+R+L+Q+Q+R
n2=L+B+B+B+E+S+L
n3=L+B+R+E+R+Q+R
n4=L+B+B+B+E+V+R
n5=B+B+E+K+V+M+G+L
total=int(n1)+int(n2)+int(n3)+int(n4)
if total != int(n5): continue
print("{0} + {1} + {2} + {3}= {4}".format(n1,n2,n3,n4,total))
input("THE END")
```
3. geoffrounce 1 August 2016 at 9:53 am
```% A solution in MiniZinc
include "globals.mzn";

var 0..9:L;
var 0..9:B;
var 0..9:R;
var 0..9:Q;
var 0..9:E;
var 0..9:S;
var 0..9:V;
var 0..9:K;
var 0..9:M;
var 0..9:G;

constraint alldifferent([L,B,R,Q,E,S,V,K,M,G])
/\ L > 0 /\ B > 0;

constraint
(L*1000000 + B*100000 + R*10000 + L*1000
+ Q*100 + Q*10 + R) +
(L*1000000 + B*100000 + B*10000 + B*1000
+ E*100 + S*10 + L) +
(L*1000000 + B*100000 + R*10000 + E*1000
+ R*100 + Q*10 + R) +
(L*1000000 + B*100000 + B*10000 + B*1000
+ E*100 + V*10 + R) ==
(B*10000000 + B*1000000 + E*100000
+ K*10000 + V*1000 + M*100 + G*10 + L);

solve satisfy;

output ["[L,B,R,Q,E,S,V,K,M,G] = " ++ show (L),show(B),
show(R),show(Q),show(E),show(S),show(V),show(K),
show(M),show(G)];

% Output
% [L,B,R,Q,E,S,V,K,M,G] = 8304216795
% ----------
% Finished in 79msec
% Comment :letter sum is: LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL
% so constructed digit sum is:  8308440 + 8333218 + 8302040 + 8333260 = 33276958
%

```

This site uses Akismet to reduce spam. Learn how your comment data is processed.