[數獨高級技巧入門]鏈的邏輯及AIC

7

轉載自獨數之道
作者：葉卡琳娜

這個帖子主要想闡述鏈是什么，怎么使用鏈，以及鏈的邏輯過程，幫助大家首先了解原理，那么以后關于chain、wing之類的按照這個思路都非常容易理解。
首先我想說明下什么是“強”關系，什么是“弱”關系？
強關系是說A與B兩個事件，假如A不成立，則B一定成立。
弱關系是說A與B兩個事件，假如A成立，則B一定不成立。
舉一個簡單的例子幫助大家體會：


（圖中被劃短橫線的格表示不含候選數1）
這是一個數獨的宮，根據數獨規則一個宮內出現數字1-9各一次，可以做出以下兩點推斷：
1.左上格不是1，則右中格一定是1；
2.左上格是1，則右中格一定不是1。
第一種推斷得到這兩格的1是強關系，所以可以說兩格之間形成一條強鏈，強鏈我們通常以雙橫線表示（==）；
第二種推斷得到這兩格的1是弱關系，所以可以說兩格之間形成一條弱鏈，弱鏈我們通常以單橫線表示（——）。

再舉一個例子：


（圖中被劃短橫線的格表示不含候選數1）
上圖可以做出三大點推斷：
1.左上格是1，則中上格及右中格一定不是1；
2.中上格是1，則左上格及右中格一定不是1；
3.右中格是1，則左上格及中上格一定不是1。
這個例子里，存在著3條弱鏈，分別是（左上--中上）、（左上--右中）、（中上--右中）。

7

上面說的是同一數字的強弱關系，當然強弱關系可以不局限于一個數字，下面用例子來說明：

（圖中被短橫線劃掉的格說明未知其候選數情況）
根據右上格的候選數僅有1與2可以做出以下推斷：
1.如果該格不能是1，則一定為2；
2.如果該格是1，則一定不是2。
推斷一說明數字1與2之間是強關系，形成強鏈；推斷二說明其為弱關系，形成弱鏈。


（圖中被短橫線劃掉的格說明未知其候選數情況）
右上格有3個候選數，我們可以做出以下推斷：
1.如果這格為1，則不能為2或3；
2.如果這格為2，則不能為1或3；
3.如果這格為3，則不能為1或2。
數字1與2、2與3、1與3之間分別為一條弱鏈。

像第二張圖這樣的關系推斷，大家可能會不以為意，但是這是理解強弱關系的一個很好的例子，對于后面將要敘述的內容也會有所幫助。

相信通過上面的說明大家已經了解了強弱鏈是什么，接下來我們將強弱鏈連接起來。
第一種情況：A==B--C==D
由A的真假情況可以做出以下BCD關系的枚舉。
再次請大家注意本文開頭所提到的強弱關系本質
1.強關系是說A與B兩個事件，假如A不成立，則B一定成立。
2.弱關系是說A與B兩個事件，假如A成立，則B一定不成立。



（圖中紅色部分表示根據上一個的真假情況必然是這樣的推導）
可見A與D不全為假，即A與D一定有一個為真。
當A與D有等位群格位的交集時，即可做出相應刪減。

7

（圖示技巧名為Skyscraper）
根據強弱關系，我們找到了一條符合A==B--C==D的強弱鏈組：r3c1(2)==r3c7(2)--r9c7(2)==r9c2(2)。
根據上文提到的邏輯關系，可以得到r3c1=2與r9c2=2至少有一個成立，所以可以刪去它們等位群格位的交集（即橙色區域）的候選數2。



•根據葉卡林娜前面對于強鏈的敘述，以下是一個雙強鏈的實例，也是大家耳熟能詳的 X-Wing。


1. 上左圖，數字 4 在 C4,C8 形成 X-Wing。
2. 上右圖，R2,R4 除了形成 X-Wing 的四格之外，其它格位不能存在數字 4，因此畫 X 處就是可以刪減候選數 4 的格位。


● X-Wing用之前提到的強弱強鏈觀察可以找到2組，以上圖為例：
　r2c4==r4c4--r4c8==r2c8，得到r2c4與r2c8的4至少有一個成立，所以可以刪除R2其他格的候選數4；
　r4c4==r2c4--r2c8==r4c8，得到r4c4與r4c8的4至少有一個成立，所以可以刪除R4其他格的候選數4。

