Mathematics and Sudokus: Sudokus as Graphs

While there are mathematical aspects to Sudoku, this game is not one of the main objects studied by research mathematicians, and probably never will be. Techniques like enumeration of possibilities, or the estimates from section 1, are of a very general nature and can be used in a wide variety of settings.

Graphs, which are studied at an introductory level in some highschool classes, are yet another way in which theory about Sudokus was developed on an abstract level many years before the puzzles became popular in the western culture.

What is a graph?

Definition: A graph is a collection of points, also called vertices, together with lines connecting (some of) them, also called edges.

Graphs can have one vertex or many, and may or may not have edges. Below is an example of a graph (picture by David Eppstein, public domain). While a graph is an abstract object, the vertices and edges often represent something, for example town and roads connecting them:

Activity 11: If this is the first time you encounter graphs, run a picture search for “graph math” on the web to find some further examples of graphs. Also find out what a “directed graph“ is. Give an example of a system or situation one could model well with a directed graph. Do the same for a “weighted graph”.

How to represent a Sudoku as a graph

Enumerate the 81 cells of the Sudoku board with numbers from 81. Then the graph associated with a Sudoku puzzle consists of 81 vertices (one for each cell of the board), together with edges as follows: two vertices are connected by an edge if the cells that they correspond to are in the same column, row or 3x3 box. We have thus represented the Sudoku grid as a graph. With 81 vertices and several hundred edges it would be a big graph if one wanted to draw it, so let us just think about it without attempting to produce a graphical representation. What about the numbers in the cells of the Sudoku puzzle, how do we represent those? Assign each number from 1 to 9 a color. Now color the vertices corresponding to cell that contains a given number in the color of the number.

It is now easy to see that completing a Sudoku puzzle without vioating the Sudoku condition is equivalent to coloring the vertices of the corresponding graph while ensuring that no two adjacent vertices have the same color.

Why is this representation useful?

Graphs have been studied for several hundred years (Wikipedia http://en.wikipedia.org/wiki/Graph_theory#History Euler worked on the Königsberg Bridge problem in 1735. Check out the Wikipedia article, it’s a fun problem that can be solved without any higher mathematics). Nowadays, graph algorithms are used when a routing tool calculates the optimal route from one city to another, or when an electricity company wants to calculate if and where it needs to build more power lines. While those are just two examples, It is clear that in these settings, graph theory has a strong economic relevance. As a result, graph theory has become one of the major fields of modern mathematical research.

Due to the general nature of many theories in mathematics, a lot of knowledge that has been established in graph theory is applicable to Sudoku puzzles, although it was not developed with Sudokus in mind. To give an example: In 2007, the mathematicians Herzberg and Murty (see References) developed a method to calculate the number of ways in which one can color the vertices of a partially colored graph in such a way that no two adjacent vertices have the same color. This result was not developed with puzzles in mind, but it applies immediately to Sudoku puzzles once one has recognized that a Sudoku puzzle can be presented as a graph coloring problem. Once you know that the method of Herzberg and Murty exists, you can use their work without much more thinking to figure out how many solutions a given Sudoku puzzle has.

Activity 12: Some famous problems in graph theory are the Chinese postman problem, the shortest path problem, the traveling salesman problem, and the max-flow min-cut theorem. Find out what each of them is about. State where you see applications of them outside mathematics,