--- title: "Problem space; BASE+BALL=GAMES" subject: "Artificial Intelligence" chapter: 2 key: "semester_6/artificial_intelligence:problem-space-base-ball-games" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/problem-space-base-ball-games site: BCT Engineering --- # Problem space; BASE+BALL=GAMES Artificial Intelligence · Chapter 2: Problem Solving - Asked in: 2075 Baisakh, 2+6 marks - Video: [Artificial Intelligence | Tutorial #2 | Crypt Arithmetic Problem](https://www.youtube.com/watch?v=2E-oGMJWUjQ) — RANJI RAJ - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/problem-space-base-ball-games - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-2 ## Question What is problem space? Solve the following crypto arithmetic problem by showing all the steps: BASE + BALL = GAMES. ## Short answer A problem space is all states, operators, initial and goal states; search explores it. For BASE+BALL=GAMES, G=1, L=5, B=7, A=4, M=9, E=3, S=8; 7483+7455=14938. ## Answer #### Problem space A **problem space** is the complete environment in which a search takes place. It consists of the set of all possible **states** that can arise, the **operators** that move from one state to another, the **initial state** and the **goal state(s)**. Searching means exploring this space for a path from the initial state to a goal. (It is also called the *state space*.) For the puzzle below, a state is a partial assignment of digits to letters, an operator is "assign an unused digit to a letter", and the goal is a full assignment that makes the sum correct. #### BASE + BALL = GAMES Variables B, A, S, E, L, G, M; domain 0-9; all different; B, G non-zero. ```text B A S E + B A L L --------- G A M E S ``` Column equations (c1...c4 carries): 1. E + L = S + 10·c1 2. S + L + c1 = E + 10·c2 3. A + A + c2 = M + 10·c3 4. B + B + c3 = A + 10·c4 5. G = c4 #### Solving 1. **G = 1** (carry out of the leftmost column; c4 = 1). 2. Substitute S from (1) into (2): E + L − 10c1 + L + c1 = E + 10c2 ⇒ **2L = 9c1 + 10c2**. The left side is even, so c1 = 0 and 2L = 10c2. If c2 = 0 then L = 0 and S = E (clash), so **c2 = 1, L = 5, c1 = 0**, and S = E + 5, so E ∈ {0, ..., 4}. 3. Column 3: 2A + 1 = M + 10c3. Column 4: 2B + c3 = A + 10. - c3 = 0: A = 2B − 10 is even, B ≥ 5. B = 5 gives A = 0, M = 1 (= G, clash). B = 6 gives A = 2, M = 5 (= L, clash). **B = 7 gives A = 4, M = 9** ✓. B = 8 gives M = 13, B = 9 gives M = 17 (not digits). - c3 = 1: A = 2B − 9 and M = 2A − 9 (so A ≥ 5). B = 5 gives A = 1 (= G), B = 6 gives A = 3 (M = −3, not a digit), B = 7 gives A = 5 (= L), B = 8 gives A = 7, M = 5 (= L), B = 9 gives A = 9 (= B): all fail. 4. So B = 7, A = 4, M = 9, G = 1, L = 5. Unused digits: {0, 2, 3, 6, 8}. With S = E + 5: E = 0 gives S = 5 (clash), E = 2 gives S = 7 (clash), **E = 3 gives S = 8** ✓. #### Verification ```text 7 4 8 3 + 7 4 5 5 --------- 1 4 9 3 8 ``` 7483 + 7455 = 14938 ✓ (unique solution). **Answer: B = 7, A = 4, S = 8, E = 3, L = 5, G = 1, M = 9.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which set of components makes up a problem space? A. States, operators, initial state and goal state(s) B. Only the heuristic function and the goal C. Only the list of all solutions D. Variables and their carries only Answer: A. A problem space is the set of all possible states, the operators that move between them, the initial state and the goal state(s). (Key point: Problem space) 2. In BASE + BALL = GAMES, why is G = 1? A. Because G is the smallest digit B. Because the sum of two 4-digit numbers can give at most a carry of 1 into the fifth digit, and G is non-zero C. Because B = 1 D. Because E + L must equal 1 Answer: B. The 5th digit G is only the carry out of the leftmost column, which is at most 1, and G cannot be 0. (Key point: Leftmost carry) 3. Substituting S from column 1 into column 2 gives 2L = 9c1 + 10c2. What follows? A. c1 = 1 because the right side must be odd B. c1 = 0 because the right side must be even, so 2L = 10c2 and L = 5 (with c2 = 1) C. L = 0 and c2 = 0 D. L = 9 and c1 = 1 Answer: B. 2L is even, so 9c1 must be even, giving c1 = 0. c2 = 0 would give L = 0 and S = E (a clash), so c2 = 1 and L = 5. (Key point: Column 2 deduction) 4. Which assignment is the final solution? A. B=7, A=4, S=5, E=3, L=8, G=1, M=9 B. B=7, A=4, S=8, E=3, L=5, G=1, M=9 C. B=6, A=2, S=8, E=3, L=5, G=1, M=5 D. B=7, A=4, S=7, E=2, L=5, G=1, M=9 Answer: B. 7483 + 7455 = 14938, which fits B=7, A=4, S=8, E=3, L=5, G=1, M=9. (Key point: Final solution) ## Related in Artificial Intelligence - [Well defined problem, state-space search](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Awell-defined-problem-state-space) — 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× - [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 ## Related in other subjects - [Column slab base: sketch and design steps](https://www.bctengineer.com/question.md?key=semester_6%2Fdesign_of_steel_and_timber_structure%3Aslab-base-procedure-sketch) — Design of Steel and Timber Structure, chapter 6, asked 3× - [Space switch and two-stage S-T drawbacks](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aspace-switch-two-stage-st) — Telecommunications, chapter 4 - [Solve TOH for 3 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-3-disks-steps) — Data Structure and Algorithm, chapter 5, asked 2× - [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×