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."

ASKER CERTIFIED SOLUTION

ozo

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds. No credit card required.

See answer

JCW2

ASKER

Backtracking: "The term backtracking search is used for a depth first search that chooses values for one variable at a time and backtracks when a variable has no legal moves left to assign."

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."

SOLUTION

ozo

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds. No credit card required.

See answer

JCW2

ASKER

I've forgotten the diagram:
Diagram.PNG

SOLUTION

ozo

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds. No credit card required.

See answer

JCW2

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.

JCW2

ASKER

What is your feedback?

JCW2

ASKER

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

JCW2

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.