文章來源: http://onigame.livejournal.com/ 

文章連結: http://onigame.livejournal.com/20626.html

作者: Wei-Hwa Huang   2006/03/20

A few months ago, I wrote a long entry here about the "Sudoku Sledgehammer". It caused a little bit of discussion, but the problem that most people reported is that it could really use a few more examples. So, during the last Gathering for Gardner, I was preparing some images for this entry, when Ed Pegg, Jr. looked over my shoulder and said that I should present them at the Gathering, and he graciously gave up some of his presentation time for it. Quite a few people came up to me afterwards thanking me for an interesting presentation. (I think it was mostly because it was short.)
一個多月前, 筆者在這個網誌中, 寫了有關於『Sudoku Sledgehammer』的長篇文章。它引發了一些討論, 但問題在於多數的人回應都表示它應該可以應用在更多的例子。所以, 在最近的 Gathering for Gardner, 筆者為了這篇文章準備了一些圖片, 當 Ed Pegg, Jr. 從筆者的東西再延伸, 並認為筆者應該要在 Gathering 發表這些內容, 同時, 他也體恤地放棄了一些他為此事呈現的時間。也有相當多的人為此如此有趣的呈現解釋, 向筆者表達謝意。(譯者注:這是翻譯得最爛的一段, 居然就在開頭….)

Anyway.
反正….

The example I’ll use is the final puzzle from the World Sudoku Championship:
筆者將拿這次世界盃數獨賽, 最終回合的題目, 當成解釋的範例
 
(I’m going to assume that you know what a Sudoku puzzle is and what the rules are.)
(筆者假設看這篇文章的人, 也就是閣下, 了解數獨為何物, 並且清楚它的規則)

Bit of a note on how the WSC worked. About 100 participants had one day of solving multiple Sudoku puzzles, and the top 9 were chosen to be in the playoffs the next day. Each round of playoffs lasted 15 minutes, and at the end of the 15 minutes, the player with the lowest "score" (correct squares minus incorrect squares) was eliminated. This went down until the field was of size 3, and then the last puzzle determined the final ranking.
先在這兒做個說明, 解釋一下 WSC (World Sudoku Championship 世界盃數獨賽)進行的流程。大約100個參賽者會先進行一天的比賽, 解開各類變體數獨的題目。前九名的參賽者, 將有機會參加第二天的決賽。決賽的進行, 每一回合15分鐘, 而每回合15分鐘結束後, 當回合分數最低的玩家就得要下台一躹躬(分數的計算方式為正確的格數扣掉錯誤的格數) 。如此回合一輪接著一輪, 直到淘汰剩下三名參賽者, 而此時下一個題目, 將決定最後的贏家。

Incidentally, the best Sudoku solver in the world (in my opinion) was eliminated in the penultimate round, by a puzzle that was (in my opinion) too difficult to really be a good gauge of logical ability. (Puzzle competition organizers tend to think that one really difficult puzzle is a better gauge of ability among top players than several medium-level ones. I think that’s a mistake; all that happens is that the top players realize that their best chance of solving it in a short amount of time is to start guessing when they get stuck.)
順道提一下, 這世上最厲害的 Sudoku 解謎者(筆者個人觀點), 在決賽倒數第二回合時….被淘汰了。原因在於當回合的題目(筆者個人觀點)太難了, 實在不是一個適合當做檢測邏輯能力的標準。(似乎主辦單位是想說, 對於能力強的參賽者而言, 一個超難的謎題比起數個中等難度的題目, 具有更佳的鑑別能力標準。筆者認為這種想法是有問題的, 這只會造成以下的情況 – 等級高的參賽者將會認知到一件事 – 他們若想要在短時間之內解出題目, 最好的辦法就是『猜』, 一路猜, 猜到碰到瓶頸為止)

But I digress. Anyway, when most beginners (especially computer-oriented ones) encounter a puzzle, they tend to create something like:
好吧, 筆者有點離題了。當多數的新手(尤其是那些玩電腦類題型的)碰到一個題目時, 他們會傾向把題目搞成這種模樣:
 
