Sudoku Solver — Graph Coloring

I got the inspiration for this project when I watched a Numberphile video on YouTube showing that a Sudoku can be solved using Graph Coloring Algorithm. And when I searched the internet about it there were a lot of videos and posts just showing that it can be done. And only a few had implemented the algorithm. And those who did implement this, used a built in library for creating graphs.

But I thought what if I can code my own graph from scratch and then implement it. Through this one can understand the basic structure and working of a graph and how the algorithm works.

What I will cover ?

1. What is Sudoku
2. What is a Graph
3. What is Graph Coloring
4. Intuition Behind Graph Coloring
5. Graph Coloring Algorithm
6. How Sudoku can be solved using Graph Coloring
7. Implementation

What is Sudoku ?

Sudoku is a single — player logic based puzzle. A Sudoku puzzle is a grid of 81 cells, which is divided into 9 rows, columns and regions(or blocks).

The goal is to place the numbers from 1- 9 into empty cells in such a way, that in every row, every column and every region (3 x 3 block) each number appears only once .

source: Wikipedia

source: Wikipedia

What is a Graph ?

Graph is a set of vertices(or nodes) and a set of edges which connects a pair of nodes.

source: GeeksForGeeks

In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34, 04, 14, 13}.

What is Graph Coloring ?

Graph coloring is an assignment of different colors ( or labels) to the vertices of a graph, such that no 2 adjacent (connected) vertices have the same color

source : Brilliant

In G- Graph Coloring Problem, we have to find if a graph can be colored with a minimum of ‘G’ colors. This ‘G’ is also known as the Chromatic Number of a Graph, and is denoted as χ(G)

For this Graph, Chromatic Number, G = 2 { χ(2) }

And for this graph, Chromatic Number, G = 3 { χ(3) }

Before I tell you about the algorithm, let’s see whats the intuition behind it.

Intuition Behind Graph Coloring

Lets take this (undirected )graph as an example. Let our starting node be 1, and our goal is to color this graph in such a way so that no two nodes adjacent to each other (connected to each other) have the same color.

And let the available (list of )colors be : Blue, Red, Yellow

Initially all the nodes are not colored.

We will be creating a recursive function.

1. Starting with Node 1
2. Take a color c from the color list.(say, Blue)
3. Before putting the color on this node check if any of the adjacent nodes have this color or not.
4. The adjacent nodes for node 1 are nodes 2 and 3.
5. They don’t have the color blue in them. So it is safe to color node 1 with blue.

Now we have colored our node 1 with the color blue. That means none of the adjacent nodes (of 1) cannot have the color blue. Lets see, how it works:

Now, go to one of the adjacent nodes of 1. (lets take 2 for this example)

1. Starting with Node 2 now
2. Take color c from color list (Blue)
   The computer does not know by default to immediately pick a color other than blue from the color list. So we have iterate through the list, and try to put a color on that node. So first option that the computer will try for node 2 will be Blue.
3. To check if it is safe to color Blue at Node 2 it will check the neighboring/adjacent nodes to see if any of nodes have Blue color or not. (For 2 the adjacent nodes are — 1,3,4)
4. Node 1 has blue color and nodes 3 and 4 are not colored. So it is not safe to put blue color on Node 2
5. Now we will check for the next color on the list. That is Red.
6. It will repeats 2 to 4 but for the color red.
7. It is safe to put red color on node 2.

Now for Node 3.

Similarly we will check for Node 3.

1. First we will check for blue color and see if it is safe to color node 3 with blue.
2. The adjacent Node 1 has blue color on it. So it is not safe to color Node 3 with Blue.
3. For the next color Red, Node 2 is colored with Red and thus we cannot color Node 3 with Red too,
4. Then we will go for next color Yellow.
5. Now we will check all the adjacent nodes again to check if any one of them is colored with Yellow or not.
6. It is safe to color node 3 with yellow.

Similarly for node 4. We can see that node 4 can take any color other than Red or Yellow.

You can color node 4 with green color too. But we are trying to minimize the number of colors to be used, so first we can put color Blue on it (node 4 is not connected to node 1)

So we can see that this whole graph can be colored with a minimum of 3 colors. Thus the chromatic number of this graph is 3.

Till now, what we have seen is that we were given a graph and a set of colors, to color the graph.

In our above example, we had 3 colors and we were able to color it easily. If we had only 2 colors we would not be able to color it.

So there are 3 different basic problems in graph coloring:

1. Graph is Given. Set of colors is given. Find out all ways in which that graph can be colored using the given colors.
2. Graph is given. Set of colors is given. Find out if the graph can be colored using the given set of colors. ( m -Coloring Decision Problem)
3. Graph is given. Set of colors is not given. Find the minimum number of colors required to color the given graph(m — Coloring Optimization Problem)