7

•有時運用不同的強弱強鏈，能達到相同的刪減效果，下面就是一個例子：





•左側使用的是r5c1==r5c9--r3c9==r1c7的強弱強鏈；

•右側使用的是r3c2==r3c9--r5c9==r5c1的強弱強鏈。

•兩種觀察方法均可以刪除r1c1的候選數1。



•上面的幾個例子都是關于單一數的強弱強鏈的，在數獨的解題技巧里我們將這類成為X-Chain。

•關于單一數鏈應用我們放在 雙強鏈解法的運用 這個主題中繼續討論。

•當把鏈的條數增加的時候，也就是A==B--C==D--E==F時，也能夠推導出A與F至少有一個為真，這邊就不做枚舉了，大家可以自行推導下。

•下面來看一些牽扯到異數的強弱強鏈的例子。

7

要說異數強弱強的關系肯定要提到XY-Wing了，下面是一個XY-Wing的例子：



（圖中三格的候選數由點算即得）

通常解釋XY-Wing原理的時候會用如果r4c2=1則r5c1=4；如果r4c2=9則r4c8=4，所以不論r4c2是1還是9，r5c1與r4c8中至少有一個是4，
從而得到r5c1與r4c8的等位群格位交集部分（圖中藍色格）不含4。

這樣是不是有點猜測的味道呢？很多人都說高級技巧是把猜的東西合理化，其實不然。

用強弱強鏈的觀點可以這樣看r5c1(4)==r5c1(1)--r4c2(1)==r4c2(9)--r4c8(9)==r4c8(4)，
也是得到r5c1與r4c8中至少有一個是4，這樣的觀察是不是更邏輯化呢？歡迎大家提出你的看法。



與XY-Wing較相近的要數XY-Chain。



XY-Wing由三格組成，分別為xy格，xz格，yz格。XY-Chain不止三格，需要把一些格合并當作XY-Wing組成格之一來看。（這些我們會在相應主題再討論）

下面來看一個例子：

這里就不用如果怎么則怎么來解釋了，畢竟通過上面一些介紹，大家可以用強弱強這樣的邏輯關系解釋，不需要用如果怎么樣的解釋。
以XY-Wing的觀點來看的話可以將r4c2作xy格，r4c9作xz格，{r5c1, r5c2}作為yz格。
以強弱鏈的觀點來看略復雜，因為由4條強鏈組成，請大家以r4c9為起點依次觀察交替的強鏈(紅色)、弱鏈(綠色)。
可以得到兩端點r5c1(1)、r4c9(1)至少有一個成立，所以可刪除兩者交集r5c89的候選數1。

7

有的時候我們可以把兩格看作一組，例如在 雙強鏈解法運用 中的第六題：



r4c1(7)==r5c4(7)--r5c2(7)=={r1c2, r2c2}(7)
得到{r1c2, r2c2}與r4c1至少有一個為7。
所以可以刪除{r1c2, r2c2}與r4c1等位群格位的交集r1c3的候選數7。
-------------------------------------------------------------------------------------

XY-Chian的首尾若能連接起來就成為了XY-Cycle（Multi X-Wing）




上圖中斷開任意一條弱鏈（綠色表示）即成為XY-Chain的結構。

例如斷開上端r8c57的弱鏈后，可以得到r8c5(7)與r8c7(7)至少有一個成立，即可刪除這兩格等位群格位交集的7（這里交集是R8除這兩格外的格）。

其他三種斷開弱鏈能夠做何刪減，大家可以自己嘗試推導。


前面是例舉了強弱強的關系，那么弱強弱的關系又能得到什么結論呢？
第二種情況：A--B==C--D
由A的真假情況可以做出以下BCD關系的枚舉。

（圖中紅色部分表示根據上一個的真假情況必然是這樣的推導）
可見A與D不全為真，即A與D一定有一個為假。

這樣的關系有什么相應應用呢？歡迎大家提出你的看法。

7

既然強弱強看起來這么厲害，那么強強強會如何呢？
A==B==C==D
由A的真假情況可以做出以下BCD關系的枚舉。