Each of those little numbers I’m calling a Placement. For instance, the upper-left corner, being empty, can contain a 4, 6, 8, or 9. (I’ve done the "obvious" and eliminated 1, 2, 3, 5, and 7 already.)
每一個小數字, 筆者把它稱做一個『Placement』。舉例來說吧, 像是在左上角的那個格子, 原本是空的, 但它可以放入4, 6, 8 或 9(筆者已將明顯可剔除的1, 2, 3, 5, 和 7 淘汰)

If you look at any "How to Solve Sudoku" book or website, you’ll see that it tries to teach you lots of different rules on the sorts of deductions you can make regarding these puzzles. One of my discoveries (or rediscoveries, although I don’t know of anyone else who has mentioned it) is that almost all of these rules are part of a very general rule, which I call the Sledgehammer.
如果你有看過像是『如何解數獨』這類的書或是網站, 你會發現, 它們都在教你大量各種不同的剔除數字技巧, 協助你去解數獨題目。而筆者的一個發現(或稱做『老調重彈』, 雖然我並不曉得有任何人曾提過這類的內容), 就是幾乎所有提到的技巧, 都是從一個非常普通的策略延伸出來, 而這個策略, 筆者稱之為 Sledgehammer。

Here’s a method to visualizing the Sledgehammer:
這兒用個方法, 讓Sledgehammer 這個理論具體化一點:
 
Here we have a Venn diagram with 9 elements and 4 sets. We’re trying to solve a constraint-satisfaction puzzle by removing elements, and the constraint we have is that there is exactly one element in each set.
這兒我們有一個維恩圖, 裏面有九個元素, 以及四個組別。我們現在要把一些元素移除, 試著解開一個『要滿足限制條件』的謎題, 而題目中限制的條要是 – 每個組別最後都要剛好留下一個元素在裏面。

In other words, try to pick some items in that diagram above such that each loop has exactly one item in it.
換句話說, 就是要拿掉一些東西, 讓上面的這個圖中, 每個環裏都剛好只有一個東西。

Try it now.
動手做吧!!
 
You’ll find that there are several solutions (3, in fact), but they all end up with two stars. The square and triangles are never used. A more general statement might be:
Suppose we have two "Premises" (the red loops), which don’t share any elements in common. Suppose we have two "Conclusions" (the green loops), which can share elements in common. Finally, suppose that all the elements in red are also in green (in the example, the stars and square). Then, we can conclude two things:
你將會發現答案不只一個(事實上, 有3個); 而且, 結束時的答案 – 全是兩個星星。不管是正方形或三角形都不會用到。一個更口語化的說明如下:
假定我們有 2 個『Premise』(即紅色的環), 而它們之間並沒有任何共同的元素。
假定我們有 2 個『Conclusion』(即綠色的環), 而它們之間有共同的元素。
最後, 再假定所有的元素只要有在紅色的環內, 就一定有落在綠色的環內(在範例中, 就是星星和正方形), 那麼, 我們將可推論以下兩件事:

• All the non-red green elements (in the example, the triangles) are not in the solution.
• All elements in more than one green loop (in the example, the square and one of the triangles) are not in the solution.
• 所有沒在紅色環內, 而在綠色環內的元素(在範例中, 就是三角形)都不會是答案。
• 所有在超過一個綠色環內的元素(在範例中, 就是正方形和一個三角形)也不會是答案。

Why? Well, the elements in red loops already account for two symbols in the solution, and so...
為什麼咧??好吧, 在紅色環內的物件已經有兩個會列在答案中, 那麼….

• ...anything non-red chosen would end up having more than two elements chosen for only two green loops; and
• ...any "double-counted" elements would result in some green loop with too many elements.
• 任何紅色環沒包含的元素, 若是列在答案中, 則將會有超過 2 個元素存在於 2 個綠色環中, 而且…
• 任何『重覆計數』的元素將會讓綠色環最後留下超過指定數量(一個)的元素

Note that the number two was arbitrary; we can replace the two with any other number and it will work just fine.
請注意, 這裏用數字2只是個示範, 並不是只有數字2才能符合要求。我們把2 換成其他的數字時, 還是一樣行得通。

Let’s see how this applies to some deductions in our Sudoku puzzle.
讓咱們再來瞧瞧, 這理論怎麼用在數獨的題目上, 去剔除掉不合的數字:

