RSS

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

12 Apr
Preface – Casually, I found this terrific article in Google search, this PDF is made by Tom Davis. I left his information including email and Name in my blog subject, just want to lead you to him on the understanding that you’ve gotten theorestic questions related to the Mathmatics of Sudoku. Thanks.    1 Introduction Sudoku is a (sometimes addictive) puzzle presented on a square grid that is usually 9 × 9, but is sometimes 16×16 or other sizes. We will consider here only the 9×9 case, although most of what follows can be extended to larger puzzles. Sudoku puzzles can be found in many daily newspapers, and there are thousands of references to it on the internet. Most puzzles are ranked as to difficulty, but the rankings vary from puzzle designer to puzzle designer.Sudoku is an abbreviation for a Japanese phrase meaning “the digits must remain single”, and it was in Japan that the puzzle first became popular. The puzzle is also known as “Number Place”. Sudoku (although it was not originally called that) was apparently invented by Howard Garns in 1979. It was first published by Dell Magazines (which continues to do so), but now is available in hundreds of publications. At the time of publication of this article, sudoku is very popular, but it is of course difficult to predict whether it will remain so. It does have many features of puzzles that remain popular: puzzles are available of all degrees of difficulty, the rules are very simple, your ability to solve them improves with time, and it is the sort of puzzle where the person solving it makes continuous progress toward a solution, as is the case with crossword puzzles. Figure 1: An easy sudoku puzzle >>>>> The original grid has some of the squares filled with the digits from 1 to 9 and the goal is to complete the grid so that every row, column and outlined 3 × 3 sub-grid contains each of the digits exactly once. A valid puzzle admits exactly one solution. Figure 1 is a relatively easy sudoku puzzle. If you have never tried to solve one, attempt this one (using a pencil!) before you continue, and see what strategies you can find. It will probably take more time than you think, but you will get much better with practice. Sudoku is mathematically interesting in a variety of ways. Both simple and intricate logic can be applied to solve a puzzle, it can be viewed as a graph coloring problem and it certainly has some interesting combinatorial aspects. We will begin by examining some logical and mathematical approaches to solving sudoku puzzles beginning with the most obvious and we will continue to more and more sophisticated techniques. A large literature on sudoku exists on the internet with a fairly standardized terminology, which we will use here: ★A “square” refers to one of the 81 boxes in the sudoku grid, each of which is to be filled eventually with a digit from 1 to 9. ★A “block” refers to a 3 × 3 sub-grid of the main puzzle in which all of the numbers must appear exactly once in a solution. We will refer to a block by its columns and rows. Thus block ghi456 includes the squares g4, g5, g6, h4, h5, h6, i4, i5 and i6. ★A “candidate” is a number that could possibly go into a square in the grid. Each candidate that we can eliminate from a square brings us closer to a solution. ★Many arguments apply equally well to a row, column or block, and to keep from having to write “row, column or block” over and over, we may refer to it as a “virtual line”. A typical use of “virtual line” might be this: “If you know the values of 8 of the 9 squares in a virtual line, you can always deduce the value of the missing one.” In the 9 × 9 sudoku puzzles there are 27 such virtual lines. ★Sometimes you would like to talk about all of the squares that cannot contain the same number as a given square since they share a row or column or block. These are sometimes called the “buddies” of that square. For example, you might say something like, “If two buddies of a square have only the same two possible candidates, then you can eliminate those as candidates for the square.” Each square has 20 buddies.
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.

Advertisements
 
Leave a comment

Posted by on 04/12/2008 in ENTERTAINMENT

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

 
%d bloggers like this: