第 46 講:毛刺、毛邊
為了解決強(qiáng)制鏈觀察困難和邏輯死板的特殊情況,我們發(fā)明了一種技巧,叫做毛刺(Burr Logic)和毛邊(Bi-burr Logic)。
本文的概念毛刺和毛邊都是由來(lái)自中國(guó)的數(shù)獨(dú)玩家“探長(zhǎng)”(網(wǎng)名,Borescoper)發(fā)現(xiàn)和命名。因?yàn)榧记煞浅?shí)用,因此本文的相關(guān)內(nèi)容對(duì)于平時(shí)做難題來(lái)說(shuō)都顯得非常重要,因此是一個(gè)相當(dāng)有意義的一大數(shù)獨(dú)思維方式。
Part?1 毛刺的定義
先來(lái)說(shuō)說(shuō)毛刺。毛刺是一些難題技巧里必不可少的包裝技巧,它能夠把一部分強(qiáng)制鏈改寫(xiě)為比較優(yōu)雅的格式,而且邏輯更清晰、做題更容易觀察。
我們來(lái)看看毛刺到底是如何工作的。
1-1?第一種毛刺用法


如左圖所示,我們發(fā)現(xiàn)r3c789里,如果沒(méi)有這個(gè)多余的r3c9(7),三個(gè)單元格將變?yōu)橐粋€(gè)三數(shù)組,那么所在的宮和行上的其余2、5、6都可以被刪除。
但可恨的地方就是r3c9(7)是客觀存在的,所以我們不能使用這個(gè)結(jié)論。那么我們就不得不找出一條強(qiáng)制鏈,來(lái)消掉對(duì)7的影響,而且還能找到和之前刪數(shù)一樣(或者大部分一樣)的結(jié)論。
幸運(yùn)的是,我們發(fā)現(xiàn),當(dāng)r3c9(7)為真時(shí),此時(shí)r6c9(7)為假,于是產(chǎn)生了一個(gè)XY-Wing結(jié)構(gòu),使得它能刪除r23c9(6);而在之前的三數(shù)組里,我們確實(shí)也能刪除r2c9(6),所以,r2c9(6)便是這個(gè)技巧的結(jié)論。如圖所示。

這就是毛刺的基本使用方式:當(dāng)我們發(fā)現(xiàn)一個(gè)結(jié)構(gòu)多余了一個(gè)數(shù)或多個(gè)數(shù)的時(shí)候,我們想方設(shè)法把它(或它們)看作一個(gè)節(jié)點(diǎn),以它為起點(diǎn),作出一條強(qiáng)制鏈,沿途產(chǎn)生的所有強(qiáng)關(guān)系都是可以直接運(yùn)用到結(jié)論里的。
當(dāng)然,這個(gè)題只有一個(gè)弱關(guān)系,接了一個(gè)XY-Wing后,我們利用了XY-Wing的構(gòu)造,產(chǎn)生了首尾的強(qiáng)關(guān)系,于是便有了刪數(shù)。這就是我們上一段文字里說(shuō)到的“沿途產(chǎn)生的強(qiáng)關(guān)系”。不過(guò)這個(gè)例子只有這一個(gè)強(qiáng)關(guān)系,所以找到的刪數(shù)只有一處。有一些示例里的刪數(shù)比較多,它便使用了更多的強(qiáng)制鏈沿途產(chǎn)生的強(qiáng)關(guān)系。
當(dāng)然,毛刺結(jié)構(gòu)是可以轉(zhuǎn)為鏈的寫(xiě)法的,例如這個(gè)示例,我們可以將它記作
不過(guò),因?yàn)榻Y(jié)構(gòu)被嵌入鏈里,所以最好帶上結(jié)構(gòu)名來(lái)區(qū)分結(jié)構(gòu)是什么。當(dāng)然,最后的XY-Wing,我們需要的僅僅是那一條強(qiáng)關(guān)系,所以我們甚至可以改寫(xiě)為
這和之前的毛刺轉(zhuǎn)ALS一樣,也被稱(chēng)為解構(gòu)(Deconstruct)。當(dāng)然,區(qū)塊三數(shù)組也可以解構(gòu):
另外,我們稱(chēng)這個(gè)多余的數(shù)字為毛刺(Burr)。例如這個(gè)示例里的r3c9(7)就是整個(gè)結(jié)構(gòu)的毛刺。
如果你沒(méi)有看過(guò)癮,我們?cè)賮?lái)看一則使用示例。


如左圖所示,如果r23c1(9)為假,則我們嘗試假設(shè)此時(shí)r3c6(4)為假,則r23c4一定含有數(shù)字4,且r23c1是4、6數(shù)對(duì),那么此時(shí),如果r23c4(1)和r3c8(1)同假的話,r23c148將會(huì)構(gòu)成關(guān)于2、4、6的拓展矩形的致命形式。為了規(guī)避該致命形式的產(chǎn)生,我們不得不設(shè)定r23c4=r3c8(1)關(guān)系成立,且該強(qiáng)關(guān)系產(chǎn)生于r3c6(4)為假的時(shí)候。于是順次推導(dǎo),并可以得到r3c9 = 9的結(jié)果,此時(shí)可以去掉r3c6(9);但如右圖所示,如果r23c1(9)為真,則r46c1(9)同時(shí)為假,此時(shí)r46c16將形成關(guān)于4和5的共軛對(duì)類(lèi)型的UR結(jié)構(gòu)。于是此時(shí)r46c6(4)必須為假,所以r3c6(4)為真,此時(shí)一樣可以刪除r3c6(9)。
由于兩種情況均可以得到一樣的結(jié)論,所以r3c6 <> 9必然成立。
注意右圖中的某個(gè)箭頭上,有一個(gè)波浪符號(hào)“~”,它用來(lái)表示左側(cè)節(jié)點(diǎn)為假時(shí)得到右側(cè)節(jié)點(diǎn)也為假的邏輯。同理,實(shí)線箭頭上方帶有一個(gè)波浪符號(hào)表示左側(cè)節(jié)點(diǎn)為真時(shí)得到右側(cè)節(jié)點(diǎn)也為真的邏輯。這個(gè)標(biāo)注模式是之前從未提到過(guò)的,這里需要你注意一下。在后面的內(nèi)容里我們也會(huì)使用這樣的寫(xiě)法,并也在附錄里給出了這樣的標(biāo)注習(xí)慣的意思。
1-2 第二種毛刺用法
實(shí)際上,毛刺的用法還不止這一種,因?yàn)樗糜阪溊?,如果我們把它放在?shù)組(或偽數(shù)組)里,會(huì)怎么樣呢?


