圖說數(shù)獨(dú)高級(jí)解題法PPT教案

1、圖說數(shù)獨(dú)高級(jí)解題法圖說數(shù)獨(dú)高級(jí)解題法唯一數(shù)變形二：透視變形22Hidden onlyone2用直觀法時(shí)，屏蔽一列數(shù)最見的是這個(gè)數(shù)出現(xiàn)在其它規(guī)則中的某個(gè)位置2X2X2X另一種就是在另一規(guī)則中輔數(shù)只出現(xiàn)在一列（行）上，這樣同樣可用來屏蔽另一規(guī)則中的行Intersection Removal 第1頁/共24頁中級(jí)一點(diǎn)的解法 fishy約束對(duì)，強(qiáng)鏈：在某一規(guī)則中某個(gè)候選數(shù)僅出現(xiàn)兩個(gè)單元中。非約束對(duì)，弱鏈：在某一規(guī)則中某個(gè)候選數(shù)僅出現(xiàn)在多個(gè)個(gè)單元中，當(dāng)我沒說。（相對(duì)于約束對(duì)來說，使用時(shí)有個(gè)名字方便）強(qiáng)鏈弱鏈以下為表示方便，用一條線段來表示一條規(guī)則，用實(shí)線表示強(qiáng)鏈用虛線表示弱鏈。AA用刪除線字母表示刪減此

2、輔數(shù)用劃圈字母表示最終填此輔數(shù)用下劃線表示不含此輔數(shù)第2頁/共24頁EAAX-wing兩個(gè)相同輔數(shù)的強(qiáng)鏈由兩個(gè)弱鏈連接，則兩個(gè)弱鏈上的（強(qiáng)鏈上的格除外）其它格的輔數(shù)刪減AAASword-fishAAAAJelly-fishESingles Chains ABCD由強(qiáng)弱強(qiáng)交替奇數(shù)個(gè)鏈長組成的鏈，若A是則E不是，若A不是則B是則C不是則D是，故無論A怎么E不均不包含此輔數(shù)。A EA B C D EE長度為5的單鏈ABCD單鏈的另一說法：單色鏈，把由強(qiáng)鏈連接的點(diǎn)間隔標(biāo)為兩個(gè)顏色（藍(lán)綠），從某一點(diǎn)能同時(shí)看到單色鏈中的兩個(gè)不同著色則此點(diǎn)上的輔數(shù)被刪除。Colouring 第3頁/共24頁AAX-wing

3、AAAX-cycleAAGrouped X-cycle單鏈的端點(diǎn)在同一規(guī)則上組成環(huán)，則所有鏈上弱連接上端點(diǎn)以外的輔數(shù)刪減掉。多于兩個(gè)環(huán)節(jié)的一般改叫環(huán)，原理相同對(duì)于一個(gè)環(huán)節(jié)來說，如果幾個(gè)格可以當(dāng)做一個(gè)單元來處理的話，也可以當(dāng)做X環(huán)來處理，叫做“聯(lián)式X環(huán)”。（也適用于單鏈）第4頁/共24頁Muti-Color B+B+B-B-A-A+A+A+1,由強(qiáng)鏈連成的鏈圖B2,由強(qiáng)鏈連成的放射圖型A3,每個(gè)A+都可以看到一個(gè)B+或B-4,A-看不到任何一個(gè)B5,所有A+到B的弱鏈中既有A+到B+的也有A+到B-的=A-就是此輔數(shù)最短的B鏈只由一個(gè)強(qiáng)鏈組成第5頁/共24頁ABACBCCY-wingY-wing

4、由三個(gè)單元格組成中心為AB兩輔數(shù)，兩邊分別為BC和AC，則能同時(shí)看到BC和AC的單元格中的輔數(shù)C被刪減。ABACBCCY-wing chainsABABY-wing chains：Y-wing中AB格被奇數(shù)點(diǎn)的強(qiáng)鏈代替EBACBCCXY-chainsAEXY-wing：Y-wing中AB格被中間值E組成AE-EB鏈代替，則中間變量不限于一個(gè)可多個(gè)順序傳遞。Y-wing不同于單鏈，它是由限制單元格輔數(shù)個(gè)數(shù)為前題的，所以并不要求所有連接都是強(qiáng)鏈第6頁/共24頁與唯一數(shù)一樣，XY類的鏈也有相應(yīng)的隱性表示.ABACBCHidden Y-wing由ABC的三個(gè)強(qiáng)鏈組成Y鏈，顯然這三個(gè)格里只能出現(xiàn)這三個(gè)對(duì)