Here’s probably the most basic rule, sometimes called a "Single." The cell labeled J doesn’t contain 1, 3, 7, or 9 (because of the row), and it doesn’t contain 2, 4, 5, 6 (because of the column). Therefore, we know it must contain an 8.
這裏介紹的是一個蠻基本的技巧, 有時稱它為『Single』。 格子 J不可以放進1,3,7,9(這些數字在同橫列中已存在), 也不能進進2,4,5,6 (同直行中已經有這些數字了) 。嗯, 我們可以看出只有8 才能進進格子J中。

The relevant set diagram looks like this:
讓我們把它畫成對應的關係圖, 應該是長得像下面那樣:
 
In this diagram, "A5" means "5 goes into the cell labeled A", "B5" means "5 goes into the cell labeled B", and so on. Each one of those is a Placement (defined above).
在圖當中, A5 代表的是『數字 5 填入格子 A』, 至於B5則是『數字 5 填入格子 B』, 以此類推。而每一個元素, 都是『Placement』(Placement 之前已有定義) 。

The first four tall loops are "Column-based Rules". For instance, the first one, containing A5 through J5, can be thought of as the rule "there is exactly one 5 in the column ABCDPQRSJ."
前四個直條的環, 是『根據直行而得到的 Rule』, 舉例來說吧, 像是第一個直條的環, 包含了從A5到J5 的Placement, 就可以把它視為『在直行ABCDPQRSJ 當中, 剛好有一個5』這個 Rule。

The next four tall loops are "Row-based Rules". For instance, the last one, containing E1 through J1, can be thought of as the rule "There is exactly one 1 in the row EFGHJKLMN."
後四個直條的環, 則是『根據橫列而得到的 Rule』, 舉例來說吧, 像是最後一個直條的環, 包含了從E1到J1 的Placement, 就可以把它想做『在直行EFGHJKLMN 當中, 剛好有一個5』這個 Rule。

There are also "Region-based Rules", but not in this example.
當然也會有像『根據區塊而得到的 Rule』, 不過這個例子中並沒有用到。

All the other loops are "Cell-based Rules". For instance, the bottom loop, containing J5 through J8, means "there is exactly one digit in cell J". The small loop at the top containing only A5 means "there is exactly one digit in cell A" -- normally it would contain A1, A2, A3, A4, A6, A7, A8, and A9, but we’ve eliminated those since it was a given that cell A contained a 5.
其他的環, 都是『根據格子而得到的 Rule』, 舉例來說, 在最下方的環, 包含了從 J5 到 J8 , 就是指『格子 J 中只會剛好有一個數字』這條 Rule。而像是只包含了 A5的小環, 則代表了『格子 A 中只會剛好有一個數字』這條Rule。但是, 一般來說不是應該要包含 A1, A2, A3, A4, A6, A7, A8, and A9嗎??哦, 因為題目已經告訴我們格子A是 5, 所以其他的 Placement 我們就可以刪掉了。

Now, let’s look at a Premise-Conclusion pair:
現在, 讓我們來看看一個 Premise-Conclusion 的組合:
 
The Sledgehammer rule applies here; there’s one Premise (in red), one Conclusion (in green), and all the red is part of the green. Therefore, we can eliminate all the non-red green elements. Doing this for all the vertical pairs results in:
開始來應用 Sledgehammer 吧: 現在有一個 Premise(紅色), 一個 Conclusion(綠色), 而且所紅色環內所有的元素都在綠色環中。因此, 我們可以把在綠色環內, 但不在紅色環內的元素全數剔除。這樣一直處理每個組對, 直到如下圖的結果
 
Now, the last horizontal set has only one element left. Whenever that happens it means that we have determined a Placement that must be in the solution, so we can write 8 into the space labeled J.
現在咧, 所有直條的組對都只剩下了一個元素。當結果出來, 我們就可以決定那一個 Placement必然就是解答 – 8 填入格子 J

Let’s look at a different basic heuristic:
再讓我們看看另一個基本的訣竅:
 