如左圖所示,我們找到了一個(gè)假的偽數(shù)組,之所以說(shuō)它是假的偽數(shù)組,是因?yàn)樗膬?nèi)部有3、4都可以跨區(qū)。我們一般認(rèn)為的偽數(shù)組只能有一個(gè)數(shù)字可以跨區(qū),這樣我們才能找到適合的結(jié)論,而這個(gè)結(jié)構(gòu)有3和4都可以跨區(qū),那么我們只能去討論跨區(qū)的最終情況了。
我們拿數(shù)字4來(lái)討論,如果數(shù)字4不跨區(qū)的話,那么例子里只有3可以跨區(qū),而結(jié)構(gòu)涉及的4個(gè)單元格里恰好只有3、4、6、9四種數(shù)字,所以我們可以利用偽數(shù)組的結(jié)果直接得到,這三個(gè)3的交集就是刪數(shù),例如圖中的r8c46和r9c4,都處于這個(gè)交集上(當(dāng)然,圖里只標(biāo)了一個(gè)結(jié)論刪數(shù),所以其它的都沒(méi)標(biāo))。
接著看右圖。當(dāng)數(shù)字4跨區(qū)的話,顯然只能把它們放到r7c8和r9c5上才可以實(shí)現(xiàn)跨區(qū)。所以放上去后,我們可以發(fā)現(xiàn)到一個(gè)強(qiáng)制UR結(jié)構(gòu):r39c45(34)。由于其中的一個(gè)單元格已經(jīng)被我們剛才的假定前提4給覆蓋了,所以我們基于這一點(diǎn),可以發(fā)現(xiàn)r9c4如果填入3的話,這四個(gè)單元格就只能放3和4:首先我們通過(guò)r9c4(3)得到r3c4(4)為真(雙值格);然后由于r3存在3的共軛對(duì),所以r3c5(3)必須為真,此時(shí)四個(gè)單元格只有3和4了。由于全部只能放下3和4,所以形成了致命形式,故假設(shè)不成立,即r9c4 <> 3。
而在第一種情況下(不跨區(qū)),r9c4(3)依然是可以刪除的,所以r9c4 <> 3即為結(jié)論。
這則示例看起來(lái)好像跟毛刺沒(méi)有什么關(guān)系,因?yàn)槊淌墙Y(jié)構(gòu)本身多出來(lái)一坨東西,但實(shí)際上,我們可以按照r9c5(4)是否成立來(lái)進(jìn)行討論,并基于偽數(shù)組這一點(diǎn)來(lái)產(chǎn)生不同的討論情況。
毛刺的兩種用法就說(shuō)完了,接下來(lái)我們來(lái)看一些其它的經(jīng)典示例。
Part 2?鏈列的毛刺用途
2-1?鏈魚(yú)
鏈魚(yú)(也叫鏈鏈列、遠(yuǎn)程鰭鏈列、遠(yuǎn)程鰭魚(yú),Kraken Fish,由于屬于魚(yú)的構(gòu)造,所以也可以簡(jiǎn)記為魚(yú)+或鏈列+)是Hodoku里規(guī)定的一種技巧,在結(jié)構(gòu)里存在一個(gè)魚(yú)鰭,不過(guò)這個(gè)魚(yú)鰭不像是之前的魚(yú)鰭一般可以直接對(duì)應(yīng)刪數(shù),而是添加一條鏈來(lái)得到刪數(shù)。


如左圖所示,假設(shè)r3c2(4)不存在,則X-Wing在r39上作為定義域是成立的。所以刪除域上的4全部都可以刪。不過(guò)由于r3c2(4)客觀存在的緣故,我們只能把它作為毛刺進(jìn)行討論。
假設(shè)r3c2 <> 4顯然可以刪數(shù);而r3c2 = 4時(shí),我們可以找到一條強(qiáng)制鏈:r3c2(4-9)=r3c7-r12c9(9=4)。由于沿途的所有強(qiáng)關(guān)系都可以使用,所以我們依次來(lái)尋找強(qiáng)關(guān)系末端的結(jié)果是否可以對(duì)應(yīng)到刪數(shù)上。
首先是r3c7(9),當(dāng)它為真時(shí),原本的刪數(shù)都是4,跟9無(wú)關(guān),所以這個(gè)強(qiáng)關(guān)系沒(méi)有刪數(shù);接著是r12c9(4),可以看到此時(shí)我們可以發(fā)現(xiàn)r12c9(4)可以對(duì)應(yīng)刪數(shù)r1c7(4),所以r1c7 <> 4便是這個(gè)結(jié)構(gòu)的結(jié)果。
當(dāng)然,很顯然的是,毛刺可以寫(xiě)成一條普通的鏈,所以這個(gè)示例可以把它寫(xiě)成一條普通的鏈:
這樣寫(xiě)的好處是可以更直觀地把結(jié)構(gòu)用鏈表達(dá)出來(lái)。不過(guò),我們就需要介紹一種新的節(jié)點(diǎn)類(lèi)型:X-Wing(以及更大型的鏈列結(jié)構(gòu))。這則示例是鏈魚(yú)的第一種類(lèi)型。
在講第二種類(lèi)型之前,我們先要處理一個(gè)遺留的問(wèn)題:X-Wing作為節(jié)點(diǎn)是什么樣的東西。
2-2?對(duì)X-Wing節(jié)點(diǎn)的討論
和之前介紹過(guò)的節(jié)點(diǎn)類(lèi)型不同的是,X-Wing的結(jié)構(gòu)非常大,這使得我們?cè)谟懻撜婕俚臅r(shí)候,不得不思考如何去放置這些數(shù)字。
首先,考慮一下X-Wing節(jié)點(diǎn)為真的情況。

