Page 58 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes Allocate decimal digit to all the letters in such a manner that the answer to the problem is correct
to the same letter appears more than once, it must be allocated the same digit each time. No two
different letters may be allocated the same digit. Consider the below given crypt arithmetic
problem.
SEND
+ MORE
-----------
MONEY
-----------

Constraints:
1. No two digit can be allocated to same letter.
2. Only single digit number can be allocate to a letter.
3. No two letters can be allocated same digit.
4. Assumption can be prepared at different levels such that they do not oppose each other.
5. The problem can be divided into secured constraints. A constraint satisfaction strategy
may be used.
6. Any of search techniques may be utilized.
7. Backtracking may be performed as applicable us applied search techniques.
8. Rule of arithmetic may be followed.
Initial state of problem.

D = ?
E = ?
Y = ?
N = ?
R = ?
O = ?
S = ?
M = ?
C1 = ?

C2 = ?
C1, C2, C3 stands for the carry variables respectively.
Goal State: The digits to the letters must be allocated in such a manner so that the sum is satisfied.
Solution Process:
We are following the depth-first technique to solve the problem.
1. Initial guess m=1 since the sum of two single digits can generate at most a carry ‘1’.

2. When n=1 o=0 or 1 since the largest single digit number added to m=1 can produce the
sum of either 0 or 1 depend on the carry obtained from the carry sum. By this we say that
o=0 because m is already 1 hence we cannot assign same digit another letter (rule no.)

3. We have m=1 and o=0 to get o=0 we have s=8 or 9, again based on the carry obtained from
the earlier sum.

52 LOVELY PROFESSIONAL UNIVERSITY