Constraint Programming: Map color problem 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 = { var: set(self.colors) for var in self.vars }


Here, MapColor.map represents a {str: Territory} mapping and MapColor.vars, the string keys of the the dictionary (my solve function visits the territories in the dictionary iteratively; once we've exhausted this list, we have know the problem has been solved). Here's an example how this problem can be instantiated:

WA  = 'western australia'
NT  = 'northwest territories'
SA  = 'southern australia'
Q   = 'queensland'
NSW = 'new south wales'
V   = 'victoria'
T   = 'tasmania'

colors    = {'r', 'g', 'b'}

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: set(self.domains[var]) for var in self.vars} 
    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)
Your code looks good but I think you should have a look at PEP 8 which is the Style Guide for Python Code. Among other things, it says :


  Comparisons to singletons like None should always be done with is or is not, never the equality operators.


Also, you should probably add documentation especially as the solve method takes a parameter for no obvious reason. PEP 257 describes the Docstring Conventions.

Finally, the name you give to your variables and members can be quite confusing.



Your Territory class describes a territory by its name, its neighbours and its colors. The association from territory to color is valid only in the context of a MapColor. Thus, Territories could be described just by their name and neighbours. Instead of defining Australia with :

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]        ) }


one could get rid of the Territory class alltogether and remove the duplicated values by defining a mapping from name to containers of neighbours. Because neighbours do not need to be in a given order, a set will do the trick :

australia = { T:   {V                },
              WA:  {NT, SA           },
              NT:  {WA, Q, SA        },
              SA:  {WA, NT, Q, NSW, V},
              Q:   {NT, SA, NSW      },
              NSW: {Q, SA, V         },
              V:   {SA, NSW, T       } }


I also took this chance to add a function to check that the graph is properly defined :

def check_valid(graph):
    for node,nexts in graph.iteritems():
        assert(nexts) # no isolated node
        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


Then, in the MapColor class, you can add a dictionnary to map nodes to their colors (if any).



You don't need to store colors in your MapColor class as you don't reuse it afterward.
Also, the nodes member is not required neither.



The is_valid method can be rewritten in a more concise way using the function all.



The biggest problem in your code is probably the fact that most interesting function takes a parameter for no obvious reason. Easiest solution would be to make it a default parameter with value 0. A more interesting solution would be to try to understand when we want to stop which is when all nodes have been given a color. In order to do so, get the list of nodes with no color and consider we have a valid solution if this list is empty :

   uncolored_nodes = [n for n,c in self.node_colors.iteritems() if c is None]
    if not uncolored_nodes:
        print self.node_colors
        return True


Then, in order to know what is the next node to consider, just take the first of the list (at this stage, we know that the list cannot be empty):

    node = uncolored_nodes[0]


(This also makes obvious the fact that condition if self.map[var].color != None: (which would be written self.node_colors[node] is not None in my code) cannot be true by definition of node.



Once comments have been taken into account (except for the comments because I can't be bothered), the code looks like :

#!/usr/bin/python


def check_valid(graph):
    for node,nexts in graph.iteritems():
        assert(nexts) # no isolated node
        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

class MapColor:

    def __init__(self, graph, colors):
        check_valid(graph)
        self.graph = graph
        nodes = list(self.graph.keys())
        self.node_colors  = { node: None for node in nodes }
        self.domains = { node: set(colors) for node in nodes }


    def solve(self):
        uncolored_nodes = [n for n,c in self.node_colors.iteritems() if c is None]
        if not uncolored_nodes:
            print self.node_colors
            return True

        node = uncolored_nodes[0]
        print 'domain for '  + node + ': ' + str(self.domains[node])
        for color in self.domains[node]:
            if all(color != self.node_colors[n] for n in self.graph[node]):
                self.set_color(node, color)
                self.remove_from_domains(node, color)

                if self.solve():
                    return True

                self.set_color(node, None)
                self.add_to_domains(node, color)

        return False

    def set_color(self, key, color):
        self.node_colors[key] = color

    def remove_from_domains(self, key, color):
        for node in self.graph[key]:
            if color in self.domains[node]:
                self.domains[node].remove(color)

    def add_to_domains(self, key, color):
        for node in self.graph[key]:
            self.domains[node].add(color)



WA  = 'western australia'
NT  = 'northwest territories'
SA  = 'southern australia'
Q   = 'queensland'
NSW = 'new south wales'
V   = 'victoria'
T   = 'tasmania'

colors    = {'r', 'g', 'b'}

australia = { T:   {V                },
              WA:  {NT, SA           },
              NT:  {WA, Q, SA        },
              SA:  {WA, NT, Q, NSW, V},
              Q:   {NT, SA, NSW      },
              NSW: {Q, SA, V         },
              V:   {SA, NSW, T       } }

problem = MapColor(australia, colors)

problem.solve()




Once all of this has been done, one can notice that the node_colors and domains contain somewhat duplicated information : a node n has color c if and only if domains[n] == {c}. I have no time to get rid of node_colors but that would be my next suggestion. Also, there might be a problem with the way you add/remove colors because when calling self.add_to_domains(node, color) we might re-add a color that has been removed at an earlier stage. I am not able to find an example right now but it might be something to consider. Please let me know if you think I am wrong.



Problem in your code (and in mine) : trying to make the test case a bit more interesting (at the moment, your example does not encounter any problem), I've discovered a problem.

Indeed, I was adding Queensland as a neighboor of Victoria (which is still possible in a planar graph if the Sunshine State decided to invade the West Coast of NSW) and I got the following error :

Traceback (most recent call last):
  File "./colors_original.py", line 99, in &lt;module&gt;
    problem.solve(0)
  File "./colors_original.py", line 43, in solve
    if self.solve(i + 1):
  File "./colors_original.py", line 43, in solve
    if self.solve(i + 1):
  File "./colors_original.py", line 36, in solve
    for color in self.domains[var]:
RuntimeError: Set changed size during iteration


Before trying to go for better perf, I think you should try to make this correct. Because maintaining a consistent state whilst calling recursive method can be quite hard, I guess you should try to make things as simple as possible. I'll try to update this answer if I think of anything interesting but it is quite unlikely.