This heuristic is sometimes called a "Naked Single." The 7 in cell A and the 7 in cell E mean that a 7 cannot be in cells B, C, D, or G. Since F is the only unoccupied cell left in the bottom Region, a 7 must go into cell F.
這種訣竅常被稱之為『Naked Single』, 有一個7 在格子A, 又有一個 7 在格子 E, 所以這樣看來, 在格子 B, C, D 或 G 全都不可能再出現7。然而在下方的九宮格區塊中, 這樣一來, 只剩下格子 F 沒有這個限制, 所以, 數字 7 一定填入格子 F。

Here’s what the set diagram looks like:
對應上面策略, 畫出來的圖應該是這樣:
 
There’s much more of a variety of Rules here. I’ve gotten a bit lazier here and didn’t bother writing out all the Placements in the BCDE row and the ABG column, although I did write out all the Placements in the "F has a digit" Rule.
這看起來, 比之前的那個圖, 有更多不同的 Rule 在裏面。就容許筆者偷懶一點, 不再對 BCDE 橫列及 ABG 直行中的 Placement 多做贅述。不過, 筆者還是把『必有一個數字在格子F裏』這條Rule 當中的所有 Placement 全寫出來了。

Looking for Premise-Conclusions:
先找出 Premise-Conclusions:

Here we have two Premises (in red) and two Conclusions (in green). Note that in this particular case we could’ve chosen them separately, but it doesn’t really matter; we can easily remove the non-red green elements:
這兒我們看到了2個Premise(紅色)以及2個Conclusion(綠色)。請注意, 在這個特定的例子中, 我們不能像上個例子那樣, 分成1對1對地來看, 但在應用理論上則沒有差別; 我們仍可很輕易地把那些在綠色環內, 但不在紅色環內的元素全數剔除
 
At this point we could just write 7 in the F cell, but just to be completist I’ll point out that the sledgehammer also can draw an "obvious" conclusion that once we know a 7 goes in F, nothing else can go in there:
到了這兒, 我們應該可以把 7 填入格子 F中, 但注意, 這並不算完成。使用 Sledgehammer 理論, 筆者可以更明確清楚地畫出它們的關連, 並且清楚指出除了7以外, 沒有其他的數字可以填入格子F。

Okay. Now it’s time for a medium-level heuristic:
好吧, 現在讓我們來談談『中級程度』的訣竅:
 
This heuristic is called Pointing Pairs by some. It goes: Look at the right Region. Because of the 2 in A and the 2 in E, we know that the 2 can’t go in C, F, or G, so that means the 2 must be in B or D. That means that the 2 in that column is in B or D, so a 2 cannot be in H, L, or N in the lower-right Region. Also, because of the 2 in A and the 2 in K, there cannot be a 2 in J, M, or P. Therefore, the 2 in the lower-right region must be in Q.
有人把這訣竅稱之為『Pointing Pairs』。來膲膲它是怎麼分析的: 先看一下在右方的區域, 因為有一個2在格子A, 又有一個2在格子E, 所以我們可以很確認2 不會出現在格子 C, F 或G – 也就是説, 2 一定要出現在格子B或 D。這代表了什麼呢 – 2 會出現在B 或 D 的那個直行, 也就是在右下角的九宮格區塊裏, 2不會出現在格子H, L 或 N中。另外, 因為2 出現在格子 A及格子K, 所以2也不會出現在格子 J, M 或P。最後我們得到一個結論 – 在右下角的九宮格區塊, 2一定要出現在格子Q。

That’s quite a mouthful. Let’s look at the set diagram:
這實在太冗長了, 只是在用嘴巴說, 讓我們看看對應的圖樣:
 
I’m not going to explain the sets this time; you should be able to figure them out for yourself. Here’s a Sledgehammer coloring:
這回, 筆者可不再多作解釋了, 看官們應該可以自己理解。以下是依據 Sledgehammer 所畫出來的紅色及綠色環:
 
This allows us to eliminate C2, F2, G2, J2, L2, M2, and P2.
這樣一畫, 我們就可以把C2, F2, G2, J2, L2, M2, 和 P2剔除掉。

As an aside, it’s worth pointing out that often after applying Sledgehammer for a while, you’ll end up with identical sets:
題外話, 經常在用過 Sledgehammer 理論幾回後, 你將會得到像這樣的包含同一個元素的組合:
 
