import sys
class Variable:
”’Class for defining CSP variables.
On initialization the variable object can be given a name and a
list containing variable’s domain of values. You can reset the
variable’s domain if you want to solve a similar problem where
the domains have changed.
To support CSP propagation, the class also maintains a current
domain for the variable. Values pruned from the variable domain
are removed from the current domain but not from the original
domain. Values can be also restored.
undoDict = dict() #stores pruned values indexed by a
#(variable,value) reason pair
def __init__(self, name, domain):
”’Create a variable object, specifying its name (a
string) and domain of values.
self._name = name #text name for variable
self._dom = list(domain) #Make a copy of passed domain
self._curdom = list(domain) #using list
self._value = None
def __str__(self):
return “Variable {}”.format(self._name)
def domain(self):
”’return copy of variable domain”’
return(list(self._dom))
def domainSize(self):
”’Return the size of the domain”’
return(len(self.domain()))
def resetDomain(self, newdomain):
”’reset the domain of this variable”’
self._dom = newdomain
def getValue(self):
return self._value
def setValue(self, value):
if value != None and not value in self._dom:
print(“Error: tried to assign value {} to variable {} that is not in {}’s domain”.format(value,self._name,self._name))
self._value = value
def unAssign(self):
self.setValue(None)
def isAssigned(self):
return self.getValue() != None
def name(self):
return self._name
def curDomain(self):
”’return copy of variable current domain. But if variable is assigned
return just its assigned value (this makes implementing hasSupport easier”’
if self.isAssigned():
return([self.getValue()])
return(list(self._curdom))
def curDomainSize(self):
”’Return the size of the current domain”’
if self.isAssigned():
return(len(self._curdom))
def inCurDomain(self, value):
”’check if value is in current domain”’
if self.isAssigned():
return(value==self.getValue())
return(value in self._curdom)
def pruneValue(self, value, reasonVar, reasonVal):
”’Remove value from current domain”’
self._curdom.remove(value)
print(“Error: tried to prune value {} from variable {}’s domain, but value not present!”.format(value, self._name))
dkey = (reasonVar, reasonVal)
if not dkey in Variable.undoDict:
Variable.undoDict[dkey] = []
Variable.undoDict[dkey].append((self, value))
def restoreVal(self, value):
self._curdom.append(value)
def restoreCurDomain(self):
self._curdom = self.domain()
def reset(self):
self.restoreCurDomain()
self.unAssign()
def dumpVar(self):
print(“Variable\”{}={}\”: Dom = {}, CurDom = {}”.format(self._name, self._value, self._dom, self._curdom))
@staticmethod
def clearUndoDict():
undoDict = dict()
@staticmethod
def restoreValues(reasonVar, reasonVal):
dkey = (reasonVar, reasonVal)
if dkey in Variable.undoDict:
for (var,val) in Variable.undoDict[dkey]:
var.restoreVal(val)
del Variable.undoDict[dkey]
#implement various types of constraints
class Constraint:
”’Base class for defining constraints. Each constraint can check if
it has been satisfied, so each type of constraint must be a
different class. For example a constraint of notEquals(V1,V2)
must be a different class from a constraint of
greaterThan(V1,V2), as they must implement different checks of
satisfaction.
However one can define a class of general table constraints, as
below, that can capture many different constraints.
On initialization the constraint’s name can be given as well as
the constraint’s scope. IMPORTANT, the scope is ordered! E.g.,
the constraint greaterThan(V1,V2) is not the same as the
contraint greaterThan(V2,V1).
def __init__(self, name, scope):
”’create a constraint object, specify the constraint name (a
string) and its scope (an ORDERED list of variable
objects).”’
self._scope = list(scope)
self._name = “baseClass_” + name #override in subconstraint types!
def scope(self):
return list(self._scope)
def arity(self):
return len(self._scope)
def numUnassigned(self):
for var in self._scope:
if not var.isAssigned():
def unAssignedVars(self):
return [var for var in self.scope() if not var.isAssigned()]
# def check(self):
# util.raiseNotDefined()
def name(self):
return self._name
def __str__(self):
return “Cnstr_{}({})”.format(self.name(), map(lambda var: var.name(), self.scope()))
def printConstraint(self):
print(“Cons: {} Vars = {}”.format(
self.name(), [v.name() for v in self.scope()]))
#object for holding a constraint problem
class CSP:
”’CSP class groups together a set of variables and a set of
constraints to form a CSP problem. Provides a usesful place
to put some other functions that depend on which variables
and constraints are active”’
def __init__(self, name, variables, constraints):
”’create a CSP problem object passing it a name, a list of
variable objects, and a list of constraint objects”’
self._name = name
self._variables = variables
self._constraints = constraints
#some sanity checks
varsInCnst = set()
for c in constraints:
varsInCnst = varsInCnst.union(c.scope())
for v in variables:
if v not in varsInCnst:
print(“Warning: variable {} is not in any constraint of the CSP {}”.format(v.name(), self.name()))
for v in varsInCnst:
if v not in variables:
print(“Error: variable {} appears in constraint but specified as one of the variables of the CSP {}”.format(v.name(), self.name()))
self.constraints_of = [[] for i in range(len(variables))]
for c in constraints:
for v in c.scope():
i = variables.index(v)
self.constraints_of[i].append(c)
def name(self):
return self._name
def variables(self):
return list(self._variables)
def constraints(self):
return list(self._constraints)
def constraintsOf(self, var):
”’return constraints with var in their scope”’
i = self.variables().index(var)
return list(self.constraints_of[i])
print(“Error: tried to find constraint of variable {} that isn’t in this CSP {}”.format(var, self.name()))
def unAssignAllVars(self):
”’unassign all variables”’
for v in self.variables():
v.unAssign()
def check(self, solutions):
”’each solution is a list of (var, value) pairs. Check to see
if these satisfy all the constraints. Return list of
erroneous solutions”’
#save values to restore later
current_values = [(var, var.getValue()) for var in self.variables()]
for s in solutions:
s_vars = [var for (var, val) in s]
if len(s_vars) != len(self.variables()):
errs.append([s, “Solution has incorrect number of variables in it”])
if len(set(s_vars)) != len(self.variables()):
errs.append([s, “Solution has duplicate variable assignments”])
if set(s_vars) != set(self.variables()):
errs.append([s, “Solution has incorrect variable in it”])
for (var, val) in s:
var.setValue(val)
for c in self.constraints():
if not c.check():
errs.append([s, “Solution does not satisfy constraint {}”.format(c.name())])
for (var, val) in current_values:
var.setValue(val)
return errs
def __str__(self):
return “CSP {}”.format(self.name())