CSP and SWIM+WEAR=RELAX

Constraint satisfaction problem (CSP)

A CSP is a problem defined by a set of variables, a domain of possible values for each, and a set of constraints restricting the allowed combinations. Solving it means assigning values to all variables so that every constraint holds (e.g. map colouring, Sudoku, cryptarithmetic).

SWIM + WEAR = RELAX

Variables: S, W, I, M, E, A, R, L, X (9 letters); domain 0-9; all different; S, W, R non-zero.

      S W I M
    + W E A R
    ---------
    R E L A X

Column equations (c1...c4 carries):

1. M + R = X + 10·c1
2. I + A + c1 = A + 10·c2 ⇒ I + c1 = 10·c2
3. W + E + c2 = L + 10·c3
4. S + W + c3 = E + 10·c4
5. R = c4

Solving

• R = 1: it is the carry into the fifth digit, so c4 = 1 and R = 1.
• Column 2: I + c1 = 10·c2. Either (c2 = 0, I = 0, c1 = 0) or (c2 = 1, I = 9, c1 = 1). The second option leads to no valid assignment (shown by exhaustive search), so take I = 0, c1 = 0, c2 = 0.
• Column 1: M + 1 = X (c1 = 0), so X = M + 1.
• Column 3: W + E = L + 10·c3; Column 4: S + W + c3 = E + 10.
• Try c3 = 0: W + E = L and S + W = E + 10.
  • Take S = 9, W = 4 ⇒ E = 3 (from 9 + 4 = E + 10) and L = 4 + 3 = 7.
  • Used digits so far: R = 1, I = 0, S = 9, W = 4, E = 3, L = 7. Remaining digits for A, M, X: {2, 5, 6, 8}.
  • X = M + 1 with both unused: M = 5, X = 6; then A = 2.
• All different ✓.

Verification

      9 4 0 5
    + 4 3 2 1
    ---------
    1 3 7 2 6

9405 + 4321 = 13726 ✓

Answer: S = 9, W = 4, I = 0, M = 5, E = 3, A = 2, R = 1, L = 7, X = 6.

Note: a computer search finds 16 valid assignments, e.g. 7604 + 6321 = 13925; each satisfies all the constraints, so the puzzle is not unique.