So, how to solve TWOplusTWO=FOUR
constraints are
ALLDIFF
the four constratints regarding the carry over digits (if applicable)
and no leading zeros
They ask us to solve the cryptarithmic puzzle in image 6.2.
My thoughts are this:
choose the first variable as the one with the highest degree of constraints (thus variable O)
choose the value to insert into this variable by selecting the variable which is least constraining.
our goal here is to find the first solution, not all solutions.
thus backtracking means that: when I get to a chosen variable that has no legal values, I must backtrack to the previous variable and select a different value for it and then try the next variable again.
forward checking means that: when I fill a variable with value, I remove any illegal values from the next variables. If any of these variables left then have an empty domain, there exists no solution - thus we backtrack again.
Now my question:
Im setting up a grid like on page 218 of R&N. Ive got the six variables, which will all have an initial domain of {0 1 2 3 4 5 6 7 8 9}. Step one needs to select a value- how? -> the only method of obtaining the least constraining value is to set up this table / grid and work out the effects of all 9 assignments of the first variable. Thus a) I take assignment of value1 to variable O. b) I check the constraints and update the domains of the other variables.
Seems like a hell of a job to check everything. PLUS.. how far do you go. I give an example.
I take into account that I am only summing two rows, so the carry over wont be more than 1. (in order to get a carry over of 2, we need to get above 20 - which you cant becuase 9+9+1 = 19 = max;
let take for example: setting O = 2, this results in R being 4 automatically (the only value for the domain of R). This means that T + T must give you 2 one some way. There are two ways - with and without a carry digits. Without the carry digit, you can only get T + T = 2 by having T = 1. With the carry digit you need to find something that adds to 11 first, then we add the carry digit and get to 12. Thus T + T = 2 carry 1. However, I can find no such value (nothing equal to each other, and added to each other will give 11 because 11 mod 2 <> 0).
So okay if O=2, then R = 4 and T = 1 OR t = 6 (6+6=12 ; thus 2 carry 1)
HOWEVER, T cannot be 1. Why? Because if T were 1 then 1+1=2 but we would have no carry digit to the next column, THUS we would have F = 0 which is not allowed (not allowed to have leading zeros).
Are we suppose to go at it in this way? This means that for variable O we check all possible assignments to get the least constraining value. And I'm guessing there might be two values which constrain other equally.. what then (i guess we take the one with the highest degree of constraints as the tie breaker). (keeping in ming that if one of the domains become empty, the solution cannot be found, and we simply skip that assignment)
your thoughts and input appreciated.
Danie van Eeden
------------------------
but please, if you have any comments - do post. it helps to see another perspective.