如圖所示。顯然X-Wing節(jié)點(diǎn)為真,就意味著對(duì)角線兩端的兩個(gè)單元格(左上r3c3和右下r7c7,或者是右上r3c7和左下r7c3)兩處的填數(shù)模式是一樣的,即有兩個(gè)位置要填這個(gè)數(shù)1,而兩個(gè)位置不填這個(gè)數(shù)1。
那么X-Wing節(jié)點(diǎn)為假則是這個(gè)說(shuō)法的對(duì)立面。X-Wing一共涉及四個(gè)節(jié)點(diǎn),所以嚴(yán)謹(jǐn)?shù)姆绞绞?,我們需要討論的情況有如下五種:
節(jié)點(diǎn)里有4個(gè)單元格都填這個(gè)數(shù);
節(jié)點(diǎn)里有3個(gè)單元格都填這個(gè)數(shù);
節(jié)點(diǎn)里有2個(gè)單元格都填這個(gè)數(shù);
節(jié)點(diǎn)里有1個(gè)單元格都填這個(gè)數(shù);
節(jié)點(diǎn)里有0個(gè)單元格都填這個(gè)數(shù)(即沒(méi)有位置放這個(gè)數(shù))。
別怕,討論的情況看起來(lái)很多,但實(shí)際上很多情況是完全不可能出現(xiàn)的。顯然,X-Wing里完全不可能出現(xiàn)3、4個(gè)節(jié)點(diǎn)都填這個(gè)數(shù)字的情況;而一下我們就排除了近一半的情況;而填入2個(gè)顯然也不可能,因?yàn)樵趺捶胖?個(gè),只要放置的位置合理不產(chǎn)生違背數(shù)獨(dú)規(guī)則的東西,都是X-Wing為真的情況,而我們要討論X-Wing為假,所以它不屬于這種情況。
所以一下我們就只剩下兩種情況了。思考一下,X-Wing可能存在“有0個(gè)單元格填這個(gè)數(shù)”的可能嗎?如果你說(shuō)是,那么你就錯(cuò)了。由于魚(yú)鰭的存在,那么魚(yú)鰭必然只會(huì)存在在定義域上,而只有一個(gè)魚(yú)鰭的情況顯然是不可能出現(xiàn)在兩個(gè)定義域區(qū)域上的。如果沒(méi)有位置填這個(gè)數(shù),這就會(huì)使得有一個(gè)定義域區(qū)域下放不下這個(gè)數(shù)字。比如上圖里,定義域我們?nèi)藶楣潭閞37,假設(shè)魚(yú)鰭在r3上,那么如果屬于“有0個(gè)填入”的情況的話,r7就無(wú)法找到合適的位置能夠放下1了,因?yàn)閞37是定義域,定義域規(guī)定了結(jié)構(gòu)必須產(chǎn)生于這些區(qū)域,即區(qū)域里必須至少有一個(gè)位置是放這個(gè)數(shù)的。
所以,在五種情況里,只有一種情況是符合X-Wing為假的,那就是“四個(gè)節(jié)點(diǎn)里有一個(gè)放這個(gè)數(shù)”,而這個(gè)數(shù)還必須位于剛才我們說(shuō)到的、魚(yú)鰭不在的定義域區(qū)域上。所以綜上所述,我們就討論了X-Wing節(jié)點(diǎn)真假的情況了:
X-Wing節(jié)點(diǎn)為真:恰有兩處對(duì)角位置上填入這個(gè)數(shù)字;
X-Wing節(jié)點(diǎn)為假:有且僅有一處位置可以填入這個(gè)數(shù)字。
那么我們?cè)俅位氐皆瓉?lái)的題目上去理解。

如圖所示。我們率先就得假設(shè)X-Wing節(jié)點(diǎn)(r39c37(4))為假(圖上沒(méi)有畫(huà)出X-Wing整體)。顯然,當(dāng)X-Wing節(jié)點(diǎn)為假時(shí),只有r9c37里有一處是4,而r3c37里都不能是4,也因此我們確定了r3c2是4。因?yàn)樗莚3上的魚(yú)鰭,r3只有r3c237三處可以填入4,現(xiàn)在X-Wing節(jié)點(diǎn)規(guī)定r3c37(4)都為假了,顯然只有r3c2(4)為真了。所以,X-Wing節(jié)點(diǎn)為假后,得到了r3c2(4)為真,于是鏈得以往下繼續(xù)理解。
X-Wing節(jié)點(diǎn)的邏輯就討論完了。那么劍魚(yú)(三鏈列)和水母(四鏈列)呢?雖然結(jié)構(gòu)更大,但討論邏輯依舊完全一樣,首先我們可以得到的是,三鏈列最多占據(jù)9個(gè)單元格,而三個(gè)定義域上最多只允許我們能放下3處鏈列涉及的這個(gè)候選數(shù),所以4到9的情況完全不用我們考慮,因?yàn)檫@樣必然是有重復(fù)的,所以問(wèn)題直接簡(jiǎn)化到討論0到3個(gè)位置填數(shù)的情況;同理,四鏈列也是一樣,最多我們也只需要討論的是0到4個(gè)位置填數(shù)的情況。
不過(guò),實(shí)際上,管它填多少個(gè),你都會(huì)發(fā)現(xiàn),在節(jié)點(diǎn)為假時(shí),填數(shù)位置一定不會(huì)出現(xiàn)在魚(yú)鰭所處的定義域區(qū)域下。這便有了我們上面那樣的結(jié)果。所以,不論鏈列的規(guī)格是多大的,我們總能得到相似的結(jié)論,這便是鏈列這個(gè)東西神奇的地方所在。
另外,可以從圖上看到,前面的例子里毛刺的討論過(guò)程跟魚(yú)鰭完全一樣,它們唯一的差別是,魚(yú)鰭可以直接對(duì)應(yīng)刪數(shù),而毛刺不能。實(shí)際上,魚(yú)鰭和毛刺是一樣的東西,毛刺由中國(guó)的數(shù)獨(dú)玩家探長(zhǎng)(昵稱(chēng))發(fā)現(xiàn),并由他命名了這個(gè)技巧。從他本人口中得到的是,毛刺應(yīng)當(dāng)和魚(yú)鰭是一樣的,只是使用場(chǎng)合不同:魚(yú)鰭一般用于魚(yú)(鏈列)結(jié)構(gòu),而毛刺則針對(duì)于其它的非魚(yú)(鏈列)技巧。
2-3?鏈魚(yú)的推廣
接下來(lái)我們來(lái)看一下鏈魚(yú)結(jié)構(gòu)的推廣,到底該怎么用。

如圖所示,我們可以看到一個(gè)鏈列結(jié)構(gòu),不過(guò)它帶有一個(gè)魚(yú)鰭,而刪數(shù)卻跟魚(yú)的涉及數(shù)值完全不一樣。我們來(lái)看一下,我們?nèi)绾芜\(yùn)用這個(gè)魚(yú)結(jié)構(gòu)。


