奋战整整四天四夜，终于在今天上午12点，结束了美国数学建模竞赛。我们做的是B题，定义“数独”（Sudoku）游戏的难度和生成给定难度的问题。

你将在本文中找到以下内容：1. What is Sudoku? 2. How to solve Sudoku puzzles using inference techniques? 3. How to solve Sudoku using a computer? 希望这些内容能够将“数独”这个风靡世界的问题展示给诸君。

What is Sudoku?

Sudoku is a logical puzzle of filling a 9 by 9 grid satisfying the following requirements:

l         Only digits of 1~9 can be filled in each cell.

l         Each digits can appear only once in each row, each column and each box. (see the following Figure)

“Box” in the above line refers to the nine three-by-three building blocks of the gird. Those who happen to be familiar with relevant mathematics will realize that such a so-called Sudoku puzzle is just a special form of Latin grid with the additional requirement of each box.

Figure 1

How to solve Sudoku puzzle using inference techniques?

There are numbers of inference techniques developed for a human in solving Sudoku puzzles. However, most of them are based on the mark-up techniques.

 Figure 2 Illustration for mark-up

Such technique is illustrated above. Observe the rows, columns and boxes, see what digits left can be filled and mark the cell with such numbers. For example, for the left-top cell, by observing the first row, digits of 8, 6 and 4 can be filled into this cell, and by observing the first column, digits of 9, 3 and 4 can not be filled, and finally by observing the left-top box, digits of 8, 9 and 5 can not be filled. So we mark the cell with digits left, that is, digits of 1, 2 and 7. Do the process one cell after another for all the cells remained blank, and get a grid as illustrated in Figure 2.

To facilitate presentation, I will call the digits filled in the mark-up process as candidates, meaning possible digits for the cell.

Getting this ready, we are at a position to use the following inference techniques:

1.       Naked Single

Observe possible candidates in each cell. If there is only one candidate, then the cell can be completed by filling the candidate. For example, candidate in row 4 column 8 and candidate in row 8 column 3.

Figure 3 Illustration of Naked Single

2.       Hidden Single

Observe possible candidates in cells of each row, column and box. If there is only one candidate bearing a particular digit which appears only once in its row, column or box, then this candidate can become the solution of the cell. For example, in the cell of row 7 column 9, candidate 4 appear only once in its row. So 4 is the solution of its cell.

Figure 4 Illustration of Hidden Single

3.       Naked Pair

If two double-candidate cells in the same row, column or box contain identical candidates, neither of these two digits can serve as a candidate for the other cells in the same row, column or box. For example, two cells of row 1 and row 2, column 7, have the only two identical candidates. Then all the 7’s in candidates in the top-right box and in the 7 column must be “disqualified”. The reason for this is: for the two double-candidate cells, the two candidates must serve for the final choices of the cells, one for each cell, though which one for which is not clear yet. But after the selection is made, other candidates in the same row, column or box are disqualified.

Figure 5 Illustration of Naked Pair

4.       Hidden Pair

If all the candidates of two digits appear only in two cells in the same zone, then all the other candidates in these two cells can be deleted. I will leave it as an exercise to the reader to think about why this process is reasonable.

Figure 6 Illustration of Hidden Pair

And it seems that there are many more techniques in solving the puzzle (dozens of them).

Here is a list of some of them (but I will not provide explanations and illustrations for them due to lack of familiarity).

You are encouraged to master some of them to solve puzzles yourself.

How to solve Sudoku using computer?

The computer can solve a given puzzle with considerable ease using searching method.

Codes can be found in internet.

In the end, the solution of the first puzzle is provided:

     2     8     1     3     6     5     7     4     9

     9     5     6     1     4     7     3     2     8

     7     3     4     8     9     2     6     1     5

     1     4     7     5     2     8     9     6     3

     5     2     9     7     3     6     4     8     1

     3     6     8     4     1     9     2     5     7

     6     1     5     2     7     3     8     9     4

     4     7     2     9     8     1     5     3     6

     8     9     3     6     5     4     1     7     2

This is the end of the article.

祝：

新年快乐！

Special Thanks to子健 for his preparation of Figure 1.