Here the two purple loops are identical, and really don’t need to be both drawn to clutter up our diagram. (If you ever read my source code that implements the Sledgehammer and wonder what the "Enslave" function is supposed to do... now you know.)
這裏有2個紫色環, 都包含了同一個元素, 而且我們其實不用去分誰紅誰綠(如果你有看過筆者執行Sledgehammer的程式碼, 而且想知道『Enslave』這個函式是做什麼用的….現在你應該知道了)(譯者注: 沒看過~~所以也不曉得什麼 Enslave:p)
 
After cleaning up our diagram it’s pretty easy to see another Sledgehammer application:
來整理一下我們的圖….呃….現在應該比較容易看出哪裏還可以應用 Sledgehammer:
 
And after eliminating H2 and N2, we’re done.
在把 H2 和 N2 移除掉之後….咱們大功告成。

In the actual compeition, if you had paused time and looked at all three finalists’ grids at the 5-minute mark, you would’ve seen this:
在這次的比賽中, 要是你在決賽開始後5分鐘宣告比賽暫停, 然後去審視三個參賽者的看板。你會發現你看到完全一樣的答案:
 
You see, at this point, we were all stuck! There’s no obvious way as to how to proceed; certainly none of the medium-level heuristics were getting us anywhere. (Except for placing an 8 in cell U ... forgot that one when I was making the diagram.) Faced with possibly stiff competition and only 10 minutes left, each of us guessed; with the championship determined by the luckiest guesser.
瞭解了吧, 到了這兒, 我們全都卡住了!!接下來, 我們找不到有很明顯的方法可以進行下去; 的確, 沒有一個中級程度的訣竅可以拯救我們離開這個僵局的泥沼。(除了在格子U 放入數字 8, 當筆者在畫這張圖時, 這裏忘了填上去)。面對這場冷到結凍的賽局, 剩下的時間只有10分鐘, 每個人都…開…始…猜!!最後的贏家, 就是最Lucky 的幸運兒。(譯者: 如果比賽有三個人, 第一名是最幸運的, 那第三名不就是最….??:P)

Ah, but if only any of us had seen this set diagram:
啊~~但要是我們三個人當中, 有任何的一個人, 看出了以下的這個關係圖的話….
 

(點選此處觀看此圖)
Note here that to simplify the diagram a bit, I’ve removed the trivial Placements from the Cell Rule sets. for example, there’s a set at top center with D6 and D9; properly, it should also have D1, D2, D3, D4, D5, D7, and D8, but since those digits can be eliminated from D by Row, Column, and Region Rules, I’ve not bothered to draw them in.
請注意, 這裏有點把圖給簡化了。筆者把比較不重要的Placement 從『根據Cell 而得的Rule』中移除掉。像是, 在上圖的中上方有一個D6 和D9的組合環; 一般來說, 它裏面應該還有 D1, D2, D3, D4, D5, D7, 和 D8。不過根據格子D 所位在的橫列, 直行以及區塊, 我們可以把它們給移除。就這樣, 筆者就不再多畫了。

You may want to stop here and check the loops to make sure you understand each of them.
呃….你大概會想要先在這兒停一下, 然後一個一個環去看去對應, 確定你搞懂了每個環的內容和含義….

As it turns out, there are three advanced deductions you can make here:
結果是….你會找到3個進階版的刪除技巧:
 

(點選此處觀看此圖)
The top one is known as an X-Wing: Since there’s a 9 in D or Z (because of the column), and a 9 in H or CC (because of the column), you can deduce that there’s no 9 in E, F, G, AA, or BB.
最上方, 就是被稱為X-wing 的技巧; 既然數字9 會出現在格子D 或Z(因為直行的緣故), 而且數字9 也會出現在格子H 或CC(因為直行的緣故), 你就可以把數字9 放進格子E, F, G, AA, 或 BB的可能性給淘汰掉。

The middle one is known as an Hidden Pair: Since the 1 in the top Region can only go in C or F, and the 6 can only go in C or F, we can deduce that no other digits can go in C or F.
而中間的那個, 則是稱之為 Hidden Pair 的技巧: 既然1在最上方的九宮格區塊中, 只有可能在格子C 或F, 而6也只能放在C或F, 那麼我們就可以把其他的數字放在C 或F 的可能性給除去。

