JCW2

asked on

# Cryptarythmatic with Forward Checking, MRV, and Least Constraining Value

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

In a cryptarythmetic problem, each of the letters are unknown numbers; usually different ones.

The C variables are carries, so one mathematical sentence that occurs will be

O + O = R * X_1, where O and R are between 0 and 9 inclusive, and X_1 has the domain { 0, 1 }.

I'm trying to understand how to approach this problem with "backtracking with forward checking and the MRV and least-constraining-value heuristics."

In a cryptarythmetic problem, each of the letters are unknown numbers; usually different ones.

The C variables are carries, so one mathematical sentence that occurs will be

O + O = R * X_1, where O and R are between 0 and 9 inclusive, and X_1 has the domain { 0, 1 }.

I'm trying to understand how to approach this problem with "backtracking with forward checking and the MRV and least-constraining-value heuristics."

ASKER CERTIFIED SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**ASKER

I've forgotten the diagram:

Diagram.PNG

Diagram.PNG

SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**ASKER

A description of how I would solve this cryptarythmatic problem without any other instructions:

Assign 7 to T.

Therefore, C_3 = 1, F = 1, and O = 4.

Assign 3 to W.

Therefore, U = 6 and C_2 = 0.

O + O = R = 8, with C_1 = 0.

T was revised from 9 to 7.

In all, T = 7, W = 3,

O = 4, F = 1,

U = 6, R = 8,

X_1 = 0, X_2 = 0, and X_3 = 1.

Assign 7 to T.

Therefore, C_3 = 1, F = 1, and O = 4.

Assign 3 to W.

Therefore, U = 6 and C_2 = 0.

O + O = R = 8, with C_1 = 0.

T was revised from 9 to 7.

In all, T = 7, W = 3,

O = 4, F = 1,

U = 6, R = 8,

X_1 = 0, X_2 = 0, and X_3 = 1.

ASKER

What is your feedback?

ASKER

This question is continued at http://www.experts-exchange.com/Programming/Algorithms/Q_26613235.html .

ASKER

Thank you for your help.

Reason for B grade:

Commenter (Ozo) did not respond to my message. Even something like "I don't know" would have been better than nothing.

Reason for B grade:

Commenter (Ozo) did not respond to my message. Even something like "I don't know" would have been better than nothing.

ASKER

Forward checking: "Whenever a variable X is assigned, the forward-checking process establishes arc-consistency for it: for each unassigned variable Y that is connected to X by a constraint, delete from Y's domain any value that is inconsistent with the value chosen for X."

MRV: Most constrained variable. "It also has been called the 'most constrained variable' or 'fail-first' heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. If some variable X has no legal values left, the MRV heuristic will select X and failure will be detected immediately- avoiding pointless searches through other variables."

Least-constraining-value: "Once a variable has been selected, the algorithm must decide on the order in which to examine its values. For this, the least-constraining-value heuristic can be effective in some cases. It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph."