## The Mathematics of Sudoku I – Tom Davis – tomrdavis@earthlink.net

12 Apr
2 Obvious Strategies Strategies in this section are mathematically obvious, although searching for them in a puzzle may sometimes be difficult, simply because there are a lot of things to look for. Most puzzles ranked as “easy” and even some ranked “intermediate” can be completely solved using only techniques discussed in this section. The methods are presented roughly in order of increasing difficulty for a human. For a computer, a completely different approach is often simpler. 2.1 Unique Missing Candidate If eight of the nine elements in any virtual line (row, column or block) are already determined, the final element has to be the one that is missing.(不愧是数学家，这样的规则多是我修炼很久才悟到，这个B人，一眼就能看穿。这个是我目前解决数独题常用的方法，多数简单题，可以通过目测得到结果。继续读下去，功力在提升中……) When most of the squares are already filled in this technique is heavily used. Similarly: If eight of the nine values are impossible in a given square, that square’s value must be the ninth.

Figure 2: Candidate Elimination and Naked Singles

2.2 Naked Singles For any given sudoku position, imagine listing all the possible candidates from 1 to 9 in each unfilled square. Next, for every square S whose value is v, erase v as a possible candidate in every square that is a buddy of S. The remaining values in each square are candidates for that square. When this is done, if only a single candidate v remains in square S, we can assign the value v to S. This situation is referred to as a “naked single”.(嘿嘿，这个方法我一直再用，确实很管用，特别是在剔除唯一值方面，有很好的功效。) In the example on the left in Figure 2 the larger numbers in the squares represent determined values. All other squares contain a list of possible candidates, where the elimination in the previous paragraph has been performed. In this example, the puzzle contains three naked singles at e2 and h3 (where a 2 must be inserted), and at e8 (where a 7 must be inserted). Notice that once you have assigned these values to the three squares, other naked singles will appear. For example, as soon as the 2 is inserted at h3, you can eliminate the 2’s as candidates in h3’s buddies, and when this is done, i3 will become a naked single that must be filled with 8. The position on the right side of Figure 2 shows the same puzzle after the three squares have been assigned values and the obvious candidates have been eliminated from the buddies of those squares. 2.3 Hidden Singles Sometimes there are cells whose values are easily assigned, but a simple elimination of candidates as described in the last section does not make it obvious. If you reexamine the situation on the left side of Figure 2, there is a hidden single in square g2 whose valuemust be 5. Although at first glance there are five possible candiates for g2 (1, 2, 5, 8 and 9), if you look in column 2 it is the unique square that can contain a 5. (The square g2 is also a hidden single in the block ghi123.) Thus 5 can be placed in square g2. The 5 in square g2 is “hidden” in the sense that without further examination, it appears that there are 5 possible candidates for that square.To find hidden singles look in every virtual line for a candidate that appears in only one of the squares making up that virtual line. When that occurs, you’ve found a hidden single, and you can immediately assign that candidate to the square.（其实就是多次的Virtual line重复检查，就可以发现Hidden Singles，这个不算什么技巧。） To check your understanding, make sure you see why there is another hidden single in square d9 in Figure 2. The techniques in this section immediately assign a value to a square. Most puzzles that are ranked “easy” and many that are ranked “intermediate” can be completely solved using only these methods. The remainder of the methods that we will consider usually do not directly allow you to fill in a square. Instead, they allow you to eliminate candidates from certain squares. When all but one of the candidates have been eliminated, the square’s value is determined.