如左圖所示,鏈表述如下:
這條鏈以弱關(guān)系開(kāi)頭了,顯然用了強(qiáng)制鏈的思想。邏輯是這樣的:當(dāng)r4c5(5)鰭為真時(shí),r8c3(7)為真。很顯然,r8c3(7)為真了,自然r8c3(1)為假。
而如右圖所示,鏈表述如下:
那這條鏈想說(shuō)明什么呢?如果r4c5(5)鰭為假時(shí),r8c3照樣不為1。首先觀察到r8c3(7)為鏈頭,引出一條區(qū)塊不連續(xù)環(huán),直至r45c3(1),這樣就可以刪除r8c3(1)了。但是有一個(gè)小問(wèn)題,c6(5)并不是強(qiáng)關(guān)系。那為什么用強(qiáng)關(guān)系了呢?
因?yàn)檫@是一個(gè)鰭為假的二鏈列。當(dāng)這個(gè)鰭為假時(shí),它就是毫無(wú)瑕疵的二鏈列結(jié)構(gòu)了,而之前環(huán)結(jié)構(gòu)一章里,二鏈列結(jié)構(gòu)可以被看作環(huán)的形式,而弱關(guān)系下的所有數(shù)字可刪,從而把弱關(guān)系改變?yōu)閺?qiáng)關(guān)系的形式。這里就是利用了這一點(diǎn):鰭為假,二鏈列成立,二鏈列又是一個(gè)環(huán),所以所有二鏈列內(nèi)的弱關(guān)系均可被看成強(qiáng)關(guān)系使用,所以這才成立的。只是要注意一點(diǎn),這只是鰭為假時(shí),才成立,并不是所有情況下都成立,別忘了這個(gè)大前提。
然后按照這個(gè)區(qū)塊不連續(xù)環(huán)的邏輯,當(dāng)鰭為假,鏈結(jié)構(gòu)成立,并最終得到了r45c3(1)為真的結(jié)論,所以此時(shí)r8c3(1)照樣為假。那么,不論鰭的真假,r8c3(1)都可以刪除。所以r8c3 <> 1。
2-4?節(jié)點(diǎn)重疊的鏈魚(yú)

如圖所示,鏈表述如下:
那么簡(jiǎn)單敘述一下它的邏輯:當(dāng)r1c6(7)為假時(shí),順次得到r7c6(7)真、r7c6(4)假、r5c6(4)真、r5c6(3)假、r5c2(3)真、r2c2(3)假,然后b1內(nèi)產(chǎn)生36隱性數(shù)對(duì),所以r23c3(36)隱性數(shù)對(duì)為真,r23c3(7)均為假。然后,因r23c3(7)均為假,所以觀察c36(7),二鏈列結(jié)構(gòu)成立。
所以最終鏈的刪數(shù)為r1c6(7)和r17c36(7)的交集。r1c6(7)和r17c36(7)都能刪除的是r1其余位置的候選數(shù)7,所以r1c9 <> 7。
這個(gè)是單候選數(shù)和二鏈列的節(jié)點(diǎn)重疊結(jié)構(gòu)。
2-5?四個(gè)魚(yú)鰭的三頭鏈

如圖所示,鏈表述如下:
首先,{r8c7, r9c8}(49)的毛刺顯性數(shù)對(duì)為假時(shí),r8c7(6)為真(之前說(shuō)明過(guò)這一點(diǎn),這里不再贅述)。然后當(dāng)r8c7(6)為真時(shí),r17c27(6)的二鏈列結(jié)構(gòu)(如果暫時(shí)先不看r1c5、r7c459這四個(gè)魚(yú)鰭的話)必然無(wú)法成立。因?yàn)閞8c7(6)為真必然會(huì)排除二鏈列結(jié)構(gòu)同一列上的兩處填數(shù)位置,二鏈列必然是對(duì)角兩格同時(shí)為真的,這樣一排除必然導(dǎo)致無(wú)法這么去填數(shù),從而形成弱關(guān)系。那么,當(dāng)二鏈列結(jié)構(gòu)為假時(shí),那只可能讓魚(yú)鰭至少其一為真了。此時(shí)分兩路觀察。
如果r7c9(6)為真,那比必然r7c9(9)為假;而如果剩下三個(gè)魚(yú)鰭至少一個(gè)為真的話,都會(huì)使得r9c5(6)為假,于是觀察r9c58這個(gè)nALS區(qū)域,最終得到r9c8(9)為真。這樣的話,r7c9(9)也應(yīng)為假。
這樣就有兩個(gè)鏈尾。這是一個(gè)三端點(diǎn)鏈。而鏈頭則是{r8c7, r9c8}(49)的毛刺顯性數(shù)對(duì),而它照樣是可以刪除r7c9(9)的,所以r7c9 <> 9。
這個(gè)例子比較麻煩的是,它帶有四個(gè)魚(yú)鰭,但實(shí)際上我們?cè)谑褂玫臅r(shí)候還是當(dāng)作一個(gè)整體使用的。
Part 3?毛刺SDC


如左圖所示,如果我們嘗試去掉r5c8(2),那么r4c3和r5c128四個(gè)單元格將構(gòu)成SDC結(jié)構(gòu),所以可以刪的數(shù)字全部已經(jīng)標(biāo)注了出來(lái)。
不過(guò),因?yàn)樗强陀^存在的,所以我們視作毛刺,假設(shè)為真并討論其邏輯,此時(shí)就會(huì)引出一條動(dòng)態(tài)強(qiáng)制鏈,并走了兩個(gè)分支。一個(gè)分支將走向r5c1(5),而另外一個(gè)分支則走向了r4c456(4)。顯然,它們都是通過(guò)毛刺r5c1(5)為真得到的,所以它們將同時(shí)成立,故刪數(shù)就是這些4和5,和左圖刪數(shù)的交集,即r5c46(4)和r5c49(5)。
Part 4?毛刺環(huán)
4-1?環(huán) + 雙RCC的ALS-XZ


