5
\$\begingroup\$

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)
\$\endgroup\$
  • \$\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\$ – SylvainD Mar 16 '14 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\$ – rookie Mar 16 '14 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\$ – SylvainD Mar 16 '14 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\$ – rookie Mar 16 '14 at 21:18
  • \$\begingroup\$ Method cp_solve is used but I cannot find the definition. Have I missed something ? \$\endgroup\$ – SylvainD Mar 16 '14 at 22:12
2
\$\begingroup\$

Not 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({guesses[neigh] for neigh in graph[n] if neigh     in guesses}), # nb_forbidden_colors
            -len({neigh          for neigh in graph[n] if neigh not in guesses}), # 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 - {guesses[neigh] for neigh in graph[n] if neigh in guesses}:
        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:   {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     } }


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: {GA, FL, TN, MS},
    AK: {},
    AZ: {CA, NV, UT, CO, NM},
    AR: {MO, OK, TX, LA, TN, MS},
    CA: {OR, NV, AZ},
    CO: {WY, NE, KS, OK, NM, AZ, UT},
    CT: {},
    DE: {},
    FL: {AL, GA},
    GA: {SC, NC, TN, AL, FL},
    HI: {},
    ID: {WA, MT, OR, WY, UT, NV},
    IL: {WI, IA, MO, KY, IN, MI},
    IN: {MI, WI, IL, KY, OH},
    IA: {MN, SD, NE, MO, WI, IL},
    KS: {NE, CO, OK, MO},
    KY: {IN, IL, MO, TN, OH, WV, VA},
    LA: {AR, TX, MS},
    ME: {},
    MD: {},
    MA: {},
    MI: {IL, WI, IN, OH},
    MN: {ND, SD, IA, WI},
    MS: {TN, AR, LA, AL},
    MO: {IA, NE, KS, OK, AR, IL, KY, TN},
    MT: {ID, WY, SD, ND},
    NE: {SD, WY, CO, KS, MO, IA},
    NV: {OR, ID, UT, AZ, CA},
    NH: {},
    NJ: {},
    NM: {AZ, UT, CO, OK, TX},
    NY: {},
    NC: {GA, TN, SC, VA},
    ND: {MT, SD, MN},
    OH: {MI, IN, KY, WV},
    OK: {KS, CO, NM, TX, AR, MO},
    OR: {WA, ID, NV, CA},
    PA: {},
    RI: {},
    SC: {GA, NC},
    SD: {ND, MT, WY, NE, MN, IA},
    TN: {KY, MO, AR, MS, MO, AL, GA, NC},
    TX: {OK, NM, AR, LA},
    UT: {ID, NV, WY, CO, AZ, NM},
    VT: {},
    VA: {WV, KY, NC},
    WA: {OR, ID},
    WV: {OH, VA, KY},
    WI: {MN, IA, IL, MI, IN},
    WY: {MT, SD, NE, CO, UT, ID},
}

# 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 = {n:neigh for n,neigh in united_stated_of_america.iteritems() if neigh}

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

solve_problem(australia, colors)
solve_problem(united_stated_of_america, colors)
print nb_calls

A few comments :

  • graph is not updated during the process. The only object we update is guesses. Because of the way we do so, changes can be easily reverted.
  • I've added quite a lot of assertions
  • Optimisations to pick a better candidate should be easy to add.
\$\endgroup\$
  • \$\begingroup\$ Did you see my comments to the original post? \$\endgroup\$ – rookie Mar 18 '14 at 13:45
  • 1
    \$\begingroup\$ I didn't get a chance to look at it yet. However, just to that you know, the usage is not to update the code in your question (because it makes the answer irrelevant and/or hard to understand). You can revert you change and add a part "Edit after taking into account <whatever> from <whoever> about <stuff>". In the meantime, I've updated my code to have some more interesting test case, a way to measure performance and some ideas of optimisation tested and approved :-) \$\endgroup\$ – SylvainD Mar 18 '14 at 17:31
4
\$\begingroup\$

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 <module>
    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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your thoughtful comments. Regarding using the variable i: we want to be efficient, so I think it would be better to take this approach than getting an uncolored list. Also, I think we're not quite okay with how I add/remove colors from the domains. I think you're right that I should only add/remove from domains if the item has not been set. Forward checking only eliminates from the domains along tentative paths: if we return True our domain elimination survives and we keep it for the next path. If not, we should backup, but only reset nodes that remain unsolved. \$\endgroup\$ – rookie Mar 17 '14 at 16:45
  • \$\begingroup\$ Also, this question was more about optimizing my existing algorithm. Can you please refer to the bolded part where I explicitly define my question? \$\endgroup\$ – rookie Mar 17 '14 at 16:47
  • \$\begingroup\$ I think I've found an error. Please have a look at my edited answer. \$\endgroup\$ – SylvainD Mar 17 '14 at 17:27
  • \$\begingroup\$ Please see my edit. If you the code on your example, you'll get false (this is because Victoria can't be a neighbor to Queensland with New South Wales in the way. J Just like in regular backtracking, we have to revert to the last known solution. The easiest way to do this is to make a copy of the old domain before recursing, and use that if we actually make a mistake. Please correct me if I'm wrong! \$\endgroup\$ – rookie Mar 18 '14 at 2:49
  • \$\begingroup\$ I have also added a check in the remove function to skip over colors that have already been set (elimination isn't needed, here). Again, please correct me if you think I'm wrong. Also, thank you for taking the time to review this code. It's great to have the support and it means a lot that you've taken the time to read over my work! \$\endgroup\$ – rookie Mar 18 '14 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.