--- title: "CSP and SEND+MORE=MONEY" subject: "Artificial Intelligence" chapter: 2 key: "semester_6/artificial_intelligence:csp-send-more-money" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/csp-send-more-money site: BCT Engineering --- # CSP and SEND+MORE=MONEY Artificial Intelligence · Chapter 2: Problem Solving - Asked in: 2072 Asoj, 1+6 marks - Video: [CryptArithmetic Problem in Artificial Intelligence | SEND + MORE = MONEY Solution | Pratiksha Jain](https://www.youtube.com/watch?v=jWvWOUb0hOI) — Techie - Pratiksha Jain - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/csp-send-more-money - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-2 ## Question What do you understand by constraint satisfaction problem? Solve the following crypt-arithmetic problem: SEND + MORE = MONEY. ## Short answer A CSP has variables, domains, and constraints; a solution assigns values satisfying all constraints. For SEND+MORE=MONEY, solving carries gives M=1, O=0, S=9, R=8, E=5, N=6, D=7, Y=2; 9567+1085=10652. ## Answer #### 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. ```text 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. | E | N | D needed (≥ 10 − E) | D + E − 10 = Y | Result | |---|---|---|---|---| | 2 | 3 | ≥ 8 | none available | fail | | 3 | 4 | 7 | Y = 0 (= O) | fail | | 4 | 5 | 6 or 7 | Y = 0 or 1 | fail (Y clashes with O or M) | | **5** | **6** | **7** | **Y = 2** | **success** | | 6 | 7 | 4 or 5 | Y = 0 or 1 | fail | | 7 | 8 | - | N = 8 = R | fail | Hence E = 5, N = 6, D = 7, Y = 2 (all different from the others). #### Verification ```text 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.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is a solution to a CSP? A. An assignment of a value to every variable satisfying all constraints B. A single variable assignment C. The shortest path D. The largest domain Answer: A. Every variable gets a value so that all constraints hold. (Key point: CSP definition) 2. Why is M = 1 in SEND + MORE = MONEY? A. M is the first letter B. The sum of two 4-digit numbers is under 20000, so the fifth-digit carry is 1 C. 1 is the smallest digit D. S = 1 Answer: B. The carry into the fifth digit can only be 1. (Key point: M = 1) 3. Why is O = 0? A. O is always zero in puzzles B. N = 0 C. S + 1 + c3 = O + 10 forces O <= 1, and O cannot equal M = 1 D. R = 0 Answer: C. Column 4 gives O = S + c3 - 9 <= 1, and O differs from M. (Key point: O = 0) 4. What is the solution? A. 9576 + 1085 = 10661 B. 9567 + 1058 = 10625 C. 8567 + 1085 = 9652 D. 9567 + 1085 = 10652 Answer: D. S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2. (Key point: Final answer) ## Related in Artificial Intelligence - [CSP and SWIM+WEAR=RELAX](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Acsp-swim-wear-relax) — Artificial Intelligence, chapter 2 - [AI, Turing test, CSP examples](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aturing-test-pass-csp-examples) — Artificial Intelligence, chapter 1 - [Problem space; BASE+BALL=GAMES](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aproblem-space-base-ball-games) — Artificial Intelligence, chapter 2 - [Cryptarithmetic LOGIC+LOGIC=PROLOG](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Acryptarithmetic-logic-prolog) — Artificial Intelligence, chapter 2, asked 3× - [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 other subjects - [Russell: wisdom more necessary with knowledge](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Arussell-wisdom-more-necessary) — Communication English, chapter 2, asked 2× - [Making programs more readable](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Areadable-programs) — Instrumentation II, chapter 9 - [Initial value problem y''−4y'+3y](https://www.bctengineer.com/question.md?key=semester_2%2Fmathematics%3Ainitial-value-problem-y-4y) — Mathematics, chapter 4, asked 3× - [Initial value problem y''+2y'+5y=0](https://www.bctengineer.com/question.md?key=semester_2%2Fmathematics%3Ainitial-value-problem-y-2y) — Mathematics, chapter 4, asked 3×