如左圖所示,我們嘗試把r4c2(3)看作毛刺,假設(shè)為假的話,r34c24將會(huì)構(gòu)成一個(gè)雙RCC的ALS-XZ,當(dāng)然它也算一個(gè)普通的環(huán)結(jié)構(gòu),不過(guò)刪數(shù)理解起來(lái)也和之前的方式一樣:首先刪除弱關(guān)系的交集,然后再來(lái)看ALS區(qū)域涉及的數(shù)字,組成數(shù)組,刪除交集。所以左圖的所有刪數(shù)我們都使用了紅色標(biāo)注出來(lái)了。
再看右圖,當(dāng)r4c2(3)為真的時(shí)候,我們不得不討論真的時(shí)候的情況,此時(shí),我們利用r4c2(3)為真的特性,向下排除,得到r9c2 <> 3,此時(shí),右圖給出嵌套ALS結(jié)構(gòu)的環(huán)就成立了,刪數(shù)也全部都標(biāo)注出來(lái)了。
可以從示例里面看到,它們兩個(gè)環(huán)的刪數(shù)是有部分相同的,所以我們?nèi)〕鱿嗤糠郑ㄉ罴t色),就是這個(gè)毛刺環(huán)結(jié)構(gòu)的刪數(shù)了。
可能你會(huì)問(wèn)我,到底這里說(shuō)的毛刺環(huán)指的是左邊還是右邊的環(huán)。實(shí)際上都可以,這一點(diǎn)并不重要,不過(guò)我更喜歡稱(chēng)呼的毛刺環(huán)指的是右邊這個(gè),因?yàn)橛疫吤虨檎娴臅r(shí)候得到的結(jié)果,作為強(qiáng)調(diào)來(lái)說(shuō),確實(shí)右側(cè)的重要性更大。
4-2?環(huán) + ALP
下面要講到的例子是最后一個(gè)毛刺的示例,不過(guò)示例非常精彩,而且富有挑戰(zhàn)性。


如左圖所示,我們嘗試把r13c2(1)看作毛刺的話,那么就會(huì)產(chǎn)生這樣的一個(gè)環(huán):
可以看到,把以前學(xué)到的所有知識(shí)點(diǎn)代入,可以理解到大部分的邏輯,但r2c7(1)-r2c4(5)是很難立刻明白原因的,你可以嘗試想想看,如果你能獨(dú)立明白它,那么恭喜你,你對(duì)以前的知識(shí)已經(jīng)真正做到了靈活運(yùn)用。如果沒(méi)有,也沒(méi)有關(guān)系,下面我們我們來(lái)講解一下左圖這個(gè)弱關(guān)系到底是怎么產(chǎn)生的。
首先,我們要明白鏈的基本構(gòu)造原理是基于頭尾至少有一個(gè)為真,形成強(qiáng)關(guān)系的。所以圖上我們可以率先得到r2c4(5)和r2c7(1)不同假,即至少有一個(gè)為真。那么我們就不妨考慮一下這兩個(gè)節(jié)點(diǎn)的真假情況。
如果兩個(gè)節(jié)點(diǎn)同真,則觀察b1,由于毛刺此時(shí)假設(shè)為假,所以放下1的位置只有r1c1這一處,而5本身也只有r1c1一處位置。說(shuō)白了,1和5此時(shí)被壓在r1c1里。顯然兩個(gè)單元格是無(wú)法填入一個(gè)數(shù)字的,所以出現(xiàn)矛盾,故兩個(gè)節(jié)點(diǎn)不同真。
但是,兩個(gè)節(jié)點(diǎn)一共只有四種組合:真真、真假、假真、假假。顯然假假不允許(強(qiáng)關(guān)系定義不同假),真真也不允許(剛才證明得到1和5無(wú)法放進(jìn)去)。所以,只有兩種情況,即一真一假。既然是一真一假,那么會(huì)發(fā)生什么事情呢?
第一,這兩個(gè)節(jié)點(diǎn)可以形成弱關(guān)系了。因?yàn)閮蓚€(gè)節(jié)點(diǎn)的關(guān)系是一真一假,既然是一真一假,那么這種情況就既滿足強(qiáng)關(guān)系的定義,也滿足弱關(guān)系的定義(一真一假的情況恰好處于兩個(gè)定義的交集上),所以兩個(gè)節(jié)點(diǎn)的關(guān)系既可以按強(qiáng)關(guān)系處理,也可以按弱關(guān)系處理。而此時(shí),我們當(dāng)然喜歡讓結(jié)構(gòu)更完美,即環(huán)比鏈更好(刪數(shù)更多),所以我們會(huì)優(yōu)先將其當(dāng)作弱關(guān)系處理,所以弱關(guān)系就成立了。待會(huì)兒我們還會(huì)用到這個(gè)弱關(guān)系。
第二,會(huì)讓涂色的五個(gè)單元格{r1c1, r2c1347}構(gòu)成關(guān)于1和5的欠一數(shù)對(duì)結(jié)構(gòu)(ALP)。這一點(diǎn)很神奇,可事實(shí)確實(shí)如此。不論r2c4(5)為真,還說(shuō)r2c7(1)為真,我們都可以確定b1里能放下1和5的位置都只能放在r1c1里,所以r1c1實(shí)際上只能放1和5,也因此,欠一數(shù)對(duì)就成立了。
既然得到了兩個(gè)結(jié)論,那么環(huán)的刪數(shù)就很明確了:首先是我們之前知識(shí)能夠刪除的地方:r1c7(24)、r467c8(9)。那么r1c1(24)和r2c5(1)則是由于剛才的欠一數(shù)對(duì)成立時(shí),產(chǎn)生的刪數(shù)(欠一數(shù)對(duì)成立會(huì)同時(shí)使得b1和c2上產(chǎn)生1、5的待定的顯性數(shù)對(duì)),所以刪除其余位置的1和5。當(dāng)然,就b1而言,r1c1只能填入1和5,所以2和4當(dāng)然就刪掉了。所以總的來(lái)說(shuō),第一個(gè)圖能得到這樣的結(jié)論。
我們?cè)賮?lái)看右圖。右圖看起來(lái)特別復(fù)雜,但實(shí)際上我們只要掌握一點(diǎn)就好:當(dāng)毛刺引入強(qiáng)制鏈(即設(shè)為真)的情況時(shí),我們只需要找出所有強(qiáng)關(guān)系處能對(duì)應(yīng)到的刪數(shù),而且這個(gè)刪數(shù)在原情況(毛刺設(shè)為假)時(shí)是可以刪掉的的話,那就可以作為整個(gè)技巧的刪數(shù)結(jié)論了。所以,我們就來(lái)嘗試找出結(jié)果。我們引入了一個(gè)動(dòng)態(tài)強(qiáng)制鏈,下面簡(jiǎn)單敘述一下路徑。首先從毛刺r13c2(1)為真出發(fā),得r4c2(1)假、r4c2(3)真、r4c89(3)假、r45c9(3)真。此時(shí)分兩個(gè)分支走向:第一個(gè)分支是走上面r23c9(3)假、r23c9(47)毛刺顯性數(shù)對(duì)真結(jié)束;第二個(gè)分支則是走下面r5c9(5)假、r6c8(5)真、r9c8(5)假、r9c8(9)真、r1c8(9)假。此時(shí)走兩個(gè)分支方向:由于r1c8(9)假的緣故,所以b1存在ALS區(qū)域,使得r1c8(9)=r2c7(1)成立;走另外一個(gè)方向則是r1c8(9)假的緣故,只得使r1c8(2)真(雙值格)。于是,我們?cè)诼窂缴戏謩e得到了r1c8(2)真、r2c7(1)真、r23c9(47)毛刺數(shù)對(duì)真、r9c8(9)真,所以它們對(duì)應(yīng)到的刪數(shù)r1c1(2)、r1c7(24)、r467c8(9)都是這個(gè)動(dòng)態(tài)強(qiáng)制鏈路徑上能排除的數(shù)字情況。而對(duì)應(yīng)左圖,只有r1c1(4)不能刪,其它的數(shù)字全部能刪。所以,整個(gè)技巧里,除了r1c1(4)不可以刪以外,右圖里的所有刪數(shù)全部都可以作為結(jié)論成立。即,整個(gè)題目的刪數(shù)如下圖所示。

