第35講：動態鏈

今天講一下鏈的新一種思想：鏈的動感之舞。

啥？鏈能跳舞？莫非是舞蹈鏈（Dancing Links）？當然不是，舞蹈鏈是一種演算法，可以提供用於解數獨題，不過總歸是一種演算法，這裡用的則是符合人腦思路的一種技巧。它被稱為動態標準鏈（Dynamic AIC），一般簡稱動態鏈。

Part 1 動態鏈（Dynamic AIC）

如圖所示，鏈的寫法如下：

r3c1(3)={ r2c2(3)-r7c2(3=4)-r8c13(4)=r8c5(4)-r4c5(4), r3c8(3)-r4c8(3)}=r4c1(1) => r3c1<>1

嘛，不要在意寫法有點像Java風格。

邏輯是這樣解釋的：由於鏈的起始需要設為假，所以設r3c1(3)為假，則同時可以得到r2c2(3)和r3c8(3)為真。兩端引出兩條不同的鏈後，分別得到r4c5(4)和r4c8(3)為假，所以r4c1(1)此時必然應為真。所以r3c1(3)為假時，r4c1(1)應為真，所以r3c1(3)和r4c1(1)至少一個為真，按照不連續環的邏輯，刪掉r3c1(1)。

那麼，有點疑問。觀察r4，r4有多個單元格塗色，但顯然不是ALS，因為數一下單元格數和候選數種類數，發現是相差2而不是相差1的。

那麼，你這麼理解一下：r3c1(3)為假時，r2c2(3)和r3c8(3)同時為真。r2c2(3)引出的鏈得到了r4c5(4)為假，而r3c8(3)引出的鏈得到了r4c8(3)為假。這也就意味著，r3c1(3)為假時，可以得到r4c5(4)和r4c8(3)同為假。如果此時r4c1(1)也為假，就意味著這三個數同為假，然後塗色的四格，就都只有2、5、8三種候選數，這顯然是不夠填的，所以r4c1(1)此時只能為真。所以它是強關係。

那麼注意一點了哈，這裡是r4c5(4)和r4c8(3)同時為假，如果寫成{r4c5(4), r4c8(3)}的話，就要注意裡面兩數是同假的，不要把邏輯搞錯，然後推導走向了另外一個錯誤的方向。比如之前有人就問我，r4c5(4)和r4c8(3)這個整體節點為假，應該是破壞「r4c5(4)和r4c8(3)同時為真」的情況，所以應該是r4c5(4)和r4c8(3)最多有一個為真的意思。這個說法是錯的，我還講了好久為什麼呢！

好了，最後告訴大家一下，這裡嵌入了一個四個單元格，但內部有六種數字的結構。它的名字是二次待定數組（Almost ALS），就是ALS的待定版本。之前為啥沒講捏，因為這個叫做AALS的東西一般不在實戰裡面出現，或者出現頻率極少，而且不好觀察到。

然後，當鏈結構帶有分支推導現象時，我們稱整體鏈結構為動態鏈結構。如果是不連續環有分支，就是動態不連續環（Dynamic Discontinuous Loop）。

當然了，說到這裡就順便提一下，這歪果仁啊，取名字也是有意思。單元格數和候選數種類數差1的叫待定數組（ALS），差2的叫二次待定數組（Almost ALS，AALS），差3的叫三次待定數組（Almost AALS，AAALS），差4的就四次待定數組（Almost AAALS），我一口老血，噗！

Part 2 三國爭雄（Three-kingdom W-Wing）

那麼這個結構也是一種強制鏈，不過放到這裡講呢，是因為它是W-Wing的拓展版，多長了一個分支出來。動態鏈的寫法如下：

r4c3(6=9)-r9c3(9)={ r9c4(9)-r3c4(9=6), r9c6(9)-r6c6(9=6)} => r4c4<>6

這裡刪除的數字是三個端點的交集，因為如果r4c3(6)為假，則r3c4(6)和r6c6(6)至少有一個為真。所以這三個數至少有一個為真。不論如何，鏈頭和兩個不同的鏈尾至少有一個為真，它們的交集都不應是6，所以r4c4<>6。

這個結構被稱為三國爭雄（Three Kingdom W-Wing），是一種很神奇的東西。而它也引出了一種新的鏈結構：有多個鏈頭或有多個鏈尾的鏈。這種鏈稱為多端點鏈（Multi Endpoint Chain）。

Part 3 多端點鏈的逆向思路

嘛，多端點鏈按照端點數不同，分多種情況，這裡先從最簡單的三端點鏈開始介紹。

假設這個三端點鏈，鏈頭有一個，鏈尾有兩個。那麼它的邏輯是「如果鏈頭為假，則兩個鏈尾至少有一個為真，則刪除它們三個端點的交集」。

那麼，如果這個鏈逆向推導呢，邏輯又是如何的？先用邏輯語言把敘述改一下。先設「鏈頭為真」叫A，「第一個鏈尾為真」叫B，「第二個鏈尾為真」叫C。則敘述應該是這樣：

若非A，則B或C。

將鏈逆向，則就是(1)式子的逆否命題。

若非（B或C），則A。

然後，借用對偶律拆開括弧。

若非B且非C，則A。

轉為自然語言，就是「兩個鏈尾同時為假時，得到鏈頭為真時，則可以刪除它們三個端點的交集」。

那麼，更多情況的，可以自己試試看。這裡就不再講解了。

Part 4 帶鰭鏈（Kraken Unit）

如圖所示。鏈表示如下：

r9c5(2)=r1c5(2)-r3c6(2)=r3c1(6)-r4c1(6)={ r4c5(6), r4c3(6)-r7c3(6)=r7c6(6)} => r9c5<>6

