Channels ▼
RSS

C/C++

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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 

Video