CSP and SEND+MORE=MONEY

Constraint satisfaction problem (CSP)

A CSP consists of a set of variables, a domain of values for each variable, and constraints on the values the variables may take together. A solution assigns a value to every variable so that all constraints are satisfied. Examples: map colouring, 8-queens, cryptarithmetic.

SEND + MORE = MONEY

• Variables: S, E, N, D, M, O, R, Y; domain 0-9; all different; S and M non-zero.

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

Column equations (c1, c2, c3 = carries; c4 = M):

1. D + E = Y + 10·c1
2. N + R + c1 = E + 10·c2
3. E + O + c2 = N + 10·c3
4. S + M + c3 = O + 10·M

Solving

1. M = 1: the sum of two 4-digit numbers is less than 20000, so the carry into the fifth digit is 1.
2. Column 4: S + 1 + c3 = O + 10, so O = S + c3 − 9 ≤ 1 (since S ≤ 9). O ≠ 1 (M = 1), so O = 0 and S = 9 − c3, that is, S = 9 (c3 = 0) or S = 8 (c3 = 1).
3. Column 3: E + 0 + c2 = N + 10·c3. If c3 = 0, then since E ≠ N we need c2 = 1 and N = E + 1. If c3 = 1, we would need E + c2 ≥ 10, which forces E = 9, c2 = 1 and N = 0 = O (clash). So c3 = 0, S = 9, c2 = 1, N = E + 1.
4. Column 2: N + R + c1 = E + 10 ⇒ (E + 1) + R + c1 = E + 10 ⇒ R = 9 − c1. R ≠ 9 (S = 9), so c1 = 1 and R = 8.
5. Column 1: D + E = Y + 10 (c1 = 1). Remaining digits: {2, 3, 4, 5, 6, 7}, with N = E + 1 and D + E ≥ 10.

Hence E = 5, N = 6, D = 7, Y = 2 (all different from the others).

Verification

      9 5 6 7
    + 1 0 8 5
    ---------
    1 0 6 5 2

9567 + 1085 = 10652 ✓ (this is the only solution, confirmed by an exhaustive computer search).

Answer: S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2.