第 41 講:基本的強(qiáng)制鏈類(lèi)型
強(qiáng)制鏈(Forcing Chain)是鏈的一個(gè)重要的思想,為了讓鏈的使用范圍更加廣泛,便產(chǎn)生了這個(gè)思想。
Part 1 基本的強(qiáng)制鏈類(lèi)型
下面陳列一些基本的、常見(jiàn)的強(qiáng)制鏈模型。
1-1?區(qū)域和單元格強(qiáng)制鏈
區(qū)域強(qiáng)制鏈(Region Forcing Chain)和單元格強(qiáng)制鏈(Cell Forcing Chain)屬于一類(lèi)強(qiáng)制鏈,這個(gè)類(lèi)型的強(qiáng)制鏈?zhǔn)褂面湹乃季S,將某一個(gè)區(qū)域所有每個(gè)候選數(shù),或某一個(gè)單元格的所有候選數(shù)情況進(jìn)行分情況討論,并以弱關(guān)系延伸(即假設(shè)每一個(gè)分支的頭節(jié)點(diǎn)為真的形式進(jìn)行向下推理),直至所有分支的尾節(jié)點(diǎn)均能得到一致的結(jié)論。如果全部情況都能得到一致的結(jié)論,則結(jié)論一定成立。不過(guò),區(qū)域強(qiáng)制鏈?zhǔn)前葱辛袑m的某一種候選數(shù)進(jìn)行分情況討論的,而單元格強(qiáng)制鏈則是按單元格的所有候選數(shù)進(jìn)行討論的。
1-1-1?區(qū)域強(qiáng)制鏈

如圖所示,可以發(fā)現(xiàn)c6一共有三個(gè)2,我們將每一個(gè)2都進(jìn)行討論。
第一種情況:r1c6(2)為真。顯然,r1c6 = 2時(shí),一定有r1c1 <> 2;
第二種情況:r3c6(2)為真,此時(shí)有一條強(qiáng)制鏈:r3c6(2)-r3c28(26)=r3c8-r3c1=r1c1(5),得到r1c1(5)為真,所以一定也有r1c1 <> 2;
第三種情況:r8c6(2)為真,此時(shí)有一條強(qiáng)制鏈:r8c6-r9c4(2)=r9c1(2),得到r9c1(2)為真,所以r1c1 <> 2。
所有的情況均能使得r1c1 <> 2,所以r1c1 <> 2結(jié)論是成立的,可以刪除掉它。
1-1-2?單元格強(qiáng)制鏈

如圖所示,按r4c7的所有候選數(shù)進(jìn)行分情況討論。
當(dāng)r4c7(3)為真時(shí),則有強(qiáng)制鏈:r4c7-r6c8=r6c3(3),即得到r6c3 = 3;
當(dāng)r4c7(5)為真時(shí),則有強(qiáng)制鏈:r4c7-r4c6=r6c6-r6c3(5=3),即得到r6c3 = 3;
當(dāng)r4c7(6)為真時(shí),則有強(qiáng)制鏈:r4c7-r7c7=r7c4(6)-r14c4(46)=r1c4-r1c3=r6c3(3),即得到r6c3 = 3。
所有的單元格的情況都能得到r6c3 = 3,所以r6c3 = 3結(jié)論成立。
可以看到,上述的兩種推導(dǎo)方式都不是很特別好,因?yàn)樗嗌俣加幸稽c(diǎn)試數(shù)的風(fēng)格。不過(guò),有些題目不得不使用這類(lèi)技巧才能完成。所以請(qǐng)讀者你在使用之前斟酌,不要隨時(shí)隨地都使用它,這樣是不合適的。
1-2?矛盾強(qiáng)制鏈
前面敘述了一種分情況討論的強(qiáng)制鏈,接下來(lái)要講到的矛盾強(qiáng)制鏈(Contradiction Forcing Chain)則是另外一種類(lèi)型的強(qiáng)制鏈。這種強(qiáng)制鏈依賴于一個(gè)節(jié)點(diǎn)的兩種情況。當(dāng)兩種不同的情況均能得到一致的結(jié)論的時(shí)候,則結(jié)論成立。

如圖所示,按r9c8(8)執(zhí)行兩種情況的假設(shè)。
假設(shè)r9c8(8)為真,則有強(qiáng)制鏈:r9c8-r9c1=r8c1(8),則r8c1 <> 6;
假設(shè)r9c8(8)為假,則有鏈:r9c8=r5c8-r5c4=r2c4(8)-r1c5(6)=r8c5(6),依然可以得到r8c1 <> 6。
不論真假,都可以得到r8c1 <> 6,所以r8c1 <> 6。
另外,這個(gè)類(lèi)型的強(qiáng)制鏈一般可以改寫(xiě)為普通鏈的形式,僅需要將其中一種情況反向即可,所以矛盾強(qiáng)制鏈一般不實(shí)用,僅在一些特殊情況(例如嵌套結(jié)構(gòu)里)使用較多。
Part 2?鏈能看逆向,那么強(qiáng)制鏈呢?
可以看到,強(qiáng)制鏈和鏈不一樣的是,強(qiáng)制鏈有至少兩個(gè)分支,而帶有不同的推理情況。那么鏈可以逆向理解,強(qiáng)制鏈?zhǔn)欠褚部梢阅???shí)際上是可以的。我們先來(lái)看區(qū)域和單元格強(qiáng)制鏈的大致邏輯:將所有情況進(jìn)行分情況討論,如果全部情況都能得到一致的結(jié)論,則結(jié)論一定成立。那么倒過(guò)來(lái),則是這樣的一種情況:假設(shè)某條件成立,則能推出某一個(gè)區(qū)域下的所有某一候選數(shù)全為假,或者某一個(gè)單元格的所有候選數(shù)全為假時(shí),產(chǎn)生矛盾,所以原假設(shè)錯(cuò)誤。
同理,矛盾強(qiáng)制鏈的逆向視角則是:假設(shè)某條件成立,則能推出某一個(gè)節(jié)點(diǎn)存在真假兩種情況都成立的矛盾情況,進(jìn)而得到原假設(shè)錯(cuò)誤。