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