#   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())