I've written some python code to solve the map coloring problem. In my code, I represent the problem using Territory and MapColor objects:
class Territory: def __init__(self, name, neighbors, color = None): self.name = name self.neighbors = neighbors self.color = color def __str__(self): return str((self.name, self.neighbors, self.color)) class MapColor: def __init__(self, graph, colors): self.map = graph self.colors = colors self.vars = list(self.map.keys()) self.domains =
Here, MapColor.map represents a
WA = 'western australia' NT = 'northwest territories' SA = 'southern australia' Q = 'queensland' NSW = 'new south wales' V = 'victoria' T = 'tasmania' colors = australia = < T: Territory(T, [V] ), WA: Territory(WA, [NT, SA] ), NT: Territory(NT, [WA, Q, SA] ), SA: Territory(SA, [WA, NT, Q, NSW, V] ), Q: Territory(Q, [NT, SA, NSW] ), NSW: Territory(NSW, [Q, SA, V] ), V: Territory(V, [SA, NSW, T] ) >problem = MapColor(australia, colors) Notice that MapColor.domains is used to keep track of the possible colors a Territory can take. My solve function in fact adds some optimization to the standard backtracking method by reducing the domains of neighboring territories. In this function, the variable i is used to iterate through the keys of MapColor.map . As I write in the comments, this code adapts the approach typically used to solve puzzles: the idea is to make a move and then continue solving the rest of the puzzle, moving to the next open spot on the board. Since we can't iterate over a "board" with explicit indices, I iterate over the keys of MapColor.map.
def solve(self, i): if i == len(self.vars): return True # discussion on why we keep track of old domain is in comments old = var = self.vars[i] print 'domain for ' + var + ': ' + str(self.domains[var]) if self.map[var].color != None: return self.solve(i + 1) for color in self.domains[var]: if self.is_valid(var, color): self.set_map(var, color) self.remove_from_domains(var, color) if self.solve(i + 1): return True self.set_map(var, None) self.domains = old return False My question: How can I use a heap (python has heapq ) to choose to visit the Territory with the smallest domain next? Should I pass the heap along with each recursive call? Or should I try to make this method iterative? Would that require using both a stack and a heap? Advice on how to do this would be much appreciated! For reference, here are the other functions used in my code:
def is_valid(self, var, color): territory = self.map[var] for neighbor in territory.neighbors: if color == self.map[neighbor].color: return False return True def set_map(self, key, color): self.map[key].color = color def remove_from_domains(self, key, color): territory = self.map[key] for var in territory.neighbors: if self.map[var].color != None: continue if color in self.domains[var]: self.domains[var].remove(color) \$\begingroup\$ Welcome to CodeReview.SE ! Your question seems interesting and properly ask (nice description and example). However, could you give more information about the i parameter to the solve method ? Also the expected output and an brief explanation would be welcome. Thanks in advance \$\endgroup\$
Commented Mar 16, 2014 at 21:03\$\begingroup\$ @Josay: The goal of the map color problem is to assign a color to each territory such that a given territory does not have the same color as its neighbors. i is used to iterate through the the keys in the MapColor.map . Typically, in depth first search, we push the adjacent nodes onto the stack (or recursively continue with the children). In the kind of backtracking used to solve puzzles, the idea is to make a move and then continue solving the rest of the puzzle, moving to the next open spot on the board. Since we can't iterate over a "board", I iterate over the keys of MapColor.map . \$\endgroup\$
Commented Mar 16, 2014 at 21:12\$\begingroup\$ Thanks for the additional explanation (feel free to edit your answer to incorporate it). Related question (and without trying to go to far in the code review already) : what value should I give if I just want to solve the problem ? 0 ? Can it be a default value ? \$\endgroup\$
Commented Mar 16, 2014 at 21:17\$\begingroup\$ @Josay Yes, 0 is fine, and you're right, the header for solve should be def solve(self, i = 0) . \$\endgroup\$
Commented Mar 16, 2014 at 21:18\$\begingroup\$ Method cp_solve is used but I cannot find the definition. Have I missed something ? \$\endgroup\$
Commented Mar 16, 2014 at 22:12Not really a code-review but more like a complete rewriting.
#!/usr/bin/python def check_valid(graph): for node,nexts in graph.iteritems(): assert(node not in nexts) # # no node linked to itself for next in nexts: assert(next in graph and node in graph[next]) # A linked to B implies B linked to A def check_solution(graph, solution): if solution is not None: for node,nexts in graph.iteritems(): assert(node in solution) color = solution[node] for next in nexts: assert(next in solution and solution[next] != color) def find_best_candidate(graph, guesses): if True: #optimised # Optimisations are to be put here. Ideas would be to take the node with the most uncolored neighboors or the one with the smallest possible number of colors or both candidates_with_add_info = [ ( -len(), # nb_forbidden_colors -len(), # minus nb_uncolored_neighbour n ) for n in graph if n not in guesses] candidates_with_add_info.sort() candidates = [n for _,_,n in candidates_with_add_info] else: candidates = [n for n in graph if n not in guesses] candidates.sort() # just to have some consistent performances if candidates: candidate = candidates[0] assert(candidate not in guesses) return candidate assert(set(graph.keys()) == set(guesses.keys())) return None nb_calls = 0 def solve(graph, colors, guesses, depth): global nb_calls nb_calls += 1 n = find_best_candidate(graph, guesses) if n is None: return guesses # Solution is found for c in colors - : assert(n not in guesses) assert(all((neigh not in guesses or guesses[neigh] != c) for neigh in graph[n])) guesses[n] = c indent = ' '*depth print "%sTrying to give color %s to %s" % (indent,c,n) if solve(graph, colors, guesses, depth+1): print "%sGave color %s to %s" % (indent,c,n) return guesses else: del guesses[n] print "%sCannot give color %s to %s" % (indent,c,n) return None def solve_problem(graph, colors): check_valid(graph) solution = solve(graph, colors, dict(), 0) print solution check_solution(graph,solution) WA = 'western australia' NT = 'northwest territories' SA = 'southern australia' Q = 'queensland' NSW = 'new south wales' V = 'victoria' T = 'tasmania' australia = < T: , WA: , NT: , SA: , Q: , NSW: , V: > AL = "Alabama" AK = "Alaska" AZ = "Arizona" AR = "Arkansas" CA = "California" CO = "Colorado" CT = "Connecticut" DE = "Delaware" FL = "Florida" GA = "Georgia" HI = "Hawaii" ID = "Idaho" IL = "Illinois" IN = "Indiana" IA = "Iowa" KS = "Kansas" KY = "Kentucky" LA = "Louisiana" ME = "Maine" MD = "Maryland" MA = "Massachusetts" MI = "Michigan" MN = "Minnesota" MS = "Mississippi" MO = "Missouri" MT = "Montana" NE = "Nebraska" NV = "Nevada" NH = "NewHampshire" NJ = "NewJersey" NM = "NewMexico" NY = "NewYork" NC = "NorthCarolina" ND = "NorthDakota" OH = "Ohio" OK = "Oklahoma" OR = "Oregon" PA = "Pennsylvania" RI = "RhodeIsland" SC = "SouthCarolina" SD = "SouthDakota" TN = "Tennessee" TX = "Texas" UT = "Utah" VT = "Vermont" VA = "Virginia" WA = "Washington" WV = "WestVirginia" WI = "Wisconsin" WY = "Wyoming" united_stated_of_america = < AL: , AK: <>, AZ: , AR: , CA: , CO: , CT: <>, DE: <>, FL: , GA: , HI: <>, ID: , IL: , IN: , IA: , KS: , KY: , LA: , ME: <>, MD: <>, MA: <>, MI: , MN: , MS: , MO: , MT: , NE: , NV: , NH: <>, NJ: <>, NM: , NY: <>, NC: , ND: , OH: , OK: , OR: , PA: <>, RI: <>, SC: , SD: , TN: , TX: , UT: , VT: <>, VA: , WA: , WV: , WI: , WY: , > # Can't be bothered to complete the East part of the map - removing unused nodes (keeping them is also a good way to test your algorithm and see if still works) united_stated_of_america = colors = solve_problem(australia, colors) solve_problem(united_stated_of_america, colors) print nb_calls