map coloring using backtracking algo

mgcoloring.py

# mgcoloring

# SOVLED USING BACKTRACKING
  
class Graph(): 
  
    def __init__(self, vertices): 
        self.V = vertices 
        self.graph = [[0 for column in range(vertices)]\
                              for row in range(vertices)]
    # A utility function to check if the current color assignment is safe for vertex v 
    def CanWeGo(self, v, colour, c): 
        for i in range(self.V): 
            if self.graph[v][i] == 1 and colour[i] == c: 
                return False
        return True
      
    # A recursive utility function to solve m coloring problem 
    def TurnTheColorOn(self, m, colour, v): 
        if v == self.V: 
            return True
  
        for c in range(1, m+1): 
            if self.CanWeGo(v, colour, c) == True: 
                colour[v] = c 
                if self.TurnTheColorOn(m, colour, v+1) == True: 
                    return True
                colour[v] = 0
  
    def DoTheJob(self, m): 
        colour = [0] * self.V 
        if self.TurnTheColorOn(m, colour, 0) == False: 
            return False
  
        # Print the solution 
        print("Solution exist and Following are the assigned colours:")
        for c in colour: 
            print(c) 
        return True
  
# Driver Code 
g  = Graph(4) 
g.graph = [[0,1,1,1], [1,0,1,0], [1,1,0,1], [1,0,1,0]] 
m=3
g.DoTheJob(m)