Problem space; BASE+BALL=GAMES

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.

      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

      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.