# Figure 5.3 page 142 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 BACKTRACKING_SEARCH(csp) : return RECURSIVE_BACKTRACKING( {}, csp) def RECURSIVE_BACKTRACKING( assignment, csp) : if COMPLETE(assignment, csp.VARIABLES ) : return assignment var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp) for value in ORDER_DOMAIN_VALUES( var, assignment, csp) : if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) : assignment[var]=value result = RECURSIVE_BACKTRACKING(assignment,csp) if result != 'failure' : return result del assignment[var] return 'failure' def SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp) : for v in vars: # Return first unassigned variable if v not in assignment: return v def COMPLETE(assignment, vars) : for var in vars : if not (var in assignment) : return False return True def ORDER_DOMAIN_VALUES( var, assignment, csp) : return csp.DOMAINS[var][:] def CONSISTENT(var, value, assignment, constraints, neighbors) : if not assignment : return True for c in constraints.keys() : for var2 in neighbors[var] : if var2 in assignment and not constraints[c](var, value, var2, assignment[var2]) : return False return True 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 BACKTRACKING_SEARCH(Australia())