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.