Foreword: As an experimental assignment for Discrete Mathematics, I chose to study Sudoku. After testing, I found that automated reasoning for Sudoku is not particularly difficult. I have converted two conventional reasoning approaches into computer code and combined them with randomized inference, resulting in a Sudoku program with decent problem-solving capabilities. In fact, the program in this article could be further optimized to achieve even higher performance (it would only require organizing the code and adding a few more loops and conditional checks), but I am honestly too lazy to continue further. I will share it with everyone as it is. Finally, the author believes that the algorithm presented in this article is closer to human thinking.
Introduction to Sudoku
History
It is said that Sudoku originated from the Latin Square and was developed in the United States in the 1970s under the name "Number Place." It later spread to Japan, where it was popularized and published as a mathematical puzzle game. In 1984, a game magazine titled Puzzle Communication Nikoli officially named it "Sudoku," meaning "each number must be single." Later, Wayne Gould, a New Zealand-born former judge of the Hong Kong High Court, accidentally discovered it while traveling in Tokyo, Japan, in March 1997. He first published it in The Times in the UK, and soon other newspapers followed suit. It quickly became a craze across Britain. He spent six years writing a computer program and put it on a website, making the game popular worldwide.
Sudoku was first introduced to Taiwan in May 2005 by the China Times, where it was serialized daily and received a great response. The Taiwan Sudoku Association (TSA) is also a member of the World Puzzle Federation. Hong Kong introduced Sudoku via AM730 at its launch on July 30, 2005. Mainland China officially introduced Sudoku on February 28, 2007. The Beijing Evening News Intellectual Leisure Sudoku Club (predecessor of the Sudoku Federation) held a ceremony at the News Building to join the World Puzzle Federation, becoming one of its 39 members. (Cited from "Chinese Wikipedia": http://en.wikipedia.org/wiki/Sudoku)
Rules
As shown in Figure 1, a typical Sudoku puzzle provides some numbers in advance, leaving blanks for us to fill. The requirement is that every row, every column, and every "3 \times 3 block" (divided by thick black lines in the figure) must contain the nine Arabic numerals 1, 2, 3, 4, 5, 6, 7, 8, and 9. The answer to the left figure is shown on the right.
For a Sudoku puzzle, the number of pre-filled digits varies, and the difficulty level ranges from low to high. Furthermore, the difficulty of a Sudoku puzzle is not necessarily related to the number of pre-filled digits. Even for a given initial Sudoku, there may be more than one correct answer. Perhaps it is the charm of this uncertainty that has made Sudoku popular worldwide.
Reasoning Logic
There are essentially two methods of reasoning. One is to determine the numbers in the blanks based on the known numbers around them. When deterministic reasoning can no longer proceed, a "trial-and-error method" is used. This involves listing the possible numbers for a blank, randomly selecting one, and then continuing with deterministic reasoning to see if a contradiction arises. If a contradiction occurs, another number is chosen, and the process is repeated.
Deterministic Reasoning
Deterministic reasoning is based on two ideas. The first step for both is to use the method of elimination to list all possible numbers for every blank and then analyze these lists. In an ideal case, if a blank has only one possible number, that number is determined. For example, if a column has only two blanks, and the first blank can be 2 or 9 while the second blank can only be 2, then the second blank is determined to be 2. After filling in the 2, the process is repeated, and the first blank is determined.
Another scenario is when a certain number appears only once among all possible numbers in a row, column, or block; in that case, that number is determined for that specific position. For example, if a row has four blanks where the first can be {1, 2}, the second {2, 3}, the third {1, 3, 4}, and the fourth {1, 2, 3}, since 4 only appears in the third blank and it must appear somewhere in the row, the third blank is determined to be 4.
Randomized Reasoning
The logic of randomized reasoning is even easier to understand. When deterministic reasoning cannot deduce any more numbers, we have to rely on luck. We look for blanks that have only two possible numbers and randomly pick one to fill in. Generally speaking, with this additional number, deterministic reasoning can proceed further. If a contradiction is found during the process, we exclude that number and choose the other one. If no contradiction occurs, the entire Sudoku can usually be completed. In a sense, this is still deterministic reasoning, but because the deduction process involves a degree of randomness, it is labeled "randomized" to distinguish it.
After testing, most Sudoku puzzles of various difficulties can be solved using these two reasoning methods. For some higher-difficulty puzzles, the above process can be repeated to obtain further results. (Of course, relying solely on these two ideas does not always work—refer to the test program below. Since we do not use more advanced reasoning or deeper enumeration, the program’s capability is indeed not perfect.)
Computer Implementation
Programming Logic
The next task is to translate the above logic into program code. The code used in this article is C++.
To implement the aforementioned logic, I used a 9 \times 9 array B (matrix) to store the partial results of the reasoning (using 0 to represent unknown numbers to be deduced) and a 9 \times 9 \times 9 array A ("cubic array") to store the "reasoning process," which represents the possible numbers for each blank. A can also be viewed as a matrix where each element is a vector. The initial value of each element is (1, 2, 3, 4, 5, 6, 7, 8, 9), meaning for any i, j, we have A_{ijk} = k. Every time a number k is determined, the corresponding A_{ijk} values associated with it (in the same row, column, or block) are set to 0.
The program consists of a main routine and three functions: the deterministic reasoning program, the detection program, and the randomized reasoning program, described as follows:
1. Deterministic Reasoning Program: Translates the "deterministic reasoning" logic into computer logic, primarily using nested loops and conditional statements.
2. Detection Program: Written to complement randomized reasoning, it primarily checks whether there are duplicate non-zero numbers among the known numbers in each row, column, and block. This is a necessary condition for a correct Sudoku.
3. Randomized Reasoning Program: Translates the "randomized reasoning" logic into computer logic, primarily using nested loops and conditional statements.
The code and the generated program are placed in the C++ folder of the directory where this file is located (the code was compiled successfully under Windows 8 + Visual Studio 2013). Below are several deduction cases; the Sudoku puzzles were automatically generated by "Sudoku Doctor."
Program Testing
Entry-level Test
Solution by the author’s program (Entry-level)
As can be seen, entry-level Sudoku puzzles can be completed using only deterministic search. This is likely the intended meaning of "entry-level."
Intermediate Test
The above is an intermediate Sudoku generated by Sudoku Doctor. Unfortunately, this program cannot solve this Sudoku. The reason is that the initial numbers are too few. For a human, the higher degree of freedom might make it seem simpler, but for computer reasoning, this freedom often causes difficulties in deduction. Of course, the logic used here could be improved to solve this Sudoku (by using multiple "deterministic + randomized" searches and checks), but this would lead to a significant increase in code length, so it will not be discussed further.
Advanced Test
The above is an advanced Sudoku generated by Sudoku Doctor. Using the author’s program, the final answer can be obtained after three iterations. It should be noted that since associative judgment was not used in the iterations, success is not guaranteed for every example.
Hardcore Test
"Hardcore" implies the highest level of difficulty. Surprisingly, testing a hardcore Sudoku generated by "Sudoku Doctor" required only one pass of deterministic and randomized reasoning. This shows that the deduction logic of this program’s algorithm is not identical to that of Sudoku Doctor. Personally, I believe the algorithm in this program is closer to human thinking.
Conclusion
Source Code and Program Download: Sudoku_Reasoning_Su_Jianlin.zip
When reposting, please include the original address of this article: https://kexue.fm/archives/2527
For more detailed reposting matters, please refer to: Scientific Space FAQ