# Figure 5.8 page 151 Min-Conflicts class CSP : """ Constraint Satisfaction Problems. CSP specified by four inputs: VARIABLES A list of variables; each is atomic (e.g. int or string). DOMAINS A dict of {var:[possible_value, ...]} entries. NEIGHBORS A dict of {var:[var,...]} that for each variable lists the other variables that participate in constraints. CONSTRAINTS A function f(A, a, B, b) that returns true if neighbors A, B satisfy the constraint when they have values A=a, B=b """ def __init__(self, vars, domains, neighbors, constraints): self.VARIABLES=vars self.DOMAINS=domains self.NEIGHBORS=neighbors self.CONSTRAINTS=constraints def conflicted_vars(self, current): "Return a list of variables in current assignment that are in conflict" return [var for var in self.VARIABLES if self.nconflicts(var, current[var], current) > 0] def nconflicts(self, var, value, assignment): "Return the number of conflicts var=val has with other variables." def conflict(var2): val2 = assignment.get(var2, None) return val2 != None and not self.CONSTRAINTS[var](var, value, var2, val2) return countTRUE(conflict, self.NEIGHBORS[var]) #______________________________________________________________________________ import random def MIN_CONFLICTS(csp, max_steps=1000000) : current = {}; for var in csp.VARIABLES: current[var]=csp.DOMAINS[var][0] for i in range(max_steps) : conflicted = csp.conflicted_vars(current) if not conflicted : return current var = conflicted[int(random.uniform(0, len(conflicted)))] val = min_conflicts_value(csp, var, current) current[var]=val print current return None def min_conflicts_value(csp, var, current): """Return the value that will give var the least number of conflicts. Ignore tie.""" return argmin(csp.DOMAINS[var], lambda val: csp.nconflicts(var, val, current)) def argmin(seq, fn) : # Return seq that evaluate to minimum fn(seq[0..n]) min = 0 minvalue = fn(seq[min]) for i in range(len(seq)) : testvalue = fn(seq[i]) if testvalue == minvalue : # Select randomly when equal if random.uniform(0, 1) > 0.5 : min = i if testvalue < minvalue : min = i minvalue = testvalue return seq[min] def countTRUE( fn, list) : n=0 for v in list : if fn(v) : n=n+1 return n def Australia() : # Return a CSP instance of the Map Coloring of Australia. WA,Q,T,V,SA,NT,NSW = 'WA','Q','T','V','SA','NT','NSW' values = ['R', 'G', 'B'] vars = [WA, Q, T, V, SA, NT, NSW] domains = {SA: values[:], WA:values[:],NT:values[:], Q:values[:], NSW:values[:], V:values[:], T:values[:]} neighbors = {WA: [SA, NT], Q: [SA, NT, NSW], T: [],V: [SA, NSW], SA: [WA, NT, Q, NSW, V], NT: [SA, WA, Q], NSW: [SA, Q, V]} constraints = {SA: constraint, WA:constraint, NT:constraint, Q:constraint, NSW:constraint, V:constraint, T:constraint} return CSP(vars, domains, neighbors, constraints) def constraint(A, a, B, b): # Two neighboring variables must differ in value. return a != b def run(): print MIN_CONFLICTS(Australia())