# Constraint solving over modular domains

I have a set of constraints over modular domains e.g. $\exists a \in A_i : x \equiv a \pmod{n_i}$ for all $i=0,\ldots,k$

The question is, does such an $x$ exist? I've been pointed to method of successive substitution which ended up with me implementing the following python code.

import fractions
def exist(ruleList, acc = [0,1]): # currentCandidate , currentDomain
if len(ruleList) == 0:
return True
else:
rule = ruleList[0]
n = rule[1]/fractions.gcd(rule[1], acc[1])
newDomain = acc[1] * n
for candidate in (acc[0] + acc[1] * i for i in xrange(n)):
if candidate % rule[1] in rule[0]:
if exist(ruleList[1:], [candidate, newDomain]):
return True
return False

rules = [([0,1,2],5),   # A_1,n_1
([4,5,6],9),   # A_2,n_2
([0,3,6],10)]  # A_3,n_3

print (exists(rules),)  # True

rules = [([0,2,3],5),   # A_1,n_1
([1,2,8],9),   # A_2,n_2
([4,6,9],10)]  # A_3,n_3

print (exist(rules),)   # False


Is their a better way of implementing this or better algorithmic approach?

• This might be interesting to you.
– Dan
Jan 21 '12 at 3:52
• What do you mean by better? Just faster, or something else? Jan 21 '12 at 12:14
• @DavidKetcheson, better in terms of improving the worst case complexity and/or speed optimisations (reduced memory copying, etc). Jan 21 '12 at 14:44
• @Dan I'll look into using that. Jan 21 '12 at 14:44