Part 5?毛邊的定義
如果毛刺是“技巧 + 1”的話,那么毛邊則是“技巧 + 2”??雌饋?lái)差別不大,但實(shí)際上在使用過(guò)程之中,我們并非是將這兩個(gè)特殊的部分作為強(qiáng)制鏈的形式進(jìn)行挨個(gè)討論的,而是構(gòu)成強(qiáng)弱關(guān)系來(lái)討論。
5-1?強(qiáng)毛邊


如左圖所示,可以看到,在c24上一共有6個(gè)1。如果我們把r2c2(1)和r4c4(1)拋開(kāi)不算的話,恰好就構(gòu)成了一個(gè)二鏈列結(jié)構(gòu)。但是由于客觀的存在,導(dǎo)致我們沒(méi)辦法使用這個(gè)技巧,所以我們只能加入鏈的思維。
此時(shí)由于是兩個(gè)毛刺,所以我們不得不分四種情況討論:真真、真假、假真、假假。雖然看起來(lái)很多,但實(shí)際上我們依舊可以簡(jiǎn)化邏輯。首先,它們同為假的時(shí)候,二鏈列的結(jié)構(gòu)就成立了,所以我們把它單獨(dú)算成一種情況;而剩下三種,我們可以發(fā)現(xiàn),真真、真假、假真這三種情況可以直接一并稱(chēng)為“不同假”。而不同假即為強(qiáng)關(guān)系,所以我們還有一種情況,就是直接把它們用強(qiáng)關(guān)系相連,接著就有了右圖這樣的不連續(xù)環(huán)結(jié)構(gòu):r5c7(1)=r5c2-r9c2(2)=r89c2-r2c2=r4c4-r4c9=r5c7(1)。可以看到,這個(gè)結(jié)論可以直接得到r5c7 = 1的結(jié)果,而原來(lái)的二鏈列可以刪除r5c7(1)對(duì)應(yīng)到的r9c7(1),所以,r9c7(1)即該技巧的結(jié)論。
可以發(fā)現(xiàn),這一則示例我們利用了四種情況來(lái)簡(jiǎn)化為兩種:同假形成結(jié)構(gòu)和強(qiáng)關(guān)系。這種構(gòu)造形式我們就稱(chēng)為毛邊(Bi-burr),可以從英文名發(fā)現(xiàn),它就是兩個(gè)毛刺(Bi-前綴加上burr)?!斑叀卑凳緝蓚€(gè)節(jié)點(diǎn)連接在一起形成鏈結(jié)構(gòu)的一條邊。
可以從示例所分的四種情況里發(fā)現(xiàn),既然我們可以劃分為強(qiáng)關(guān)系和同假,那么是否也可以劃分為弱關(guān)系和同真呢?答案是肯定的,因?yàn)槿蹶P(guān)系對(duì)應(yīng)不同真,而恰好跟同真是互斥的情況。
5-2?弱毛邊


