Solving Simple Sudoku via Graph Coloring

Graph coloring, or vertex coloring, is a very useful problem in the sense that most practical problems can be reduced to this problem. For example, frequency assignment to mobile stations, allocation of registers of a processing unit, making time tables, solving sudoku puzzles etc. Vertex coloring is the process of coloring vertices of a graph such that no two vertices that are connected with an edge is colored using the same color. Chromatic number of a graph is the smallest number of different colors needed to color the vertices of the graph. If a graph is k-colorable, the chromatic number of the graph is less than or equal to k. Unfortunately vertex coloring is an NP-Complete problem and because sudoku puzzle can be reduced to this problem, it’s also NP-Complete. Practically, this means that we cannot possibly know if there can be a polynomial time exact solution for sudoku as long as we don’t know if P = NP or P != NP. For the algorithm presented here, it’s not the best approximation that exists to date. There are other approximations which give better solutions. The program can solve only very easy sudoku puzzles.

In a sudoku puzzle, one should fill a partially filled grid consisting of 9×9 cells with only 9 digits from 1 to 9. However, some conditions should be met: no two same digits are allowed in a row, no two same digits are allowed in a column, no two same digits are allowed in a sub-square.

To solve a sudoku puzzle with graph coloring, we should represent the sudoku grid as a graph. A simple representation could be representing each cell with a vertex and connecting vertices whose corresponding cells are in the same row, the same column or the same sub-square with an edge. In this representation, we also think of each digit as a color. This way, coloring the graph means that solving the sudoku puzzle.

For graph coloring, Dsatur algorithm is used. Actually, Dsatur is more of a heuristic than an algorithm. In each step, the vertex which has the largest number of distinctly colored neighbors is chosen to be colored next and is colored with the color of the smallest index. In the paper by Brelaz, the two additional algorithms, Matula-Dsatur and Dsatur with interchanges, give slightly better results than Dsatur. The Dsatur algorithm is as follows.

  1. Arrange the vertices by decreasing order of degrees.
  2. Color a vertex of maximal degree with color 1.
  3. Choose a vertex with a maximal saturation degree. If there is an equality, choose any vertex of maximal degree in the uncolored subgraph.
  4. Color the chosen vertex with the least possible (lowest numbered) color.
  5. If all the vertices are colored, stop. Otherwise, return to 3.

Each vertex of the graph we constructed has degree 20, considering the row, column and sub-square to which the corresponding cell belongs. Because of this, we can skip step 1. We can also ignore the maximal degree condition in step 3 for the same reason.

The implementation is straightforward and the necessary comments are provided in the code. Thus, the further explanation would be repetitive.

Leave a Reply

Your email address will not be published. Required fields are marked *