5、，其它候選數(shù)全部刪減。B+B-B-左圖是單色的一部分，但是它有一個(gè)非常重要的性質(zhì)：傳遞。它可以加入到任意鏈環(huán)中進(jìn)行鏈的傳遞延伸。.ABACBCB+A+Hidden XY-wing chains或XY-loop,XY-cycle.ABACBCHidden Y-wing chainsorX-cycle,X-loop.AB.AB第7頁/共24頁XZYZXYZZXYZ-Wing兩個(gè)規(guī)則的交集中包含XYZ，其中一個(gè)包含XZ另一個(gè)包含YZ，則交集中其它點(diǎn)上的輔數(shù)Z刪減XZYZWXYZZWXYZ-WingWZ第8頁/共24頁G守護(hù)者守護(hù)者：由偶數(shù)個(gè)強(qiáng)鏈組成的鏈接，兩個(gè)端點(diǎn)的弱連接上其它候選數(shù)就是守護(hù)者，如果

6、守護(hù)者僅有一個(gè)那就可以確定它就是這個(gè)數(shù)；同時(shí)A，E格的輔數(shù)被刪減。1,把ABCD看成單鏈刪減E。2,由強(qiáng)鏈關(guān)系確定：D,C,B,A。3,AE所在規(guī)則內(nèi)的”守護(hù)者”G被確定。守護(hù)者 Guardians Broken Wings, Turbot-Fish EABCD也可以看成單色（單鏈）和XY-chains來解。如果是單個(gè)格組成則可直接確定值第9頁/共24頁ABABAB雙向環(huán)雙向環(huán)由四個(gè)單元格組成中心為AB兩輔數(shù)，兩邊分別為A和B的強(qiáng)鏈接，另一角為AB,與A和B在同一規(guī)則內(nèi)。則這兩個(gè)弱鏈接上其它的A/B被刪減.尋找法:先找兩個(gè)AB,如果從一個(gè)AB出發(fā)分別有A和B的強(qiáng)鏈,這兩個(gè)強(qiáng)鏈的另一端正好能看到

7、另一個(gè)AB格.AB第10頁/共24頁Unique Rectangles 唯一矩陣12121212Deadly Pattern 致命樣式如左圖在兩個(gè)宮中的兩行兩列組成矩形，不管填1還是2都會(huì)有兩個(gè)解，這與數(shù)獨(dú)唯一解的規(guī)則不符。12x.121212唯一矩陣 1若右下角為1或2則終盤中這4點(diǎn)可交換從而導(dǎo)致終盤不唯一，故右下角不能為1或2，刪減之。注：要求4個(gè)格占據(jù)兩行兩列兩宮。僅限于在兩個(gè)宮內(nèi)，分在4個(gè)宮內(nèi)的不是。這才剛用到數(shù)獨(dú)唯一解這個(gè)性質(zhì)，如果有的網(wǎng)站出的題有多解就不能用這個(gè)了第11頁/共24頁ABCABCABAB唯一矩陣形 2由于Roof兩格不能為AB組合，故Roof中必包含C，與Roof兩格

8、屬同一規(guī)則的其它格中輔數(shù)C被刪減。FloorRoofCCABCABABCABC2B，豎著的樣式ABCDABCDABABCDCDCD數(shù)對(duì)擴(kuò)展ABDABCABABCDECDECDE三數(shù)擴(kuò)展第12頁/共24頁ABCABABCABABDEABABCAB4B，兩個(gè)都是C也不是必需的，在CD中必選一即可。ABCXABEFABABABM唯一矩陣 3（隱形）Roof只有3組含AB，如是M則前兩組必為AB組合，故不是M，M被刪減之。唯一矩陣 4(自宮)由于不能是AB組合，則C必存在于此，那AB必舍其一，就看哪個(gè)必需了。如果A是強(qiáng)鏈就刪B害不了別人就害自己吧這個(gè)東西也有二數(shù)三數(shù)的擴(kuò)展第13頁/共24頁空矩型Emp