Before starting to color the graph, one should know the minimum number of colors required to color that graph. So before going with problems 1 and 2 (defined above) we first find out the minimum number of colors required to color that graph.

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. Therefore, chromatic number for Sudoku Puzzle is 9.

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.

We would be going with Problem 2 in this tutorial :

Graph is given. Set of colors is given. Find out if the graph can be colored using the given set of colors. ( m -Coloring Decision Problem)

Algorithm for Graph Coloring (m-Coloring Decision Problem)

Recap : The idea is to assign colors one by one to different vertices, starting from the vertex 0. 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. If there is any color assignment that does not violate the conditions, mark the color assignment as part of the solution. If no assignment of color is possible then backtrack and return false.

Algorithm

1. Create a recursive function that takes current vertex index, number of vertices and output color array as arguments.
2. If the current vertex index is equal to number of vertices. Return True and print the color configuration in output array.
3. Assign color to a vertex (1 to m).
4. For every assigned color, check if the configuration is safe, (i.e. check if the adjacent vertices do not have the same color) recursively call the function with next index and number of vertices
5. If any recursive function returns true break the loop and return true.
6. If no recursive function returns true, then return false.

How Sudoku can be solved using Graph Coloring

Sudoku Graph is a graph with 81 vertices (or nodes) . Each cell in the Sudoku can be seen as a node of the graph.

Each node (or cell) has an edge to every other node (cell) in its respective column, row, and 3 x 3 grid.

Graph will look like this :

source : Reddit

This is a simplified image. As there are a lot of edges that are hidden. Each vertex has an edge from it to every vertex in it’s column and row, but in this image, all of these edges are lying on top of each other.

Visualization of the whole Sudoku Graph done by : a Reddit User

So we can say that Sudoku can be viewed as Graph and thus can be solved by Graph Coloring with a Chromatic Number, G = 9.

It is no different to using 9 different colors to color the vertices in a way that no two adjacent vertices have the same color.

Implementation

I have used Python to implement it. But you can still follow and understand it and can implement it in any other language. I have not used any library, just classes and objects.

The structure of the directory

.\
   graph.py
   sudoku_connections.py
   main.py

First step is to code a graph, which our Sudoku application will use.

Creating Graph and Node

Create a file graph.py

In this we will write 2 classes :

• class Node
• class Graph

Node Class

As we know a graph is a set of nodes and edges connecting 2 nodes.

So we will make a Node class first.

The instance variables are id, data and connectedTo

The connectedTo variable dictionary is a way one can represent edges between 2 nodes.

The connectedTo dictionary ( key : value pair) will store the ids of the other nodes it is connected along with the weight of that edge.

For this particular application, the data field and the weight of the edges (in the dictionary) are not required. But I still added these to the class, to make it more general and you can use it any other application too.

Now, to add the functions to this class.

In the def addNeighbour(self, neighbour , weight = 0) function, the id and weight pair is added to the connectedTo dictionary. The rest of the code is pretty self - explanatory.

Graph Class

The instance variable of allNodes is a dictionary. It will contain the id of the node object as the key, and the node object itself as the value (idx : node object). This will help us to access the nodes of the graphs with just the id of the nodes.

addNodeData(self, idx, data) function - Creates a Node Object and adds it to the dictionary

addEdge(self, src, dst, wt = 0) function - Adds an edge between 2 given nodes.

I added DFS (Depth First Search) and BFS (Breadth First Search) functions too in this code but they are not mandatory. They will not be used in this project.

Testing the code

Adding a test main function :

In this test example, first we created a graph object and then added 6 nodes withs ids 0 to 5(both inclusive).

Then added edges between various nodes and printed them.

Then did DFS and BFS to check the correctness of the algorithm.

OUTPUT

We are through with the Structure of the Node and the Graph. Now, lets make the nodes and connect them

Initializing all the Nodes and connecting them

For this make another file sudokuConnections.py

In this file first import the Graph class created in the previous section

from graph import Graph

Now create the class SudokuConnections . In this class we will manage the graph and create all the nodes and connect them.

Firstly an instance of Graph Class is created.

After initializing the total number of cells, rows, and columns, function to generate all the nodes is called inside the constructor.After the creation of all the nodes which is stored in the instance variable self.graph a method to connect all the nodes ( discussed below) is called.

Connecting Nodes of Sudoku

Each node (cell) is connected to every other node in the same column , same row and in same 3x3 grid (block).

To connect the nodes connectEdges(self) method is called.

Before connecting all the nodes we need to assign a position to each node. After this only then we can know which nodes to connect.

