Backtracking - M Coloring Problem

Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”. Problems which are typically solved using backtracking method have a property in common: These problems can only be solved by trying every possible configuration and each configuration is tried only once.

The M Coloring problem is an example of such problem.
The problem statement is a follow:
Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.

1) A 2D array graph[V][V] where V is the number of vertices in graph and graph[V][V] is adjacency matrix representation of the graph. A value graph[i][j] is 1 if there is a direct edge from i to j, otherwise graph[i][j] is 0.
2) An integer m which is maximum number of colors that can be used.

Output: An array color[V] that should have numbers from 1 to m. color[i] should represent the color assigned to the ith vertex. The code should also return false if the graph cannot be colored with m colors.

png

Algorithm:

If all colors are assigned,
    print vertex assigned colors
Else
    a. Trying all possible colors, assign a color to the vertex
    b. If color assignment is possible, recursivelty assign colors to next vertices
    c. If color assignment is not possible, de-assign color, return False

Code:

def is_safe(n, graph, colors, c):
    # Iterate trough adjacent vertices
    # and check if the vertex color is different from c
    for i in xrange(n):
        if graph[n][i] and c == colors[i]: return False
    return True

# n = vertex nb
def graphColoringUtil(graph, color_nb, colors, n):
    # Check if all vertices are assigned a color
    if color_nb+1 == n :
        return True
    
    # Trying differents color for the vertex n
    for c in xrange(1, color_nb+1):
        # Check if assignment of color c to n is possible
        if is_safe(n, graph, colors, c):
            # Assign color c to n
            colors[n] = c
            # Recursively assign colors to the rest of the vertices
            if graphColoringUtil(graph, color_nb, colors, n+1): return True
            # If there is no solution, remove color (BACKTRACK)
            colors[n] = 0

We test the algorithm for the following graph and test whether it is 3 colorable:

   (3)---(2)
    |   / |
    |  /  |
    | /   |
   (0)---(1)

#nb of vertex
vertex_nb = 4
# nb of colors
color_nb = 3
# Initiate vertex colors
colors = [0] * vertex_nb

graph = [
    [0, 1, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 1, 0],
]

#beginning with vertex 0
if graphColoringUtil(graph, color_nb, colors, 0):
    print colors
else:
    print "No solutions"

[1, 2, 3, 2]

The solution corresponds to the following assignments:
1st node : color 1
2nd node : color 2
3rd node : color 3

References:

http://www.geeksforgeeks.org/backttracking-set-5-m-coloring-problem/

Backtracking - Rat in a Maze »