Can You Effectively Solve Sudoku?
Ali Eshghi, Rocío Jaime, Emily Kim, Annika Miller
What is Sudoku?
Sudoku is a logic puzzle filled with numbers {1–9}. In each row, column, and block, every number must appear once and only once. While sudoku puzzles of other sizes can be used, the 9x9 sudoku puzzle is the most standard. Sudoku puzzles start out partially filled in and it is up to the solver to fill in the rest while following the rules.
What is Graph Theory?
Graph theory is just the study of graphs, and graphs are defined as vertices (also called nodes) connected by edges (or lines). Graph Coloring is one branch of graph theory that involves rules for coloring in the vertices of a graph. Each vertex must be colored in such a way that no adjacent vertices, that is any vertices that are directly connected by an edge, have the same color. A graph that follows these rules and successfully colors all of the vertices is called a proper coloring.
How are Sudoku and Graph Coloring Related?
A sudoku board can be represented as a graph where each square, or potential number, is represented by a vertex. Any squares that are in the same row, column, or block as each other will be connected by an edge. The vertices in the graph can be colored, where each number {1–9} is represented by a different color vertex. Following the rules of graph coloring, no connected vertices may share a color. For our sudoku-turned-graph, this means the same thing as no boxes in the same row, column, or block as each other may share a number. By making a proper coloring where no connected vertices have the same color, a correct sudoku puzzle can be completed.
How does this work?
Let’s walk through an example of how this works on a 4x4 sudoku graph. We will start with the grid with each number 1–4 associated with a color. Here that means 1 is green, 2 is purple, 3 is blue, and 4 is red.
We will then assign each box, or “vertex” a number starting from 1 in the upper left hand corner and going to 16 in the lower right.
These numbers are put into the below graph. It is important to note that each set of four in the graph represents a “box” and each group of four vertices are all connected by an underlying edge which is difficult to notate in a 2D graph.
We then gradually work our way through the graph making sure no connected vertices have the same color. You can see that we start by filling in the 4th color in the top row and left column. We are then able to fill in nodes 4 and 13 because the three other nodes in each of their sets are already colored. We continue filling in the graph following these steps until it is completed.
Once the graph is completed we can return to the original sudoku grid and fill it in.
The final step is to replace the colors with their associated numbers.
Congratulations! You have now completed a sudoku puzzle.
Another Way to Interpret Sudoku Using Graph Theory
A solution for Sudoku can be found by reducing it to an instance of an independent set. In graph theory, a set S of vertices is considered an independent set if there are no edges connecting any of the vertices. In the graph below, we see that the vertices labelled 0, 2, and 4 form an independent set, because they do not share any edges. In this blog we will discuss how to verify a proposed solution to Sudoku using an independent set.
How it Works
In a 4x4 puzzle, we know a valid solution will include exactly 4 of each number (1,2,3,4). We can convert a puzzle into a graph with 16 labeled vertices (four 1s, four 2s…). Numbers that share a box, row, or column are connected by an edge.
When checking a solution, we want to make sure that none of the vertices labeled with the same number share an edge. This implies that they do not have any overlapping rows, columns or boxes. In other words, we want all the 1s to form an independent set, along with the 2s, 3s, …etc. Below we see a proposed solution.
Now when verifying our solution using the graph, we see that all the 1s, 2s, 3s, and 4s form an independent set.
Since all the individual numbers for an independent set, we know that our solution to Sudoku is valid. Voila!
Motivation to Solve Sudoku
Throughout quarantine some of us have been playing a lot of sudoku, and have started to wonder about how the game works. Our group all took algorithms this past year and were interested in the applications of graph theory and algorithms on common puzzles. Why are some puzzles so much harder than others? What other approaches are there to solving sudoku puzzles? How can we build a sudoku solver to “cheat” the system when we have spent an obscene amount of time on the sudoku app and are starting to get frustrated? These are all questions we were interested in answering and which inspired our motivation in this topic.
Our Evaluation
We can see that the sudoku grid is essentially a graph but one that’s just been drawn in a slightly unusual and unfamiliar way. In the example shown earlier we will have 16 vertices, with each “box” designated one color. We are able to use graph theory, specifically graph coloring, to help us solve sudoku.
However, we do recognize that even though we can use graph coloring to solve sudoku in a relatively efficient way, we do also recognize that in terms of actually using graph theory when solving it is not practical.
As said above, we have found that the reduction shown cannot be solved in polynomial time and that this is another way of solving sudoku.
Key Contribution
We found that there was a graph coloring algorithm which used a greedy algorithm approach, by Dr. Hussein Al-Omari and Khair Eddin Sabri named New Graph Coloring Algorithms. Of course, with the background of algorithms and extensive theoretical computer science, this is able to help solve sudoku in a way that is a little more complicated than shown above.
This idea about graph theory and sudoku also helped Herzberg and Murty to prove theorems about sudoku in their paper Sudoku Squares and Chromatic Polynomials. As we can see, sudoku (and other games), have asked questions on how to solve these problems, and many people are able to come up with algorithms and even use the knowledge we learn in discrete math and theory of computation to help answer some of these questions.
Introduction of sudoku and graph coloring, relationship between sudoku and graph theory written by Annika Miller; walk through of an example of using graph coloring on 4x4 sudoku graph written by Ali Eshghi; walk through of a reduction to an instance of an independent set written by Rocío Jaime; evaluation, key contribution, and Medium post written by Emily Kim.
Sources
3. https://medium.com/@lukecoope/generalising-sudoku-k-distant-graph-colouring-puzzles-47c6af5165ca
4. https://core.ac.uk/download/pdf/25782121.pdf
5. https://www.ams.org/notices/200706/tx070600708p.pdf
6. http://www.ams.org/news?news_id=484
7. http://www.cs.kent.edu/~dragan/ST-Spring2016/SudokuGC.pdf