This is done with the help of __getGridMatrix(self) function.

All the ids with respect to their position in the Sudoku Grid.

Now we can know which nodes to connect through their ids.

Firstly, 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.

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.

I stored all the connections in a dictionary called connections

This dictionary would contain key value pairs of :

• rows : [all the ids in the row]
• cols : [all the ids in the column]
• block : [all the ids in that respective 3x3 block]

connections = dict()
row = []
col = []
block = []

I could have just added them into a single list, but I think by segregating them into different groups improves the readability of the code.

Now, lets discuss on how to connect them…

Connecting Each Node to every other node in the same row :

As we know the position of the head node ( rows, cols) , we can iterate with a simple for loop and get all the ids.

Since we are iterating through the same row, only the column value changes

Connecting Each Node to every other node in the same column:

Similarly we can do the same for columns. But this time column will remain same and we will iterate through rows.

Connecting Each Node to every other node in the same block (3x3 grid):

We can do this by 2 methods :

First, Use FOR LOOP to iterate through element in the 3x3 block and then exclude all the elements in the same row and same column because we already connected them in the previous 2 steps.

Second, use the IF-ELSE condition.

I used the latter option as the time taken to solve it is faster than the former option.

What I did here was just got the index of the ids in the the respective 3x3 grid which are to be connected and generalised them using the rows and cols variables.

After getting all the ids which are to be connected with each other, we call another function self.__connectThose() to connect all the ids and update the connectedTo variable of each node object in the graph.

Testing the Code :

First we created an instance of the class Sudoku Connections. In the constructor itself generated all the nodes. Then connected them according to the constraints (explained above).

Then printed all nodes and their edges.

OUTPUT

So till now, we have created the structure of Graph Class and then connected all the nodes.

Now in the next section we will implement the main function.

Main File (Putting it all together)

Create a file main.py

First import the file you created above

from sudoku_connections import SudokuConnections

Instance Variable self.board is a 2D matrix which represents our Sudoku Board having 9 columns and rows. Right now I have hard coded it to 1 problem, but one can make a generalized version too.

self.sudokuGraph is an object of SudokuConnections Class. This variable holds the whole graph.

self.mappedGrid is a 2D matrix containing the ids of nodes at the position they were assigned, which was discussed in the previous section.

Now lets implement the algorithm :

Recalling the algorithm,

Algorithm for Graph Coloring Problem

1. Create a recursive function that takes the graph, current vertex index, number of vertices and output color array.
2. If the current vertex index is equal to number of vertices. Print the color configuration in output array.
3. Assign color to a vertex (1 to m). { m = the number of colors you want to color the Graph }
4. For every assigned color, check if the configuration is safe, (i.e. check if the adjacent vertices do not have the same color) recursively call the function with next index and number of vertices
5. If any recursive function returns true break the loop and return true.
6. If no recursive function returns true then return false.

As you can see the first step is to create a recursive function, but before we implement that lets make a base function which the object will of this class will call. This base function will now call the recursive function.

One should not directly call the recursive function through an object of the class, since it is not a good programming practice.

The color variable is 1 - D array where each index represents the of the node, and the value at that index represents the color (in our case- numbers from 1-9) assigned to that node.

The given variable is a list and keeps a track of all the numbers which are provided by the puzzle, and thus are not meant to be changed.

Through def graphColoringInitializeColor(self) we are assigning the colors to index (id) which are given by the puzzle.

Then we call the recursive function self.__graphColorUtility(m =m, color=color, v =1, given=given)

Now the first step of the algorithm is complete.

For the 2nd step : if vertex v is equal to total number of nodes in the graph, then return True

Then for steps 3–5,

What the for loop will do is to try to put a color c( or in our case a number between 1 and 9) at that particular vertex v, before putting it in, first it will check if it is safe to put that color in or not through the function __isSafe2Color(self, v, color, c, given).

If a vertex v is in given list but the algorithm is trying to put a different color on that vertex, then return FALSE.

For all the neighbors of vertex v , if a color c is already assigned to any one of them then return FALSE , else return TRUE

If a vertex v is in given list, and the color which it is trying to add matches the color at that vertex then it returns TRUE.

When __isSafe2Color() returns FALSE, it means it is not safe to put that color (number) at that position. So it skips to the next iteration of the loop, and tries the next color.

If it returns TRUE, then it recursively calls self.__graphColorUtility() for the next vertex( v +1)

The program recursively solves the position of each color (number) on the board.

The whole code of this part :

Now testing the code,

OUTPUT :

As you can see, the algorithm was able to solve the Sudoku. It took less than 2 seconds to solve it. No 2 numbers are same in a column, row, and 3x3 grid.

Find the code here : GitHub Code.

😄