The bottom one is known as Naked Pair: Since cell A can only be 2 or 6, and cell V can only be 2 or 6, we can eliminate 2 and 6 from all the other cells in the column.
至於最下方的那個, 則一般被稱為Naked Pair : 既然格子 A 只能放數字2或6, 而格子V 也只能放數字2或6, 因此我們就可以知道, 那個直行中的其他格子不能放2 以及6。

You may be a bit surprised to see that these three rules, while all very different in the Sudoku grid, look amazingly similar in the set diagram. That illustrates the main power of the Sledgehammer theory -- that it shows that most of these heuristics are actually the same once you realize the symmetric relationships between the different constraints.
你可能會有點訝異這三個不同的訣竅, 平常在玩Sudoku 時, 感覺它們的性質迥異; 然而在這個圖當中, 它們卻又如此的相似。這, 就明白顯示了 Sledgehammer 理論最強的一個優勢 – 當你在不同的限制條件下, 了解了對應的關係, 絕大部分的訣竅其實都源出一系。

Anyway, let’s apply the Sledgehammer, eliminate some Placements, and look for some more applicable Premise-Conclusion groups:
反正無論如何, 讓我們應用Sledgehammer, 去剔除掉一些Placement, 並且去找出一些其他可以有用的Premise-Conclusion群組:
 

(點選此處觀看此圖)
These three are much simpler to explain. They’re all Pointing Pairs.
這三個就比較容易解釋了, 他們都是Pointing Pairs (技巧)

Note that the fewer loops are involved, the simpler the heuristic tends to be to explain. Anyway, eliminating another round leads to:
記得一點, 環所包含的元素越少, 則用來分析的訣竅就越簡單。反正, 接著就會變成:
 

(點選此處觀看此圖)
Up to now, we haven’t been able to reduce any loop down to just one element, so we haven’t been able to write anything in. But here, finally, we have a complex three-ring Premise-Conclusion group (a Naked Triple), allowing us to eliminate the B4 Placement and finally prove that cell K must contain a 4!
到目前為止, 我們都沒辦法把任何環當中的元素減少到剩下一個, 所以我們也還不能十分確定地填入任何數字。不過咧, 最後, 我們有一個十分複雜的三環Premise-Conclusion 組合(一個Naked Triple), 這讓我們可以把B4 移掉….天啊, 我們最後終於証明了格子K 必需要填入4。

After that, the rest of the puzzle should be easy, so I won’t solve it here. (Well, you may want to take a note that during that complex process we also eliminated AA6 and AA9.)
在這之後, 剩下的題目就應該挺容易的了, 所以筆者就不再解題下去(好吧, 也許你還想加個註記: 在這段複雜的過程中, 我們也刪除掉了AA6 和AA9 的可能)(譯者注: 所以這代表了AA 要放入1??也就是一開始其實我們也可以加一個AA1, AA6 及 AA9 的Rule??)
 
I hope this gives a much better feel for how the Sledgehammer concept works. Please drop me an e-mail (onigame at gmail.com) if you have any questions, suggestions, ideas for making it easier, etc.
筆者希望這篇文章, 讓你對Sledgehammer 這個概念的使用方式, 有更清楚的了解。如果你有任何的問題, 建議, 點子, 或是可以讓這內容更簡化, 請寄一封 E-mail(onigame@gmial.com), 讓筆者曉得。

One more thing worth mentioning: Although almost all known Sudoku heuristics can be stated as a Sledgehammer situation, and Sledgehammer heuristics can solve almost all Sudoku puzzles, not all of them can be. Usually those that cannot are those that are meant when solvers talk about "puzzles that require guessing" or "puzzles that cannot be solved by logic alone. I hope to explore those sorts of situations in a later blog entry.
另外還有一個要提一下: 雖然大部分為人所知的Sudoku 技巧都可以用Sledgehammer 的模式來描述呈現。而Sledgehammer 的理論也能解掉幾乎所有的 Sudoku 題目, 但….不是全部。通常這些沒有辦法用此理論的題目, 就是玩家們所稱的『要靠猜的謎題』或是『無法單用邏輯就可解開的題目』。筆者希望能在未來的Blog 文章中, 再去探研這些類型。

Good luck, and have fun!
祝好運, 玩得開心點喔!!

---以上文章經 Wei-Hwa Huang 同意 Joky 翻譯轉載