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 kcoloring (e.g. coloring (1) in the above example is a 3coloring while coloring (2) is a 5coloring).
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 nonadjacent 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 35 until the list is empty.
6 .Remove vertex V from the graph
7. Repeat steps 16 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 AlOmari 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;
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 9coloring of this graph (colors 19)
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.