Skip to main content

Cryptarithmetic LOGIC+LOGIC=PROLOG

Short answer

Solve as a constraint satisfaction problem: assign unique digits 0-9 to letters, with L and P non-zero, and satisfy column-wise addition with carries. Constraint propagation yields the unique solution L=9, O=0, G=4, I=5, C=2, P=1, R=8 (90452+90452=180904).

Solve the following crypto-arithmetic problem, where different letters denote different integers and identical letters denote the same integer: LOGIC + LOGIC = PROLOG. Show all the steps of solving it through constraint satisfaction problem.

A cryptarithmetic puzzle is a constraint satisfaction problem (CSP):

  • Variables: L, O, G, I, C, P, R (7 letters).
  • Domain: digits 0-9.
  • Constraints: (1) all letters have different digits; (2) leading letters L and P are not 0; (3) the column-wise addition is correct with carries.
      L O G I C
    + L O G I C
    -----------
    P R O L O G

Column equations (right to left, c1...c5 are carries)

  1. C + C = G + 10·c1
  2. I + I + c1 = O + 10·c2
  3. G + G + c2 = L + 10·c3
  4. O + O + c3 = O + 10·c4 ⇒ O + c3 = 10·c4
  5. L + L + c4 = R + 10·c5
  6. P = c5

Solving

  • P = 1: the sum of two 5-digit numbers has at most 6 digits, so the carry c5 is 1 and P = 1.
  • From (5), L + L + c4 = R + 10 ⇒ L ≥ 5.
  • From (4): either c4 = 0 (then O = 0, c3 = 0) or c4 = 1 (then c3 = 1, O = 9).

Case A: c4 = 1, O = 9, c3 = 1.

  • (2): 2I + c1 = 9 + 10·c2; the left side must be odd, so c1 = 1. Then I = 4 (c2 = 0) or I = 9 (not allowed, O = 9). So I = 4, c2 = 0.
  • (1): 2C = G + 10 ⇒ C ∈ {5, 6, 8}, G ∈ {0, 2, 6} (C = 7 gives G = 4 = I, C = 9 clashes with O).
  • (3): 2G + 0 = L + 10 ⇒ G = 0 gives L = −10; G = 2 gives L = −6; G = 6 gives L = 2, but L ≥ 5. Contradiction. Case A is impossible.

Case B: c4 = 0, O = 0, c3 = 0.

  • (2): 2I + c1 = 10·c2. Since O = 0, I ≠ 0, so c2 = 1 and 2I + c1 = 10 ⇒ I = 5, c1 = 0.
  • (1): c1 = 0 ⇒ G = 2C (C ≤ 4).
  • (3): 2G + 1 = L (c3 = 0) ⇒ L = 4C + 1.
  • (5): 2L = R + 10 (c4 = 0, c5 = 1).
  • Try C: C = 1 ⇒ G = 2, L = 5 = I (clash). C = 2 ⇒ G = 4, L = 9, R = 2·9 − 10 = 8. C = 3 ⇒ G = 6, L = 13 (not a digit). C = 4 ⇒ L = 17 (not a digit).

All letters get different digits: L = 9, O = 0, G = 4, I = 5, C = 2, P = 1, R = 8.

Verification

      9 0 4 5 2
    + 9 0 4 5 2
    -----------
    1 8 0 9 0 4

90452 × 2 = 180904 = PROLOG ✓ (an exhaustive computer check confirms this is the only solution).

Answer: L = 9, O = 0, G = 4, I = 5, C = 2, P = 1, R = 8 (90452 + 90452 = 180904).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Artificial Intelligence chapter 2 questions →