--- title: "Cryptarithmetic LOGIC+LOGIC=PROLOG" subject: "Artificial Intelligence" chapter: 2 key: "semester_6/artificial_intelligence:cryptarithmetic-logic-prolog" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/cryptarithmetic-logic-prolog site: BCT Engineering --- # Cryptarithmetic LOGIC+LOGIC=PROLOG Artificial Intelligence · Chapter 2: Problem Solving - Asked in: 2069 Bhadra, 7 marks; 2072 Magh, 3+4 marks (asked 2 times) - Video: [#Cryptoarithmatic LOGIC+LOGIC = PROLOG in Artificial Intelligence - Shiva Gyawali](https://www.youtube.com/watch?v=6MtDpBYnPU4) — Shiva Gyawali - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/cryptarithmetic-logic-prolog - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-2 ## Question 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. ## 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). ## Answer 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. ```text 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 ```text 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). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why is P = 1 in LOGIC + LOGIC = PROLOG? A. P is the smallest letter B. 1 is the only unused digit C. Two 5-digit numbers sum to at most 6 digits, so the leading carry is 1 D. L equals 1 Answer: C. The leftmost digit of the 6-digit result is only a carry, which can be at most 1, and P is non-zero. (Key point: Why P = 1) 2. From O + O + c3 = O + 10*c4, what follows? A. O = 5 always B. c4 must be 2 C. O = c3 + 1 D. O + c3 = 10*c4, so either O = 0 (c3 = 0) or O = 9 (c3 = 1) Answer: D. Cancelling O leaves O + c3 = 10*c4, giving O = 0 with no carry or O = 9 with c3 = 1. (Key point: Column 4 equation) 3. Why is the case O = 9 impossible? A. It leads to G = 6 and L = 2, but L must be at least 5, a contradiction B. 9 is not a digit C. P would be 9 D. It makes I = 0 Answer: A. With O = 9, I = 4 and the remaining options force L = 2, contradicting L >= 5. (Key point: Eliminating case A) 4. What is the final solution? A. 91452 + 91452 = 182904 B. 90452 + 90452 = 180904 C. 90542 + 90542 = 181084 D. 80452 + 80452 = 160904 Answer: B. L=9, O=0, G=4, I=5, C=2, P=1, R=8 gives 90452 x 2 = 180904. (Key point: Final solution) ## Close variants set in other exams - [Cryptarithmetic RIGHT+RIGHT=WRONG](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Acryptarithmetic-right-right-wrong) — Artificial Intelligence, chapter 2, asked 3× ## Related in Artificial Intelligence - [Cryptarithmetic WRONG+WRONG=RIGHT](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Acryptarithmetic-wrong-wrong-right) — Artificial Intelligence, chapter 2 - [CSP and SWIM+WEAR=RELAX](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Acsp-swim-wear-relax) — Artificial Intelligence, chapter 2 - [Cryptarithmetic ONE+ONE+TWO=FOUR](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Acryptarithmetic-one-one-two-four) — Artificial Intelligence, chapter 2, asked 2× ## Related in other subjects - [Three students solving a problem](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Athree-students-solve-problem) — Probability and Statistics, chapter 1 - [Creative problem solving and brainstorming](https://www.bctengineer.com/question.md?key=semester_6%2Fmachine_design_i%3Acreative-problem-solving-brainstorming) — Machine Design I, chapter 4