Constraint Programming: Map color problem
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.