constraints

from csp import Constraint, Variable

class TableConstraint(Constraint):
”’General type of constraint that can be use to implement any type of
constraint. But might require a lot of space to do so.

A table constraint explicitly stores the set of satisfying
tuples of assignments.”’

def __init__(self, name, scope, satisfyingAssignments):
”’Init by specifying a name and a set variables the constraint is over.
Along with a list of satisfying assignments.
Each satisfying assignment is itself a list, of length equal to
the number of variables in the constraints scope.
If sa is a single satisfying assignment, e.g, sa=satisfyingAssignments[0]
then sa[i] is the value that will be assigned to the variable scope[i].

Example, say you want to specify a constraint alldiff(A,B,C,D) for
three variables A, B, C each with domain [1,2,3,4]
Then you would create this constraint using the call
c = TableConstraint(‘example’, [A,B,C,D],
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4],
[1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2],
[2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4],
[2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1],
[3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4],
[3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1],
[4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3],
[4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]])
as these are the only assignments to A,B,C respectively that
satisfy alldiff(A,B,C,D)

Constraint.__init__(self,name, scope)
self._name = “TableCnstr_” + name
self.satAssignments = satisfyingAssignments

def check(self):
”’check if current variable assignments are in the satisfying set”’
assignments = []
for v in self.scope():
if v.isAssigned():
assignments.append(v.getValue())
return True
return assignments in self.satAssignments

def hasSupport(self, var,val):
”’check if var=val has an extension to an assignment of all variables in
constraint’s scope that satisfies the constraint. Important only to
examine values in the variable’s current domain as possible extensions”’
if var not in self.scope():
return True #var=val has support on any constraint it does not participate in
vindex = self.scope().index(var)
found = False
for assignment in self.satAssignments:
if assignment[vindex] != val:
continue #this assignment can’t work it doesn’t make var=val
found = True #Otherwise it has potential. Assume found until shown otherwise
for i, v in enumerate(self.scope()):
if i != vindex and not v.inCurDomain(assignment[i]):
found = False #Bummer…this assignment didn’t work it assigns
break #a value to v that is not in v’s curDomain
#note we skip checking if val in in var’s curDomain
if found: #if found still true the assigment worked. We can stop
return found #either way found has the right truth value

def findvals(remainingVars, assignment, finalTestfn, partialTestfn=lambda x: True):
”’Helper function for finding an assignment to the variables of a constraint
that together with var=val satisfy the constraint. That is, this
function looks for a supporing tuple.

findvals uses recursion to build up a complete assignment, one value
from every variable’s current domain, along with var=val.

It tries all ways of constructing such an assignment (using
a recursive depth-first search).

If partialTestfn is supplied, it will use this function to test
all partial assignments—if the function returns False
it will terminate trying to grow that assignment.

It will test all full assignments to “allVars” using finalTestfn
returning once it finds a full assignment that passes this test.

returns True if it finds a suitable full assignment, False if none
exist. (yes we are using an algorithm that is exactly like backtracking!)”’

# print “==>findvars([“,
# for v in remainingVars: print v.name(), ” “,
# print “], [“,
# for x,y in assignment: print “({}={}) “.format(x.name(),y),
# print “”

#sort the variables call the internal version with the variables sorted
remainingVars.sort(reverse=True, key=lambda v: v.curDomainSize())
return findvals_(remainingVars, assignment, finalTestfn, partialTestfn)

def findvals_(remainingVars, assignment, finalTestfn, partialTestfn):
”’findvals_ internal function with remainingVars sorted by the size of
their current domain”’
if len(remainingVars) == 0:
return finalTestfn(assignment)
var = remainingVars.pop()
for val in var.curDomain():
assignment.append((var, val))
if partialTestfn(assignment):
if findvals_(remainingVars, assignment, finalTestfn, partialTestfn):
return True
assignment.pop() #(var,val) didn’t work since we didn’t do the return
remainingVars.append(var)
return False

class NValuesConstraint(Constraint):
”’NValues constraint over a set of variables. Among the variables in
the constraint’s scope the number that have been assigned
values in the set ‘required_values’ is in the range
[lower_bound, upper_bound] (lower_bound <= #of variables assigned 'required_value' <= upper_bound) For example, if we have 4 variables V1, V2, V3, V4, each with domain [1, 2, 3, 4], then the call NValuesConstraint('test_nvalues', [V1, V2, V3, V4], [1,4], 2, 3) will only be satisfied by assignments such that at least 2 the V1, V2, V3, V4 are assigned the value 1 or 4, and at most 3 of them have been assigned the value 1 or 4. def __init__(self, name, scope, required_values, lower_bound, upper_bound): Constraint.__init__(self,name, scope) self._name = "NValues_" + name self._required = required_values self._lb = lower_bound self._ub = upper_bound def check(self): assignments = [] for v in self.scope(): if v.isAssigned(): assignments.append(v.getValue()) return True rv_count = 0 #print "Checking {} with assignments = {}".format(self.name(), assignments) for v in assignments: if v in self._required: rv_count += 1 #print "rv_count = {} test = {}".format(rv_count, self._lb <= rv_count and self._ub >= rv_count)

return self._lb <= rv_count and self._ub >= rv_count

def hasSupport(self, var, val):
”’check if var=val has an extension to an assignment of the
other variable in the constraint that satisfies the constraint

HINT: check the implementation of AllDiffConstraint.hasSupport
a similar approach is applicable here (but of course
there are other ways as well)
if var not in self.scope():
return True #var=val has support on any constraint it does not participate in

#define the test functions for findvals
def valsOK(l):
”’tests a list of assignments which are pairs (var,val)
to see if they can satisfy this sum constraint”’
rv_count = 0
vals = [val for (var, val) in l]
for v in vals:
if v in self._required:
rv_count += 1
least = rv_count + self.arity() – len(vals)
most = rv_count
return self._lb <= least and self._ub >= most
varsToAssign = self.scope()
varsToAssign.remove(var)
x = findvals(varsToAssign, [(var, val)], valsOK, valsOK)

class IfAllThenOneConstraint(Constraint):
”’if each variable in left_side equals each value in left_values
then one of the variables in right side has to equal one of the values in right_values.
hasSupport tested only, check() untested.”’
def __init__(self, name, left_side, right_side, left_values, right_values):
Constraint.__init__(self,name, left_side+right_side)
self._name = “IfAllThenOne_” + name
self._ls = left_side
self._rs = right_side
self._lv = left_values
self._rv = right_values