block : Ĭonnections = dict() row = col = block =.This dictionary would contain key value pairs of : I stored all the connections in a dictionary called connections The function _whatToConnectdefines which elements to connect based on the position of the head in the matrix which are passed as arguments to the function. Now we can know which nodes to connect through their ids.įirstly, we will form a nested loop to iterate through each element ( called head from now), and then create a list of all the elements(ids of the nodes) that particular element will be connected to. If no recursive function returns true, then return false.Īll the ids with respect to their position in the Sudoku Grid.
If any recursive function returns true break the loop and return true.check if the adjacent vertices do not have the same color) recursively call the function with next index and number of vertices For every assigned color, check if the configuration is safe, (i.e.Return True and print the color configuration in output array. If the current vertex index is equal to number of vertices.Create a recursive function that takes current vertex index, number of vertices and output color array as arguments.If no assignment of color is possible then backtrack and return false. If there is any color assignment that does not violate the conditions, mark the color assignment as part of the solution. Before assigning a color, check for safety by considering already assigned colors to the adjacent vertices i.e check if the adjacent vertices have the same color or not. Recap : The idea is to assign colors one by one to different vertices, starting from the vertex 0. ( m -Coloring Decision Problem )Īlgorithm for Graph Coloring (m-Coloring Decision Problem) Find out if the graph can be colored using the given set of colors. We would be going with Problem 2 in this tutorial : We will be skipping the step of finding the chromatic number, but you can try to implement it on your own if you are curious enough. Therefore, chromatic number for Sudoku Puzzle is 9. So in the next section we will find out how a Sudoku graph can be solved using Graph Coloring, and since we already know -to solve a Sudoku puzzle one needs 9 numbers (or 9 colors, each number representing a color), so the minimum number of colors required is 9. So before going with problems 1 and 2 (defined above) we first find out the minimum number of colors required to color that graph. Find the minimum number of colors required to color the given graph( m - Coloring Optimization Problem)īefore starting to color the graph, one should know the minimum number of colors required to color that graph. Find out all ways in which that graph can be colored using the given colors. So there are 3 different basic problems in graph coloring: If we had only 2 colors we would not be able to color it. In our above example, we had 3 colors and we were able to color it easily. Till now, what we have seen is that we were given a graph and a set of colors, to color the graph. Thus the chromatic number of this graph is 3. So we can see that this whole graph can be colored with a minimum of 3 colors.