A Sudoku Solver using Graph Coloring

Download SudokuSolver.zip

Introduction

In this article, I will explain the concept of graph coloring and how it can be used to solve a 9x9 Sudoku Puzzle. This article assumes that the reader is already familiar with the concept of a graph and its representation.

Graph Coloring Demystified

A graph is a mathematical representation of a set of objects where some pairs of objects are connected (linked) to each other. The objects are represented by vertices (nodes) and the links are called edges.

 

A Graph with 5 nodes and 5 edges

Graph coloring is the assignment of "colors" to vertices of the graph such that no two adjacent vertices share the same color. For example, in the graph mentioned above vertices 1 and 2 cannot have the same color because they have an edge connecting them. However, vertices 2 and 3 can have the same color because they are not connected. Below is one possible coloring of this graph.

It should be clear by now that one graph can have more than one possible coloring. The goal is to use the minimum number of colors possible. Below are another two possible colorings for the example graph. Coloring (1) uses the 3 colors while Coloring (2) uses 5 colors, hence, coloring (1) is better than coloring (2).

Our color is to find a coloring of a given graph that uses the minimum number of colors. A coloring that uses at most k colors is called k-coloring (e.g. coloring (1) in the above example is a 3-coloring while coloring (2) is a 5-coloring).

If you tried to color the above graph using only two colors you will find out that it cannot be colored at all, Go try it out I will wait :). Therefore, the smallest number of colors needed to color a graph is called its chromatic number.

Contraction and Greedy Coloring Algorithms

Graph coloring is computationally hard and it has been a research topic for many years. Most of the algorithms can be broadly categorized in one of two main topics “Contraction” and “Greedy Coloring”.

Greedy Coloring focuses on carefully picking the next vertex to be colored. Once a vertex is colored, its color never changes. Algorithms under this category differ in the way the next vertex is selected.

A famous algorithm under this category is the Welsh–Powell algorithm. It works as follows:

1. Find the degree of each vertex. (Degree: is the number of edges connected to it)

2. Order the vertices in descending order according to their degree.

3. Go through the list, color each vertex not connected to colored vertices with the same color.

4. Remove colored vertices from the list and repeat the process until all vertices are colored.

Let’s go back to our example.

Step 1:

Vertex	Degree
1	3
2	1
3	2
4	1
5	3

Step 2: The order is 1,5,3,2,4

Step 3:

Vertex		Action
1		Color red
5		Don’t color red because it is connected to 1
3		Don’t color red because it is connected to 1
2		Don’t color red because it is connected to 1
4		Color red

Now the graph looks like this and the new list is  5,3,2

Vertex		Action
5		Color blue
3		Don’t color blue because it is connected to 5
2		Color blue

 

Now the graph looks like this and we are left with one vertex which will be colored green.

The second category “Contraction” works by finding two vertices removing any edges between them, and replacing them with a single vertex where any edges that were connected to any of them are now redirected to new single vertex. A contraction algorithm would work as follows:

1. Select the vertex of maximum degree V.

2. Find the set of non-adjacent vertices to V.

3. From this set select the vertex Y of maximum common vertices with V.

4. Contract Y into V to be colored with the same color.

5. Remove Y from the set and repeat steps 3-5 until the list is empty.

6 .Remove vertex V from the graph

7. Repeat steps 1-6 until the resulting graph has all contracted nodes adjacent to each other.

Let’s go back to our example. Vertex (1) has the maximum degree; its non adjacent vertices are vertex (4). Hence, Vertex (1) and (4) are contracted into one node.

 

Now, the vertex with maximum degree is ({1,4}) and it all remaining vertices are adjacent. Hence, remove vertex ({1,4}) from the graph and select vertex with maximum degree.

 

 

Now, vertex (3) has maximum degree and it has one non adjacent vertex (2). Vertex (3) and (2) are contracted into a single vertex.

Vertex ({3,2}) has no non adjacent vertices, hence, it will be removed from the graph. We are left with a single vertex (5); our work is done. The algorithm produces three groups {1,4}, {2,3} and {5} each group will take a different color.

Implemented Algorithm

In my implementation, I choose a greedy coloring algorithm with some modifications as proposed in the paper by Dr. Hussein Al-Omari and Khair Eddin Sabri published in the American Journal of Mathematics and Statistics.

As I discussed earlier, the trick is choosing the next vertex to color. The proposed algorithm uses a combination of saturated degree ordering (SDO) and degree ordering that we explained earlier.

The saturation degree of a vertex is the number of its adjacent differently colored vertices.  The vertices are ordered according to their saturation degree and if two vertices have the same degree the tie is broken by comparing their degree.

int colorNumber = 1; //number of used colors
int numberOfColoredNodes = 0;

while (numberOfColoredNodes < graph.Count)
{
 var max = -1;
 var index = -1;

 for (int i = 0; i < graph.Count; i++)
 {
  if (!Colored(graph.Nodes[i], nodeSet))
  {
   var d = SaturatedDegree(graph.Nodes[i], nodeSet);
   if (d > max)
   {
    max = d;
    index = i;
   }
   else if (d == max)
   {
    if (Degree(graph.Nodes[i]) > Degree(graph.Nodes[index]))
    {
     index = i;
    }
   }
  }
 }
 AssignColor(graph.Nodes[index], nodeSet,ref colorNumber);
 numberOfColoredNodes++;
}

Sudoku Solver

A Sudoku puzzle (9x9) can be thought of a graph with 81 vertices, one for each cell, and two vertices are connected by an edge if they cannot be assigned the same value. For example, all cells in the same row, column or block will have edges between their corresponding vertices.

Given a Sudoku puzzle we can build the associated graph. The given number in the puzzle cane be used to add additional edges to the graph we can then use graph coloring to find a 9-coloring of this graph (colors 1-9)

Points of Interest

The optimal solution in the case of the Sudoku puzzle is to find a coloring using only 9 colors. Some algorithms behave better than others and it is usually a tradeoff between runtime complexity and the number of colors used. Currently not all puzzles can be solved; for some puzzles the algorithm cannot find a coloring that uses only nine colors.  An example of a puzzle that cannot be solved is given below.

I hope you liked this post if you have any questions please leave a comment.