（圖中紅色部分表示根據上一個的真假情況必然是這樣的推導）
可以發現，AD一真一假，全為真，全為假都可能，所以雖然是強強強，也達不到任何效果，比弱強弱還不如。
這難道就是所謂的物極必反么？


那么既然強強強都沒用，再加一個強，變成強強強強是不是會有點用處呢？
以前看過獨數文章的朋友可能還記得有一個叫Guardians（守護者）的技巧，也有地方稱之為Broken Wings或者Turbot-Fish。
其描述的是某一個候選數X的情況，當有偶數條強鏈，且兩個端點處于同一unit時，這時可以刪除兩個端點上的候選數X，
如果該unit出這兩端點格外只有一格含有候選數X，則該格一定就是X。


可以刪除r2c3與r4c3的候選數5，守護者r9c3=5。

大家可以解釋其中的原理么？

7

TTHsieh  對原理的解答：

單數鏈以強、弱方式構成環，稱為 X-Cycle，無法構成環，則稱為 X-Chain。
X-Cycle 的弱環節除節點外，單元內其它格位的相同候選數均可刪除。
X-Chain 在開口處之兩節點共同作用格的相同候選數均可刪除。
________________________________________________________________________
本質上 X-Cycle 只是 X-Chain 的特例，因此統稱為單鏈。
單鏈若由兩條強鏈與一條弱鏈構成，就是習稱的雙強鏈，有摩天樓、雙線風箏、魚三種連結方式。
單鏈若由兩條強鏈與兩條弱鏈構成環，就是習稱的 X-Wing。


________________________________________________________________________


上面三圖中，從藍色格出發到達紅色格，根據它們之間的邏輯關系，可以得到紅色格有相同的真假值。


上面二圖中，從一個紅色格出發到達另一紅色格，根據它們之間的邏輯關系，亦可得到另一紅色格有相同的真假值。

紅色格若為假，沒問題兩個都可刪除，紅色格若為真，則違反數獨原則也應當刪除。
結論：紅色格應予刪除。


以分色法(Coloring)的推導方式是：若在某一單元出現相同的顏色，則色鏈中與該顏色相同的格位均應刪除。

圖1

圖2

圖3

上圖1 刪除白色, 上圖2 刪除藍色, 上圖2 刪除白色


圖4

圖5

上圖4 刪除藍色, 上圖5 刪除藍色
從每一格位出發所得到的結論均相同。

7

在本帖7樓提到了守護者的結構，這看起來似乎與在7樓的另一個觀點相矛盾。
但是事實并非如此，請注意觀察守護者的例子，因為這里所有的強鏈都是在同一unit的強鏈，因此，根據數獨規則，當然也符合弱鏈的定義，同一unit有兩個相同數不是矛盾了么？
因此在17樓中的推理如果是基于A==B==C==D且A--B--C--D，即所有鏈既是強鏈也是弱鏈時，八種情況中的六種即可刪除。


即只剩下 真假真假 與 假真假真 兩種情況。

因此，事實上守護者是同時符合A==B==C==D==E與A--B--C--D--E的結構。
按照A的真假性可以做出如下推導：
1. A真 -> B假 -> C真 -> D假 -> E真
2. A假 -> B真 -> C假 -> D真 -> E假
可見A與E真假性相同。
當A與E處于同一個unit時（此為守護者的結構描述，見本帖第15樓），不能同時為真，所以只能全為假。
因此，也就產生了A與E所在unit其他格中的X是守護者一說。
大家也可參考8樓提出的說明。


再來看另一種涉及雙數關系的技巧Y-Wing的邏輯關系：


用鏈的觀點來看：r3c8(9)==r3c8(2)--r6c8(2)==r6c6(2)--r9c6(2)==r9c6(9)，因此可以刪除r9c8的候選數9。

亦可這樣理解，如果r3c8不為9，r3c8為2，則r6c8不為2，r6c6為2，r9c6不為2，即r9c6為9；

反過來，如果r9c6不為9，則r9c6為2，r6c6不為2，r6c8為2，r3c8不為2，即r3c8為9；

可見r3c8與r9c6至少有一個為9，因此可以刪除r9c8的候選數9。

8773

額，先收下了，慢慢消化，不過，這應該是經驗得來的吧，好好學學