Page 61 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 4: Heuristic Search Techniques

Notes
Example: Given Problem:
CROSS

+ROADS
——————
DANGER
——————
Constraints & Production Rules:

Same rules as used for the previous problem.
Initial State of Problem:
C = ?
R = ?

D = ?
A = ?
O = ?
N = ?

G = ?
S = ?
E = ?
C1 = ?

C2 = ?
C3 = ?
C4 = ?
Goal State:

The Digits to the Letters should be allocated in such a way. So that, the sum is satisfied.
Solution Process:
Again, I am following depth-first search technique to solve the problem.
1. Initial Guess, D=1. Since the sum of two single digits can, at most, generate a carry ‘1’.

2. Now, we begin guessing the digits and try to solve the problem. The supposing and the
consequent effect of it is exposed in the form of a tree below.

LOVELY PROFESSIONAL UNIVERSITY 55