# Sudoku & Graph Theory

Sudoku is a logic puzzle in which there are 81 cells (vertices) filled with numbers between 1 and 9. In each row, the numbers 1,2,3,..,9 must appear without repetition. Likewise, the numbers 1,2,3,..,9 must appear without repetition in the columns. In addition to the row and column constraints, the numbers 1,2,3,..,9 must appear in the nine nonoverlapping 3×3 subsquares without repetition. So in short, the puzzle board is separated into nine blocks, with nine cells in each block (see Figure 1).

#### Figure 1: Sudoku puzzle.

There are several possible rules you can use to successfully fill in missing numbers. In this article, we examine two rules — Chain Exclusion and Pile Exclusion — for solving Sudoku puzzles. These rules are at the heart of a Windows-based Sudoku solver that we built using Visual C++. (Executables and the complete source code for this solver are available here). The goal of this logical Sudoku solver is to prove that only one possible number can be assigned to each vertex, and to find that number for each vertex in which the number is not defined. Illogical Sudoku puzzles can also be solved, but require guesses (Implementation, OK button).

We refer to possible numbers that should be assigned to a row, column, or one of the nine 3×3 subsquares as a "Permutation Bipartite Graph" or nodes. A node consists of a vector of `n`>1,`n`=2,3,4... vertices and all possible numbers that can be assigned to these vertices, such that there exists at least one possible match between the vertices of the vector and the numbers 1,2,...`n`.

For example, the following are nodes:

```({1,2,3,5},{2,3},{2,3,4},{3,4},{4,5}, n=5
({1,2,3,7},{3,6},{3,4},{1,4},{5,6,7},{4,6},{2,7},{8,9},{8,9}, n=9

```

A possible match for the first vector is easy:

```1 -> {1,2,3,5}
2 -> {2,3}
3 -> {2,3,4}
4 -> {3,4}
5 -> {4,5}

```

A possible match for the second vector is more tricky:

```2 -> {1,2,3,7}
3 -> {3,6}
4 -> {3,4}
1 -> {1,4}
5 -> {5,6,7}
6 -> {4,6}
7 -> {2,7}
8 -> {8,9}
9 -> {8,9}

```

A number can be only assigned to a vertex that contains the possibility of assigning that number. For instance, only the following possibilities are accepted:

```7 -> {2,7} or 2 -> {2,7}.

```

Pile Exclusion and Chain Exclusion provide the basis of logical elimination rules.

To understand Pile Exclusion, consider the following nodes:

```({1,2,3,5},{3,6},{3,4},{5,6},{1,7,8,9},{4,6},{5,7,8,9},{4,6},{6,7,8,9},{1,4}, n=9

```

The numbers 7,8,9 appear only in three vertices:

```{1,7,8,9},{5,7,8,9},{6,7,8,9}

```

Because there is at least one possible match in the Permutation Bipartite Graph, one vertex will be matched to 7, one to 8, and one to 9. Thus, you can erase the other numbers from these three vertices to get the following three augmented vertices:

```{1,7,8,9} -> {7,8,9}
{5,7,8,9} -> {7,8,9}
{6,7,8,9} -> {7,8,9}

```

and the entire Permutation Bipartite Graph becomes:

```({1,2,3,5},{3,6},{3,4},{5,6},{7,8,9},{7,8,9},{4,6},{7,8,9},{1,4}), n=9

```

As for Chain Exclusion, consider these nodes:

```({1,2,3,7},{3,6},{3,4},{1,4},{5,6,7},{4,6},{2,7},{8,9},{8,9}, n=9

```

In the second, third, and sixth positions in the vertices vector, you have:

```{3,6},{3,4},{4,6}

```

Only the numbers 3,4,6 can be assigned to these vertices. From this, you infer that 3,4,6 are not a matching option in any of the remaining vertices. Thus, you can erase these numbers from all the other vertices, resulting in a new, more simple graph:

```({1,2,7},{3,6},{3,4},{1},{5,7},{4,6},{2,7},{8,9},{8,9}, n=9

```

You can do the same thing with {1}, so that the resulting graph is:

```({2,7},{3,6},{3,4},{1},{5,7},{4,6},{2,7},{8,9},{8,9}, n=9

```

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.