Constraint Satisfaction Problem2.

2. Given Problem :

  C ROSS

+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 assigned in such a manner. So that , the sum is satisfied.

Solution Process :

 

Again , I am following depth – first search method to solve the problem.

1. Initial Guess , D=1. Because the sum of two single digits can , at most , generate a carry ‘1’.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

At Step(2) we have assigned a single digit to every letter in accordance with the constraints and production rules.

Now by backtracking, we find the different digits assigned to different letters and hence reach the solution state.

Solution State:-

C = 9
N = 8
G = 7
A = 5
O = 2
E = 4
D = 1
R = 6
S = 3
C1 = 0
C2 = 0
C3 = 0
C4 = 0

              C4(0) C3 C2(0) C1(0)
              C9 R(6) O(2) S(3) S(3)
           + R6 O(2) A(5) D(1) S(3)
    D(1) A(5) N(8) G(7) E(4) R(6)