Solve the cryptarithmetic problem in Figure 6.2 by hand, using the strategy of backtracking with forward checking and the MRV and least-constraining-value heuristics.

Login

+2 votes

0 votes

Higher order constraint involves three or more variables. A familiar example is provided by cryptarithmetic puzzles. It is usual to insist that each letter in cryptarithmetic puzzles represents a different digit.

TWO

TWO

-------

+ FOUR

TWO

TWO

-------

+ FOUR

0 votes

(broken image)

Choose the variable by the help of Minimum Remaining Value Heuristic and assign the value for chosen variable by the help of Least Constraining Value heuristic method is as shown below constraints:

(broken image)

According to the given figure, is consider that the main variable is F, T, U, W, R, O and (broken image) represent the auxiliary variables that depend on the assigned values.

The auxiliary or caries variable adopts the value zero and one. Another caries variable such as F, T can’t adopt the zero value.

Therefore, the backtracking, forwarding searching algorithm working as follows steps:

Choose the variable by the help of Minimum Remaining Value Heuristic and assign the value for chosen variable by the help of Least Constraining Value heuristic method is as shown below constraints:

(broken image)

According to the given figure, is consider that the main variable is F, T, U, W, R, O and (broken image) represent the auxiliary variables that depend on the assigned values.

The auxiliary or caries variable adopts the value zero and one. Another caries variable such as F, T can’t adopt the zero value.

Therefore, the backtracking, forwarding searching algorithm working as follows steps:

0 votes

**Step 1:** Consider the constraints variable F and it shows that it can only take the value 1. Thus, the variable (broken image) can caries 0 or 1 and according to condition (broken image). Therefore, (broken image)=1.

(broken image)

**Step 2:** Now, after F = 1, is consider that the rest variable U, W, R, O may have the value 0 to 9.

Thus, the value T is not to be zero and one, so T may be one of {2, 3, 4, 5, 6, 7, 8, 9}.

According to the MRV heuristic constraints the state is:

(broken image)

Therefore, consider that the assigning values two, three, four values to T, then no possible values for O. If assign the 5 to T, then the single value of O is zero. Now, consider the rest value {6, 7, 8} value to assign the value to T. Here, applies the least constraining heuristic approach to choose the value for T.

Therefore, the value of T is 6.

(broken image)

**Step 3**: According to the step 2 (broken image). Therefore, the (broken image) caries either 0 or 1. Thus, the value of O is may be {2,3}. Now, applies the applies the least constraining heuristic approach to choose the value for O.

Hence, the value of O is 2.

(broken image)

**Step 4:** Now, find the value for constraints R. Consider the statement:

(broken image)

Consider that (broken image) either 0 or 1. So, (broken image) is zero because R is not to be negative.

Hence, R = 4.

(broken image)