JCW2
asked on
Cryptarithmetic
Can you further explain these terms, especially in relation to this cryptarithmetic puzzle?
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."
Information about cryptarithmetic: http://en.wikipedia.org/wi ki/Cryptar ithmetic
Diagram.PNG
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."
Information about cryptarithmetic: http://en.wikipedia.org/wi
Diagram.PNG
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thank you for your help.
http://docs.google.com/viewer?a=v&q=cache:PgguanbKc2gJ:www.cs.ucc.ie/~gprovan/CS3315-FY08/Lectures/Lecture12-CSP-short.pdf+cryptology+%22forward+checking%22+backtracking+mrv+%22least+constraining+value%22&hl=en&gl=us&pid=bl&srcid=ADGEESgRtVJIzpdkHmnuEpGX-hXAk-NQJC0Yb7TzBlc4E0rkTUmPx4IUT5-4gQrRmciHkTnM6Hw2lN8L5_Tqjmam7Fj-jtU64df7lsN4vPsyd-RztWIUb8fPWKBd6iR2OtX1CdhQNk1r&sig=AHIEtbQsfaFLzlWIDJqs2uVguGbtOHNCLQ