如左圖所示,如果我們假設(shè)r4c2(1)和r6c7(1)同真和不同真,會(huì)怎么樣呢?假設(shè)它們不同真,我們首先可以得到的結(jié)果是,不論是同假也好還是有一個(gè)填入也好,我們都有r4c2(7)=r6c7(6),說(shuō)明這一點(diǎn)也很簡(jiǎn)單:當(dāng)兩個(gè)1同假時(shí),它們就直接填進(jìn)去了,顯然不同假,所以這個(gè)強(qiáng)關(guān)系成立;如果有一個(gè)為真,則另外一個(gè)單元格必須填入6或者7這個(gè)數(shù)字,這便使得兩個(gè)單元格的6和7不同假了,所以依然是強(qiáng)關(guān)系。于是,我們利用上這個(gè)強(qiáng)關(guān)系,我們可以尋找到一個(gè)連續(xù)環(huán)結(jié)構(gòu)。
不過(guò)有一個(gè)問(wèn)題。我們這個(gè)例子在講弱毛邊,顯然應(yīng)當(dāng)是同真和不同真的情況,但是左圖卻用的是強(qiáng)關(guān)系(即不同假)。不同假和同真并非是互斥的,所以我們證明思路是否出現(xiàn)了問(wèn)題和漏洞呢?其實(shí)不然。這一點(diǎn)就得用到環(huán)的特性了。之前環(huán)里有一個(gè)特殊的特性,環(huán)內(nèi)的任意關(guān)系都可以切換,即強(qiáng)關(guān)系可以視為弱關(guān)系;而弱關(guān)系則可以視為強(qiáng)關(guān)系。既然環(huán)內(nèi)的任意相鄰兩個(gè)節(jié)點(diǎn)都是一真一假的話,那么顯然我們就可以把這里r4c2(1)和r6c7(1)作為弱關(guān)系來(lái)看待。所以實(shí)際上并沒(méi)有出現(xiàn)問(wèn)題。
接著我們來(lái)看右圖。由于左圖我們是當(dāng)作不同真處理了,所以右圖必須是同真的情況??梢钥吹?,當(dāng)兩個(gè)1同真后,對(duì)r7排除,就可以得到r7c27(1)為假的結(jié)果,于是我們就有了r7c27(1)=r7c7(9)的強(qiáng)關(guān)系。接著向上連接,最終可以得到r2c9(7)為真。所以實(shí)際上,這個(gè)例子我們可以通過(guò)r4c2(1)和r6c7(1)同真而得到r2c9(7)為真。
可是例子刪什么數(shù)字呢?左圖是一個(gè)環(huán),可以刪除的是兩個(gè)數(shù)字:r2c2(7)和r8c7(6),而在右圖我們得到了r2c9(7)為真的結(jié)果,所以r2c2(7)和它是同行的,所以可以刪除掉,而r8c7(6)就不行了。所以這個(gè)例子最終可以刪除的數(shù)字只有r2c2(7)。
你也別小看了它,因?yàn)檫@個(gè)題目就這一個(gè)技巧就可以破解。
可以發(fā)現(xiàn),弱毛邊和強(qiáng)毛邊的使用有一點(diǎn)點(diǎn)小的區(qū)別是,弱毛邊在處理同真的情況的時(shí)候,我們利用的方式一般有兩種:一種是通過(guò)像上圖這樣的排除,進(jìn)而得到想要的強(qiáng)關(guān)系;而另外一種則是通過(guò)結(jié)構(gòu)的占位來(lái)得到強(qiáng)關(guān)系。所以弱毛邊用起來(lái)比強(qiáng)毛邊更靈活。
接下來(lái)我們?cè)賮?lái)看看一些特殊的結(jié)構(gòu)或技巧都如何利用毛邊進(jìn)行解題。
Part 6?一些常見(jiàn)技巧里的毛邊
6-1?BUG + 3


如圖所示,這是一個(gè)BUG + 3結(jié)構(gòu),其中三個(gè)真數(shù)分別是r2c9(4)、r7c9(8)和r9c6(4)。為了好用毛邊結(jié)構(gòu),我們將兩個(gè)4作為毛邊來(lái)看待,并使用強(qiáng)毛邊來(lái)推導(dǎo)。
假設(shè)r2c9(4)和r9c6(4)同假,則由于BUG + n要求所有真數(shù)不同假,所以只得讓r7r9(8)為真,于是引出一條強(qiáng)制鏈,得到r7c2(4)為真,所以此時(shí)可以刪除r7c6(4)。
接著我們假設(shè)r2c9(4)和r9c6(4)不同假,則它們形成強(qiáng)關(guān)系,于是可以看到一個(gè)環(huán)結(jié)構(gòu),依然可以得到刪數(shù)r7c6(4)。
所以不論哪種情況都可以刪除r7c6(4),所以它就是這個(gè)技巧的結(jié)論。
6-2?XR + 3

如圖所示,如果r5c6(9)為真,則直接可以刪除r2c6(9);當(dāng)它為假的時(shí)候,我們就引出了一條毛邊r3c4(6)=r8c6(1),按照?qǐng)D上給出的方向進(jìn)行推理,最終我們就可以得到刪數(shù)結(jié)果。需要闡述的地方是上面的ALS區(qū)域和假SDC區(qū)域。
ALS區(qū)域里,如果給出的5和6同真,則會(huì)導(dǎo)致ALS區(qū)域沒(méi)有5和6,致使填數(shù)少掉兩種,2、7、9又無(wú)法填滿四個(gè)單元格,導(dǎo)致出錯(cuò)。當(dāng)然,這里你也可以看互補(bǔ)的視角:r2無(wú)法填入6(1、3、4、8是確定值,而原視角涉及的是2、7、9,所以互補(bǔ)視角只涉及5和6,而5把6該填的位置占了);而假SDC區(qū)域里,如果5和9同假,則會(huì)使得區(qū)域里只有3和6,且都不跨區(qū),所以填數(shù)一定不相同,而三個(gè)單元格必須要填入三種不同的數(shù)字,而此處只剩下3和6兩種數(shù)字可填,所以產(chǎn)生了矛盾。
當(dāng)然,這個(gè)例子你也可以叫毛刺,如果你強(qiáng)調(diào)的是r5c6(9)的真假討論的話。之所以稱(chēng)為毛邊,是考慮到拓展矩形的真數(shù)的填數(shù)情況而設(shè)定的。如果同假,則r5c6(9)為真,而如果不同假,就形成強(qiáng)關(guān)系。所以其實(shí)這兩種說(shuō)法只是針對(duì)的側(cè)重點(diǎn)不同罷了,沒(méi)有必要糾結(jié)。
6-3?毛邊對(duì)交空矩形
下面我們來(lái)看一點(diǎn)精彩的例子:毛邊和對(duì)交空矩形到底會(huì)交織出什么樣的邏輯呢?


如左圖所示。如果我們嘗試讓r8c5(8)和r9c9(4)同假,此時(shí)我們就可以得到b9的空矩形區(qū)域和兩個(gè)關(guān)于4和9的雙值格,于是空矩形欠一數(shù)對(duì)就這樣誕生了。所以,r8c2(4)便是此時(shí)的刪數(shù)。注意,這是當(dāng)r8c5(8)和r9c9(4)同假時(shí)才得到的刪數(shù),并不是全局的刪數(shù)。接著,由于r8c2(4)為假,那么由于ALS的關(guān)系,r4c2(1)為真。所以,此時(shí)可以刪除掉r2c2(1)。
接著看右圖。由于同假是一種情況,那么反面情況自然就是不同假,即強(qiáng)關(guān)系了。所以我們必須利用上r8c5(8)=r9c9(4)。于是我哦們能夠找到上圖的鏈結(jié)構(gòu),注意b3里有一個(gè)ALS區(qū)域。
可以看到,不論哪種情況,我們都可以得到r2c2(1)是刪數(shù)的結(jié)論,所以r2c2(1)即為刪數(shù)。
6-4?毛邊環(huán)