這條鏈的刪數邏輯是，觀察r4c5(6)，設它為真時，可以刪除r9c5(6)；設它為假時，引出鏈，以r9c5(2)起頭，得到r7c6(6)為真，依然可以刪除r9c5(6)。所以r9c5(6)可以刪除。

這個結構運用了之前在標準魚裡面的鰭結構的思想。所以稱為帶鰭鏈（Kraken Unit）。這個結構因為鰭會影響到鏈之中r4的強關係，所以英文名叫Kraken Row，可以翻譯為行上帶鰭鏈。

Part 5 動態環的刪數

如圖所示，鏈寫法如下：

r7c2(1=8)-r7c6(8)={ r7c6(2)-r7c8(2)=r5c8(2), r7c6(5)-r1c6(5=6)-r2c5(6=1)-r2c7(1)=r3c8(1)}-r5c8(1)=r5c2(1)-r7c2(1) => r7c5<>8

它的邏輯大致是這樣的：設r7c2(1)為假，則得到r7c6(8)為假時分兩種情況討論，一個是r7c6=2，另外一個則是r7c6=5。但不管r7c6是2還是5，都能得到r5c8(1)為假，於是又可以得到r5c2(1)為真、r7c2(1)為假。這樣就首尾拼接成環了。

可是稍微奇怪的是，r7c6分了兩種情況討論，也就是這裡產生了分支，那麼，這個環的刪數仍然還是所有弱關係對應位置嗎？

想一下邏輯，如果把邏輯抽象出來，就是下面這個樣子：

首先，大體下，F-A部分是可以刪除的，不過B-C和D-E兩處是兩種不同的情況，它們是「或」的關係（注意「或」的關係是指兩個部分至少有一個為真，而不是有且僅有一個為真），所以我們無法判斷到底B-C還是D-E是一直都可以的，也就不能找到分支條件下的刪數。所以總體來看，刪數只有F-A。

對於圖上來說，只有r5c2(1)-r7c2(1)和r7c2(8)-r7c6(8)兩處弱關係可以刪數。

這個結構稱為動態標準環（Dynamic Continuous (Nice) Loop），一般簡稱動態環。

Nice一詞在這個題是需要去掉的（Dynamic Continuous Loop），但有些動態標準環可以保留。Nice一詞加不加，是看結構內是否所有弱關係的對應位置都可刪數。如果環內所有弱關係都是可以刪的，就要加上Nice，但此時因為結構具有分支，所以無法讓分支上的弱關係刪數，所以不能加Nice。

如圖所示，這個鏈內嵌入的AHS結構。鏈的寫法如下：

r9c5(1)=r9c1(1-7)={ r4c1(7)-r4c9(7), r1c1(7)-r1c79(7)=r3c9(7)-r4c9(7)}={r4c7, r5c8}(27)-r4c7(1)=r4c5(1)-r9c5(1) => r9c1<>3, r6c5<>1, r4c7, r5c8<>58

這個題的推導和剛才的動態環差不多。刪數也是找總體下的弱關係。總體下的弱關係有r9c1(1-7)、{r4c7, r5c8}(27)-r4c7(1)、r4c5(1)-r9c5(1)這三個。那麼刪數也就在這裡面去找。需要提到的地方就是這裡的r4c7和r5c8的27隱性數對的刪數了。我們之前說到的是，刪數是看兩端都能刪的地方，雖然這個27隱性數對確實可以刪r5c8(8)，但是r4c7(1)為什麼也能保證r5c8(8)可以刪呢？因為此時r4c7(1)和r5c8(8)都是弱關係。如果r4c7(1)和r5c8(8)同真時，b6內數字2沒有位置可填。所以r4c7(1)和r5c8(8)確實是弱關係，也就確實是可以刪的。

另外，這個結構稱為動態超標準環（Dynamic Hyper Continuous (Nice) Loop），一般簡稱動態超環。同樣，此題不加Nice。

Part 6 總結

這一節是針對講到的技巧做的一個統一的難度歸納和理論分析。

• 動態標準鏈
• 英文名：Dynamic AIC
• 動態不連續環
• 英文名：Dynamic Discontinuous (Nice) Loop
• 三國爭雄
• 英文名：Three-kingdom W-Wing
• 難度係數：SER 無，XR 5.0
• 命名空間：Tech.Chain.Wing.Irregular.Extended
• 帶鰭鏈
• 英文名：Kraken Unit
• 動態標準環
• 英文名：Dynamic Continuous (Nice) Loop
• 動態超標準環
• 英文名：Dynamic Hyper Continuous (Nice) Loop

使用到的術語：

• 二次待定數組
• 英文名：Almost Almost Locked Set
• 解釋：同一區域內的n個單元格下有(n+2)種候選數的集合。
• 三次待定數組
• 英文名：Almost Almost Almost Locked Set
• 解釋：同一區域內的n個單元格下有(n+3)種候選數的集合。
• 四次待定數組
• 英文名：Almost Almost Almost Almost Locked Set
• 解釋：同一區域內的n個單元格下有(n+4)種候選數的集合。
• 舞蹈鏈
• 英文名：Dancing Links
• 解釋：一種快速計算數獨題的演算法。它採用了一種叫做雙向循環十字鏈表的鏈表數據結構。
• 雙向循環十字鏈表（編程）
• 英文名：Doubly Circular Orthogonal Linked List
• 解釋：一種由鏈表派生出的數據結構，同時具有循環鏈表（首尾成環）、雙向鏈表（節點雙向，前驅節點和後繼節點可以正向或反向進行遍歷）、十字鏈表（節點是二維的，可左右遍歷也可以上下遍歷）三種鏈表的特徵。
• 動態
• 英文名：Dynamic
• 解釋：對於有分支的鏈結構的名稱。單元強制鏈是特殊的動態鏈。

推薦閱讀：