csp convert to binary

[matanhol]

Hi,

I'm using the library for solving cryptarithmetic problems ("SEND"+"MORE"="MONEY" where each letter stands for some digits) by converting it to CSP
then I use convert_to_binary to convert the constraints to binary ones, thus speeding the backtracking
I tried the usual "SEND" + "MORE" = "MONEY", "TWO"+"TWO"="FOUR", it works great with and without binarization
but when
"CBA" + "MMMCBA" = "ROOOODE"
this has a solution as 543+999543=1000086 and it gives me that when I call backtrack without binarization.
but after binarization it gives me 745+999745=1000068 which does not satisfy the constraints.
maybe there is some bug in convert_to_binary?

what I understand the problem is here (csp.py line 239)
new_domains[hidden] = [t for t in product(*map(domains.get, vars_)) if const(vars_, t)]
in case of same variable appear twice in the constraint (A + A = E + carry), it still creates a domain which is the cartesian product D_A X D_A X D_E X D_carry, though different assignments to same variable should not be allowed (e.g. the tuple (9, 8, 7, 1) is not allowed, only (9, 9, 7, 1 ). must somehow ensure that in the hidden variable possible vector all appearances of the same variable get the same value. because when it checks inside wdiff.diff it checks only the index of the first appearance in vars_ (since that what vars_.index returns)

I solved this by adding a condition "same_variable_same_assignment(vars_, t)" in line 239:
new_domains[hidden] = [t for t in product(*map(domains.get, vars_))
if const(vars_, t) and same_variable_same_assignment(vars_, t)]
where:
def same_variable_same_assignment(vars_, t):
....unique_vars = set(vars_)
....for var_ in unique_vars:
........inds = [i for i in range(len(vars_)) if vars_[i]==var_]
........if any([t[ind]!=t[inds[0]] for ind in inds]):
............return False
....return True

Thanks

[fisadev]

Hi! thanks for the report and the proposed solution! I'm a little busy with work and other stuff during these days, but I'll try to take a better look at this in the following couple of weeks :)