如圖所示,這個(gè)例子可能也算毛邊里比較難理解的例子了,但邏輯依舊很清晰。如果r9c2(7)為假,則我們可以觀察AALS區(qū)域{r8c12, r9c2}里,立刻可以找到一個(gè)強(qiáng)關(guān)系r8c1(1)=r8c2(6),這樣我們就可以利用這個(gè)強(qiáng)關(guān)系,進(jìn)而形成一個(gè)環(huán)結(jié)構(gòu)(藍(lán)色的強(qiáng)弱關(guān)系畫(huà)出來(lái)的這部分)。
得到這個(gè)結(jié)構(gòu)后,我們就得到了環(huán),所以順帶也就得到了這個(gè)環(huán)的一個(gè)刪數(shù)r7c1(3)。而之前說(shuō)過(guò),刪數(shù)和結(jié)構(gòu)是成弱關(guān)系的,所以它們可以用弱關(guān)系連起來(lái)。所以實(shí)際上我們開(kāi)始的這兩個(gè)強(qiáng)關(guān)系大致是這樣:設(shè)r9c2(7)為假,則r9c2(7)=環(huán)結(jié)構(gòu)-r7c1(3)。接著繼續(xù)向下推導(dǎo),我們可以得到一條完整的鏈,一直到r9c4(7)。
這里需要闡述一下r2c4(9)-r9c5(2)。如果它們同真,則c4上2和6將無(wú)法填數(shù),因?yàn)槎急粩D入r5c4一個(gè)單元格里,顯然它們是不能同時(shí)填入這個(gè)單元格的,所以矛盾。
最后,由于整條鏈結(jié)構(gòu)(紅色)成立,所以刪數(shù)也就成立了:r9c3(7)。需要注意的是,如果我們把r9c2(7)和r9c5(7)用弱關(guān)系連起來(lái)的話,那這條鏈就已經(jīng)變?yōu)榱艘粋€(gè)完整的環(huán),不過(guò)遺憾的是,這個(gè)環(huán)只有r9c3(7)一個(gè)刪數(shù),所以我把它畫(huà)成了鏈。反正只有一個(gè)刪數(shù),就沒(méi)必要畫(huà)成環(huán)了。
Part 7?總結(jié)
至此,毛刺毛邊的內(nèi)容就全部結(jié)束了,而且,構(gòu)造也就結(jié)束了,而且,鏈的內(nèi)容我們就全部講完了。
可以看到的是,鏈里給出的所有例子都非常的精彩,而且刪數(shù)也非常值得去反復(fù)推敲,所以在自己做題的時(shí)候,希望你們能做到“記、觀、用、活”這四個(gè)點(diǎn)。
記就是記憶,能記住這些鏈結(jié)構(gòu)都怎么用,為啥這么用(why),什么時(shí)候這么用(when),在哪里可以用(where),如何用(how)。
觀就是觀察,當(dāng)我們能夠熟練到快速理解和看懂整體邏輯的時(shí)候,我們就可以嘗試自己去找了。因?yàn)槭炀毧炊壿嫊r(shí),你就已經(jīng)掌握了眾多鏈的使用方式,也就順帶擁有了如何尋找鏈的一些基礎(chǔ)經(jīng)驗(yàn),我們就可以通過(guò)這些基礎(chǔ)經(jīng)驗(yàn)來(lái)尋找鏈結(jié)構(gòu)。
用就是使用,當(dāng)能做到觀察到后,我們應(yīng)當(dāng)學(xué)會(huì)如何去使用它。這一點(diǎn)不同于觀察,使用鏈和觀察鏈?zhǔn)莾苫厥?,?dāng)觀察到的時(shí)候,不一定能找到刪數(shù)。而且一些環(huán)結(jié)構(gòu),它的刪數(shù)有時(shí)候隱藏得很深(比如嵌入AUR之類(lèi)的東西)。這個(gè)時(shí)候就必須得靠自己去逐個(gè)驗(yàn)證和得到,然后熟練于心。
活就是靈活,當(dāng)我們能夠做到熟練使用教程文檔給出的使用方式后,就可以嘗試去找出一些教程里沒(méi)有給出的強(qiáng)弱關(guān)系的證明方式和邏輯。我們?cè)趯W(xué)習(xí)這些東西的時(shí)候,可以看到技巧是非常多,也非常復(fù)雜的。我們?cè)诮坛涛臋n里不可能也沒(méi)有必要對(duì)每一個(gè)類(lèi)型的技巧都給出一個(gè)示例,這樣是不現(xiàn)實(shí)的,所以在做題的時(shí)候,我們利用我們學(xué)到的東西,可以得到一些我們學(xué)不到的東西,比如我們學(xué)習(xí)了UR,我們可以將UR同時(shí)通過(guò)數(shù)和形進(jìn)行拓展,進(jìn)而得到新的致命結(jié)構(gòu)(這一點(diǎn)將在后面的內(nèi)容介紹到);又比如我們學(xué)習(xí)了鏈的強(qiáng)弱關(guān)系的證明方式和過(guò)程,它用到了逆否命題,我們就可以通過(guò)一些新的東西,比如借助完全不相關(guān)的逆命題或否命題來(lái)論證一些我們從未嘗試過(guò)的新的玩意兒;再比如我們學(xué)習(xí)了鏈列,我們就可以將它進(jìn)行推廣,放到環(huán)里,形成動(dòng)態(tài)環(huán)來(lái)找刪數(shù),實(shí)際上鏈列也是一個(gè)環(huán),除了之前我們說(shuō)到的標(biāo)準(zhǔn)連續(xù)環(huán)結(jié)構(gòu),是必須讓定義域區(qū)域縮減為強(qiáng)關(guān)系才能形成,那么一般情況下,它實(shí)際上就是一個(gè)動(dòng)態(tài)的環(huán)結(jié)構(gòu),而且它的刪數(shù)就恰好是所有弱關(guān)系都可以用到。
這些東西,都不應(yīng)該全部由我給大家介紹,而是希望大家通過(guò)貫穿整個(gè)教程,來(lái)達(dá)到靈活運(yùn)用的效果。如果你做到了,那么恭喜你,大部分的數(shù)獨(dú)題目都已經(jīng)對(duì)你來(lái)說(shuō)不難了;但是如果你做不到,或者接近于做到,那么也沒(méi)有必要灰心和難受,成功沒(méi)有捷徑可走,但有工具可以幫你快速到達(dá)成功。只要你能靈活掌握,成功就不遠(yuǎn)了。
下一個(gè)部分將為你介紹兩種不同于鏈的包裝模式,它們基于共軛對(duì)和一些零散的結(jié)構(gòu)。