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

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

StackExchange Code Review Q#44521, answer score: 4