第 27 講:均衡數組
接下來我們來看一種稍微暴力一些的技巧,叫均衡數組(Aligned Subset Exclusion)。
Part 1 均衡數對(Aligned Pair Exclusion)

如圖所示,觀察r12c6。在無計可施的情況下,我們來枚舉這兩格的所有填數情況。那么,r12c6都是三值格,所以就應該有九種不同的填法。我們一一羅列出來:

第一列表示r1c6填的所有可能,第二列表示r2c6填的所有可能。隨后我們發(fā)現,有一種特別的情況,使得它所有對應的情況,全部都是錯誤的。就是那個r2c6 = 8。當r2c6 = 8的時候,r1c6的所有填數可能與之的組合都不對。正是因為如此,所以r2c6 <> 8。
這個結構稱為均衡數對(Aligned Pair Exclusion),它的邏輯很暴力——枚舉。說白了就是一個一個去找。更大的結構就是下面的這個例子了。
Part 2?均衡三數組(Aligned Triple Exclusion)

按照剛才的邏輯,我們把r1c46和r2c1的所有填數情況都枚舉一遍。

隨后發(fā)現,所有r1c4 = 4的情況均是錯誤的。所以,r1c4 <> 4。
這個就是均衡三數組(Aligned Triple Exclusion)了。
Part 3 均衡四數組(Aligned Quadruple Exclusion)

可怕的枚舉情況。一共我們需要枚舉r7c6、r8c27和r9c4四個的所有填數組合。候選數一共是2 * 3 * 3 * 3 = 54種情況!
不過,r8c2 = 7時,其它三個單元格的所有填數情況全部都會導致矛盾,所以r8c2 <> 7。
Part 4 為什么如此暴力的技巧,也會放在這里介紹?
均衡數組一直飽受爭議,因為它的推理方式過于暴力,并且不容易觀察到。在此為大家介紹一種觀察方式。
首先,由于均衡數組的枚舉單元格是不定的,所以我們此時按照每一大行和大列的方式搜尋。如果找的是均衡數對,則去找大行和大列存在的雙值格(含有兩個候選數的單元格),如果這樣的雙值格較多,就有一定可能產生均衡數對(但如果這樣的單元格較少,就不容易得到類似于均衡數對枚舉而產生的矛盾現象);那如果是均衡三數組,則去尋找大量的三值格(含有三個候選數的單元格)和雙值格,看是否這樣的單元格很多。如果這樣的單元格很多,則我們可以知道的是,這樣的均衡三數組很有可能出現(當然,也有可能不存在,只是很大程度滿足了結構需求了)。
當結構滿足要求的時候,這個時候就去看雙值格和三值格涉及的所有數字,然后去尋找只有這些候選數的單元格,最后才會針對這樣的結構進行枚舉推導。而均衡數組經常被改寫為待定數組的某些形式,但有時也不一定比均衡數組觀察起來方便。
那么,整個待定數組的基本使用技巧就講到這里,這也象征著進階技巧已經全部講完了,接下來我們將進入到鏈的學習之中。