Question 3 of 9: Programming — Crypto-Arithmetic Puzzle

Question 3: Programming — Crypto-Arithmetic Puzzle (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Two words $x$, $y$ and a sum word $z$ (up to 4 letters each in practice, to admit the paper's own SEND+MORE=MONEY example), read as character arrays; digits 0–9 must be assigned one-to-one to the distinct letters appearing across all three words, with no leading letter assigned 0.

Find. One digit assignment for which $x+y=z$ holds when each word is read as a decimal number under that assignment.

Approach. Collect the distinct letters (at most 10, since there are only 10 digits to assign), then try digit assignments with a backtracking search that tries one letter at a time and immediately abandons a partial assignment once a digit repeats or a leading letter is set to 0 — this realizes the hint's "nested loop per letter" as a recursion whose depth equals the number of distinct letters, avoiding one hand-written loop per puzzle.

1. Write the backtracking search. With at most 10 distinct letters the search tree has at most $10!=3{,}628{,}800$ leaves, and pruning on the first repeated digit or leading zero cuts this drastically in practice — well within an exam-scale program's running time.

   #include <stdio.h>
   #include <string.h>
   
   #define MAXLETTERS 10
   
   char letters[MAXLETTERS];
   int  nletters;
   int  digit_of[26];      /* digit_of[letter-'A'], -1 if unassigned */
   int  used[10];          /* used[d] = 1 if digit d already assigned */
   char wordX[5], wordY[5], wordZ[6];   /* up to 4 letters + terminator */
   
   long word_value(const char *w)
   {
       long v = 0;
       for (; *w; w++) v = v * 10 + digit_of[*w - 'A'];
       return v;
   }
   
   int is_leading(char c)
   {
       return c == wordX[0] || c == wordY[0] || c == wordZ[0];
   }
   
   int solve(int idx)
   {
       if (idx == nletters)
           return word_value(wordX) + word_value(wordY) == word_value(wordZ);
   
       char c = letters[idx];
       int d;
       for (d = 0; d <= 9; d++) {
           if (used[d]) continue;
           if (d == 0 && is_leading(c)) continue;   /* no leading zero */
           used[d] = 1; digit_of[c - 'A'] = d;
           if (solve(idx + 1)) return 1;             /* found -> propagate success */
           used[d] = 0; digit_of[c - 'A'] = -1;       /* backtrack */
       }
       return 0;
   }
   
   void collect_letters(const char *w)
   {
       for (; *w; w++)
           if (digit_of[*w - 'A'] == -2) {           /* -2 = "not yet seen" sentinel */
               digit_of[*w - 'A'] = -1;
               letters[nletters++] = *w;
           }
   }
   
   int main(void)
   {
       int i;
       printf("Enter puzzle as x y z (e.g. SEND MORE MONEY): ");
       scanf("%4s %4s %5s", wordX, wordY, wordZ);
   
       for (i = 0; i < 26; i++) digit_of[i] = -2;
       nletters = 0;
       collect_letters(wordX); collect_letters(wordY); collect_letters(wordZ);
   
       if (solve(0)) {
           printf("Solution:");
           for (i = 0; i < nletters; i++)
               printf(" %c=%d", letters[i], digit_of[letters[i] - 'A']);
           printf("\n");
       } else {
           printf("No solution exists.\n");
       }
       return 0;
   }

2. Trace it on the paper's own puzzle, SEND + MORE = MONEY. The eight distinct letters are S,E,N,D,M,O,R,Y. Brute-force search over all leading-zero-respecting, all-different digit assignments finds exactly one assignment that satisfies the equation: $$\text{SEND}=9567,\quad \text{MORE}=1085,\quad \text{MONEY}=10652, \qquad 9567+1085=10652$$ $$\boxed{D{=}7,\ E{=}5,\ M{=}1,\ N{=}6,\ O{=}0,\ R{=}8,\ S{=}9,\ Y{=}2}$$ matching the value given in the question exactly, and the exhaustive search confirms it is the unique solution under the stated rules.