Paint adjacent boundaries with distinct colors

In my recent A.I. class, I had an assignment where I had to write some code that will paint the countries of Africa with distinct colors. For the colors, I was given a domain of set(['red','blue','white','yellow','green']). Additionally, a Python dictionary is given that contains each country and their adjacent countries.

For example, Egypt is right next to Libya and Sudan. This means that if Egypt is given some color, such as red, then Libya and Sudan must not be red.

Here is the Python code that paints adjacent countries with different colors. I have tried two different inference methods, forward checking and AC-3. I found my forward checking algorithm to only use 4 out of the 5 colors given, where as my AC-3 used all 5 colors. 4 is definitely the minimum -- any less is not possible for this assignment without contradicting the adjacent and distinct color rule.

    countries = {
        "algeria": ["libya", "mali", "mauritania", "morocco", "niger", "tunisia"],
        "angola": ["democratic_republic_of_the_congo", "republic_of_the_congo", "namibia", "zambia"],
        "benin":["togo", "burkina_fazo", "niger", "nigeria"],
        "botswana":["namibia", "south_africa", "zimbabwe", "zambia"],
        "burkina_fazo":["benin", "ivory_coast", "ghana", "mali", "niger", "togo"],
        "burundi":["democratic_republic_of_the_congo", "rwanda", "tanzania"],
        "cameroon":["central_african_republic", "chad", "republic_of_the_congo", "equatorial_guinea", "gabon", "nigeria"],
        "cape_verde":[],
        "central_african_republic":["cameroon", "chad", "democratic_republic_of_the_congo", "republic_of_the_congo", "sudan"],
        "chad":["cameroon", "central_african_republic", "libya", "niger", "nigeria", "sudan"],
        "comoros":[],
        "democratic_republic_of_the_congo":["angola", "burundi", "central_african_republic", "republic_of_the_congo", "rwanda", "sudan", "tanzania", "uganda", "zambia"],
        "republic_of_the_congo":["angola", "cameroon", "central_african_republic", "democratic_republic_of_the_congo", "gabon"],
        "ivory_coast":["burkina_fazo", "ghana", "guinea", "liberia", "mali"],
        "dijbouti":["eritrea", "ethiopia", "somalia"],
        "egypt":["libya", "sudan"],
        "equatorial_guinea":["gabon", "cameroon"],
        "eritrea":["dijbouti", "ethiopia", "sudan"],
        "ethiopia":["eritrea", "dijbouti", "somalia", "sudan", "kenya"],
        "gabon":["equatorial_guinea", "cameroon","republic_of_the_congo"],
        "gambia":["senegal"],
        "ghana":["burkina_fazo","ivory_coast", "togo"],
        "guinea":["ivory_coast","guinea-bissau","liberia","mali","senegal","sierra_leone"],
        "guinea-bissau":["guinea", "senegal"],
        "kenya":["ethiopia", "somalia", "tanzania", "uganda", "sudan"],
        "lesotho":["south_africa"],
        "liberia":["guinea", "ivory_coast", "sierra_leone"],
        "libya":["algeria", "chad", "egypt", "niger", "sudan", "tunisia"],
        "madagascar":[],
        "malawi":["mozambique", "tanzania", "zambia"],
        "mali":["algeria", "niger", "burkina_fazo", "ivory_coast", "guinea", "senegal", "mauritania"],
        "mauritania":["algeria", "mali", "senegal"],
        "mauritius":[],
        "morocco":["algeria"],
        "mozambique":["malawi", "south_africa", "swaziland", "tanzania", "zambia", "zimbabwe"],
        "namibia":["angola", "botswana", "south_africa", "zambia", "zimbabwe"],
        "niger":["algeria", "benin", "burkina_fazo", "chad", "libya", "mali", "nigeria"],
        "nigeria":["benin", "cameroon", "chad", "niger"],
        "reunion":[],
        "rwanda":["burundi", "democratic_republic_of_the_congo", "tanzania", "uganda"],
        "sao_tome_and_principe":[],
        "senegal":["gambia", "guinea", "guinea-bissau", "mali", "mauritania"],
        "seychelles":[],
        "sierra_leone":["guinea", "liberia"],
        "somalia":["dijbouti", "ethiopia", "kenya"],
        "south_africa":["botswana", "lesotho", "mozambique", "namibia", "swaziland", "zimbabwe"],
        "sudan":["central_african_republic", "chad", "democratic_republic_of_the_congo", "egypt", "eritrea", "ethiopia", "kenya", "libya", "uganda"],
        "swaziland":["mozambique","south_africa"],
        "tanzania":["burundi", "democratic_republic_of_the_congo", "kenya", "malawi", "mozambique", "rwanda","uganda","zambia"],
        "togo":["benin", "burkina_fazo", "ghana"],
        "tunisia":["algeria", "libya"],
        "uganda":["democratic_republic_of_the_congo", "kenya", "rwanda", "sudan", "tanzania"],
        "zambia":["angola", "botswana", "democratic_republic_of_the_congo", "malawi", "mozambique", "namibia", "tanzania", "zimbabwe"],
        "zimbabwe":["botswana", "mozambique", "south_africa", "zambia", "namibia"],}


    domain = set(['red','blue','white','yellow','green'])

    def selectUnassignedVariable(assignment, csp): # Minimum Remaining Variable - Choose the variable with the smallest domain

    # count keeps track of the smallest length of domains
        count = 0

    # select_country keeps track of the country with the domain of smallest length
        select_country = False


        for country in assignment:
            if len(assignment[country]) > 1:

            # count should only be 0 at initialization
                if count is 0 or count > len(assignment[country]):
                    count = len(assignment[country])
                    select_country = country

        return select_country

    def orderDomainValues(): # Unordered
        return domain

    """

    def inference (csp, var, value, assignment): # Forward checking
        for adj_c in csp[var]: # for each adjacent country to the current country represented by 'var'
            if value is assignment[adj_c]: # if this color is exactly the only color that this adjacent country has in the domain
                return False
            elif (value in assignment[adj_c]): # otherwise check if this color is a subset of the adjacent countrys domain
                assignment[adj_c].remove(value) # if so, remove the color from the adjacent country's domain
        return True

    """
    def inference (csp, assignment): # AC-3

        """ initialize the queue with all the arcs in csp"""

    # queue = list of arcs (i.e. an arc from Chad to Egypt)
        queue = []

    # tail represents a country
        for tail in csp :

        # curr represents a country adjacent to tail
        # add arcs from tail -> (adjacent countries to tail) to the queue
            for curr in csp[tail]:
                queue.append( ( tail, curr ) )

        """ loop until queue is empty """
        while queue:
            (tail, head) = queue.pop()

        # check if the arc from tail -> head satisfies constraint
            if revise(csp, assignment, tail, head):

            # the arc from tail -> head failed constraint, but was fixed in the revise function

            # add new arcs from (adjacent countries of tail) -> tail to the queue
                for curr in csp[tail]:
                    queue.append((curr, tail))



    def revise(csp, assignment, tail, head): # returns True (arc is revised) or False (arc needs no revision -- it passes all constraints)

    # default return value is False (may change later)
        revised = False

    # This procedure is needed since python collections are mutable
    # tempAssignment is a copy of assignment that is iterated while changes are made to assignment
        tempAssignment = {}
        for country in assignment:
            tempAssignment[country] = assignment[country].copy()

    # Initialize boolean for constraint check
        constraintSatisfied = True


    # x - a color in tail domain
    # y - a color in head domain
        for x in tempAssignment[tail]:
            for y in tempAssignment[head]:
                constraintSatisfied = True

                """ Constraints:
                    # 1. For every color x in tail, there is some color y in head that is legal
                    # 2. The domain is not assigned a color already """
                if x is y and len(tempAssignment[tail]) is not 1:
                    constraintSatisfied = False

            if constraintSatisfied is False:
                assignment[tail].remove(x)
            # return value changed from False to True (this arc is revised)
                revised = True

        return revised

    def backtrackingSearch(csp):

    # initialization, runs only once
        assignment = {}
        for country in csp:
            assignment[country] = set(['red','blue','white','yellow','green'])

        return recursiveBacktracking(assignment,csp)

    def recursiveBacktracking(assignment, csp):

        """ GOAL TEST : each country should be mapped to 1 color only, meaning they are assigned """
        if all(len(assignment[country]) == 1 for country in csp):
            return assignment

        """ choose a country with MRV (Minimum-Remaining Values) """
        var = selectUnassignedVariable(assignment, csp)

        """ choose a color from all available colors. No ordering is used for orderDomainValues. """
        for value in orderDomainValues():

        # if the color is in the countrys domain, proceed
            if value in assignment[var]:

            # assign this color to this country; the countrys domain is just now one element of this color
                assignment[var] = set([value])

                """ run the inference (AC-3) and remove necessary colors from adjacent countries """
                inferences = inference(csp, assignment)

            # recursive loop, find the iteration that passes the goal test and has all countries assigned
                result = recursiveBacktracking(assignment, csp)
                if result is not None:
                    return result

    # this iteration of the recursion loop did not pass the goal test, so we terminate it
        return None


    coloredMap = backtrackingSearch(countries)
    print "\ncoloredMap = \n\n", coloredMap

Update 1: Fixed formatting of code.