Verbal Arithmetic - Solving Cryptarithms

Solving Cryptarithms

Solving a cryptarithm by hand usually involves a mix of deductions and exhaustive tests of possibilities. For instance, the following sequence of deductions solves Dudeney's SEND + MORE = MONEY puzzle above (columns are numbered from right to left):

1. From column 5, M = 1 since it is the only carry-over possible from the sum of two single digit numbers in column 4.
2. Since ( S + M + carry ) > 9 and M = 1 So ( S + carry ) > 8, these leads S is either 8 or 9 (since carry can be 0 or 1).
3. Since there is a carry in column 5, and M = 1, then O = 0
4. Since O = 0 there cannot be a carry in column 4 (otherwise N would also be 0 in column 3) so S = 9.
5. If there were no carry in column 3 then E = N, which is impossible. Therefore there is a carry and N = E + 1.
6. If there were no carry in column 2, then ( N + R ) mod 10 = E, and N = E + 1, so ( E + 1 + R ) mod 10 = E which means ( 1 + R ) mod 10 = 0, so R = 9. But S = 9, so there must be a carry in column 2 so R = 8.
7. To produce a carry in column 2, we must have D + E = 10 + Y.
8. Y is at least 2 so D + E is at least 12.
9. The only two pairs of available numbers that sum to at least 12 are (5,7) and (6,7) so either E = 7 or D = 7.
10. Since N = E + 1, E can't be 7 because then N = 8 = R so D = 7.
11. E can't be 6 because then N = 7 = D so E = 5 and N = 6.
12. D + E = 12 so Y = 2.

The use of modular arithmetic often helps. For example, use of mod-10 arithmetic allows the columns of an addition problem to be treated as simultaneous equations, while the use of mod-2 arithmetic allows inferences based on the parity of the variables.

In computer science, cryptarithms provide good examples to illustrate the brute force method, and algorithms that generate all permutations of m choices from n possibilities. For example, the Dudeney puzzle above can be solved by testing all assignments of eight values among the digits 0 to 9 to the eight letters S,E,N,D,M,O,R,Y, giving 1,814,400 possibilities. They provide also good examples for backtracking paradigm of algorithm design.