9、ty Rectangle (ER) 如果一個(gè)宮內(nèi)的4個(gè)角都不包含此輔數(shù)，它就叫空矩形。叫四角空更好。CDBA當(dāng)十字中心C與一個(gè)強(qiáng)鏈AB組成矩形時(shí)，刪減D矩形的變化若輔數(shù)在行上 - A - B - D,，若在列上則 D，故D上的輔數(shù)刪減。第14頁/共24頁yaxaAL:在一個(gè)規(guī)則中的兩個(gè)格（或多個(gè)）通過一個(gè)中間量a傳遞，在此規(guī)則中x或y至少有一個(gè)存在，即：如果不存在x則存在y，反之亦然。ybxaxyaAyx這樣記錄一個(gè)ALS集AaAyxbByx*ALS:兩個(gè)AL集(AB)，若同色端點(diǎn)(a)在一個(gè)規(guī)則內(nèi)，則另一個(gè)顏色的兩個(gè)端點(diǎn)(b)所在規(guī)則交集上的格(*)同一輔數(shù)可以刪除。x,yAbaaAyxbB

10、yz*xzCc第15頁/共24頁下的一個(gè)例題，A集一端是r4c1r4c3(找交集時(shí)看做一個(gè)格)，另一端r5c3，B集由34兩個(gè)數(shù)傳遞，兩端是r2c7和r6c7，C集由789三個(gè)數(shù)傳遞，兩端分別是r1c3和r1r8。若A中r4c1r4c3中包含9則r6c2,r4c9不包含9；若A中r4c1r4c3不包含9，則A集包含4(r5c3)則C集不包含4,由AL定義C集包含5，由于C集包含5(r1c8=5，弱鏈)則B集中不包含5,由AL定義B集中包含9則r4c9,r6c2不包含9,故：r4c9,r6c2中的9刪減。第16頁/共24頁ABCDEABCDABECDE1,在一個(gè)宮的三個(gè)格（M組）里（同一行或列上

11、）只包含5個(gè)候選數(shù)；2,它們所在的兩條規(guī)則（宮，行或列）各包含其中兩（不重復(fù)）；3,在這兩條規(guī)則其它格里的這兩個(gè)和5個(gè)候選數(shù)中的另外一個(gè)被刪減。證明： 由于AB在存在，組M不能同時(shí)包含A和B，同理也不能同時(shí)包含C和D，因?yàn)槿齻€(gè)格要填三個(gè)數(shù)，所以三個(gè)格候選數(shù)為E、AB中的一個(gè)、CD中的一個(gè)，則與AB格所在的同一規(guī)則中，組M和AB必然包含ABE故此規(guī)則中所有候選數(shù)ABE刪減，同理與CD格同一規(guī)則中的候選數(shù)CDE被刪減。第17頁/共24頁這個(gè)東西確實(shí)不好說，叫列舉吧。X,Y可有以下幾種可能組合：1.3,22.3,5 （不可能，這樣B就無數(shù)可填了）3.5,24.5,5 （太不可能了）5.7,2 （不可

12、能，這樣A無數(shù)填了）6.7,5 （不可能，這樣C無法填了）剩下可能的組合是：3,2；5,2；結(jié)果 X可填3和5，7被刪減 Y只能填2，5被刪減。第18頁/共24頁定義：定義：Bivalue Universal Grave (BUG)全雙值墳?zāi)梗喝p值墳?zāi)梗涸谒形唇忾_的格子里都有兩個(gè)候選數(shù)，如果一個(gè)候選數(shù)出現(xiàn)在某個(gè)規(guī)則里，它一定出現(xiàn)兩次。BUG-Lite ：它的局部是BUG，即如果去掉某些單元中的某些候選數(shù)，它就是一個(gè)BUG。poly-valued cell 聚值單元：在BUG-Lite里，候選數(shù)多于兩個(gè)的單元。Localized BUG Move (LBM) ：在單元格中選擇一或兩候選數(shù)使它

