Automated Reasoning for Sudoku
Foreword: As an assignment for my Discrete Mathematics course, I chose to study Sudoku. Through testing, I found that automated reasoning for Sudoku isn't actually that hard. I turned two conventional lines of reasoning into computer code, combined them with randomized deduction, and ended up with a Sudoku solver of reasonably good ability. In fact, the program in this post could be further optimized to yield an even more capable solver (just a matter of tidying up the code and adding a few loops and conditionals), but I'm simply too lazy to keep pushing on it, so I'll just share it as it is. Finally, I think the algorithm in this post is one that comes closer to the way we actually think.
Introduction to Sudoku
History
Sudoku is said to have originated from the Latin Square, and developed in the United States in the 1970s under the name Number Place. It later spread to Japan, where it flourished, being published as a mathematical puzzle game. In 1984, a puzzle magazine called Puzzle Communication Nikoli officially named it Sudoku, meaning "a single number in each cell." Later, a New Zealand-born former judge of the Hong Kong High Court, Wayne Gould, stumbled upon it while traveling in Tokyo, Japan in March 1997. He first published it in the UK's The Times, and soon other newspapers followed suit, quickly making it a nationwide craze across Britain. He then spent six years writing a computer program and put it on a website, which allowed the game to spread rapidly around the world.
Taiwan first introduced Sudoku in May 2005 via the China Times, running it as a daily serial feature, which also generated a strong response. The Taiwan Sudoku Association (TSA) is a member of the World Puzzle Federation. Hong Kong introduced Sudoku on July 30, 2005, when AM730 launched and included it from its first issue. Mainland China officially introduced Sudoku on February 28, 2007. The Beijing Evening News Intelligence and Leisure Sudoku Club (the predecessor of the Sudoku League) held a ceremony at the News Building to receive its certificate of membership in the World Puzzle Federation, becoming one of its 39 member organizations. (Quoted from the Chinese Wikipedia: http://zh.wikipedia.org/wiki/数独)
Rules
Classic Sudoku Example 1
Classic Sudoku Example 2
As shown in Figure 1, a typical Sudoku puzzle comes with some numbers pre-filled, leaving blanks for us to complete. The requirement is that each row, each column, and each "3$\times$3 block" (marked off by thick black lines in the figure) must contain the nine digits 1 through 9. The answer to the puzzle on the left is shown on the right.
For a given Sudoku puzzle, the number of pre-filled digits can vary, and the difficulty of the puzzle can likewise vary — but there is no necessary relationship between the number of given digits and the difficulty. In fact, for a given starting grid, there may be more than one valid solution. Perhaps it is precisely this element of uncertainty and charm that has made Sudoku so popular worldwide.
Lines of Reasoning
There are essentially only two modes of reasoning: one is to determine the number in a blank cell based on the known numbers around it (in its row, column, and block); when deterministic reasoning is no longer possible, we resort to a "trial method" — listing the candidate numbers for a blank cell, randomly picking one, and then continuing with deterministic reasoning to see whether a contradiction arises. If a contradiction occurs, we switch to another candidate number and repeat the process.
Deterministic Deduction
Deterministic deduction is based on two ideas, and in both cases the first step is elimination: listing, for every blank cell, all the numbers it could possibly be, and then analyzing these candidate lists. The ideal case is when a blank cell has only one possible candidate number left — in that case the number is determined. For example, suppose a column has only two blank cells; the first blank's candidates are 2 and 9, and the second blank's only candidate is 2. Then the second blank must be 2. After filling in 2, repeating the process would then determine the first blank as well.
The other case is: among all the candidate numbers listed for a given row, column, or block, if some particular digit appears only once across all the candidate lists, then that digit must be the answer for the cell where it appears. For example, suppose a row has four blanks: the first blank's candidates are 1, 2; the second's are 2, 3; the third's are 1, 3, 4; and the fourth's are 1, 2, 3. Since 4 appears only in the third blank's candidate list, and 4 must appear somewhere in the row, the third blank must be 4.
Randomized Deduction
The idea behind randomized deduction is even easier to understand. When deterministic deduction can no longer produce any further numbers, we have no choice but to try our luck. We look for a blank cell that has exactly two candidate numbers, pick one at random, and fill it in. In general, once this number is added, deterministic deduction can proceed further. If a contradiction is found during this process, we rule out that number and try the other candidate; if no contradiction arises, in most cases the whole Sudoku puzzle can then be completed. In a sense, this too is deterministic reasoning — it's just that, because of the randomness involved in choosing which candidate to try first, we call it "randomized" to distinguish it.
Through testing, I found that these two forms of reasoning combined can solve most Sudoku puzzles of moderate difficulty. For some higher-difficulty puzzles, repeating the above procedure once more can yield further progress. (Of course, these two ideas alone don't always work — see the test cases below. Since we haven't employed more advanced reasoning or deeper-level enumeration, the program's capability is admittedly not perfect.)
Computer Implementation
Programming Approach
The next task is to translate the above ideas into program code; this post uses C++.
To implement the ideas above, I used a 9$\times$9 array B (matrix) to store the partial results already deduced (using 0 to represent an as-yet-undetermined cell), and a 9$\times$9$\times$9 array A (a "cube") to store the "reasoning process," i.e., the candidate numbers for each blank cell. A can also be thought of as a matrix whose entries are vectors, with each entry initialized to $(1,2,3,4,5,6,7,8,9)$, meaning that for any $i,j$ we have $A_{ijk}=k$. Whenever a number $k$ is determined, the corresponding $A_{ijk}$ entries in its associated row, column, and block are set to 0.
The program consists of a main routine and three functions: the deterministic-deduction routine, the checking routine, and the randomized-deduction routine, described as follows:
1. Deterministic-deduction routine: translates the "deterministic deduction" reasoning into computer logic, relying mainly on nested loops and conditionals;
2. Checking routine: written to support the randomized-deduction routine, this checks whether any duplicate non-zero numbers appear among the known digits in each row, column, or block — a necessary condition for a valid Sudoku;
3. Randomized-deduction routine: translates the "randomized deduction" reasoning into computer logic, again relying mainly on nested loops and conditionals.
The code and the compiled program are placed in the c++ folder in the same directory as this file (the code compiles successfully under Windows 8 + Visual Studio 2013). Below are several test cases, with the puzzles generated automatically by "Sudoku Doctor".
Program Testing
Beginner-Level Test
Beginner-level Sudoku generated by Sudoku Doctor
shudu-rumen-2
The author's program's solution (beginner level)
As can be seen, a beginner-level Sudoku can be completed using deterministic search alone. This is perhaps what makes it "beginner" level in the first place.
Intermediate-Level Test
Intermediate-level Sudoku generated by Sudoku Doctor
Above is an intermediate-level Sudoku generated by Sudoku Doctor, but unfortunately, my program is unable to solve it. The reason is that the puzzle starts with too few given digits — for a human, this might actually feel simpler due to the higher degree of freedom, but for computer reasoning, this same freedom often creates difficulties. Of course, the criteria used in this post could be improved to solve this puzzle (by using multiple rounds of "deterministic + randomized" search and checking), but this would cause the program's code length to balloon, so I won't go into further detail here.
Advanced-Level Test
Advanced-level Sudoku generated by Sudoku Doctor
Above is an advanced-level Sudoku generated by Sudoku Doctor. Using my program, three iterations are enough to reach the final answer. Note that since no cross-referencing checks are used during the iterations, a different example might not necessarily converge successfully within the same number of iterations.
Expert-Level Test
Expert-level Sudoku generated by Sudoku Doctor
The author's program's solution (expert level)
"Expert level" here refers to the highest difficulty tier of Sudoku, the level for true enthusiasts pushed to their limit. Surprisingly, when tested on an expert-level puzzle generated by "Sudoku Doctor," it only took a single round of deterministic and randomized deduction to solve it. This suggests that the reasoning approach in this post doesn't quite align with the logic used by Sudoku Doctor itself. Personally, I believe this program's algorithm comes closer to the way humans actually think.
Finally
Source code and program download: Sudoku_Deduction_SuJianlin.zip
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.