13、成為一個(gè)BUG。non-BUG candidate 非非BUG候選候選：在LBM中被選出的那些候選數(shù)，所有的這些值不包含在BUG內(nèi)。BUG+n ：一個(gè)BUG包含n個(gè)聚值單元，BUG+1即有一個(gè)聚值單元的BUG。原理：原理：BUG的出現(xiàn)將導(dǎo)致有零或多于一個(gè)的解，這與數(shù)獨(dú)唯一解的規(guī)則相悖，所以BUG是不可能出現(xiàn)的，所以真正可能的值出現(xiàn)在非BUG候選數(shù)之中。結(jié)論結(jié)論1：如果通過LBM能形成BUG，則解中至少有一個(gè)來看到非BUG候選數(shù)。如果非BUG候選數(shù)只有一個(gè)，那它一定是解。結(jié)論結(jié)論2：任何包含全部非BUG候選數(shù)的推理都是有效的。結(jié)論結(jié)論3：任何包含刪減全部非BUG候選數(shù)的推理都是無效的。結(jié)論結(jié)論4

14、：任何刪減能能使其成為BUG+1都是有效的。結(jié)論結(jié)論5：結(jié)論1，2，3適用于BUG-Lite。第19頁/共24頁 2 9 8 | 47 567 56 | 3 1 45 7 4 5 | 2 1 3 | 6 9 8 1 3 6 | 48 58 9 | 2 7 45 -+-+- 5 1 4 | 6 3 8 | 7 2 9 6 2 9 | 17 57 15 | 8 4 3 8 7 3 | 9 4 2 | 1 5 6 -+-+- 4 5 2 | 18 68 16 | 9 3 7 3 8 1 | 5 9 7 | 4 6 2 9 6 7 | 3 2 4 | 5 8 1 如果把5去掉它就是一個(gè)BUG，這樣將會(huì)

15、出現(xiàn)兩組解。R1C5就是聚值單元LBM就是將5取出使其剩余成為BUG，5就是”非BUG“候選數(shù)。此題中只有一個(gè)聚值單元，它就叫BUG+1由于解中至少有一個(gè)值來自于非BUG候選數(shù)，而些題中非BUG候選數(shù)只有一個(gè)”5“，故此格的解就是5.第20頁/共24頁 3 79 57+9 | 1 2 8 | 49 45+9 6 6 4 25 | 3 7 9 | 8 15 12 8 1 29 | 5 6 4 | 7 39 23 -+-+- 9 5 1 | 7 4 3 | 2 6 8 7 3 4 | 2 8 6 | 19 19 5 2 8 6 | 9 1 5 | 3 47 47 -+-+- 4 27 3 | 8

16、5 1 | 6 27 9 1 6 79 | 4 39 2 | 5 8 37 5 29 8 | 6 39 7 | 14 23+14 14+3 這是一個(gè)BUG+4的題”“后面的是非BUG候選數(shù)根據(jù)結(jié)論1,正解必需至少包含R1C3=9,R1C8=9,R9C8=1,R9C8=4,R9C9=3其中之一。對(duì)上述所有情況進(jìn)行假設(shè)都能推出R1C85,根據(jù)結(jié)論2,R1C85是成立的故將R1C8中的5刪減掉。第21頁/共24頁*-* | 4 28 19 | 3 6 89 | 5 7 12 | | 5 7 3 | 4 1 2 | 9 6 8 | | 28 6 19 | 89 7 5 | 4 3 12 | |-+-+-| | 6 28 4 | 28 3 1 | 7 5 9 | | 1 9 5 | 7 4 6 | 2 8 3 | | 28 3 7 | 29+8 5 89 | 6 1 4 | |-+-+-| | 9 5 6 | 1 2 3 | 8 4 7 | | 3 4 2 | 6 8 7 | 1 9 5 | | 7 1 8 | 5 9 4 | 3 2 6 | *-* 這個(gè)題用BUG在R6C4填8