图说数独高级解题法PPT教案

1、图说数独高级解题法图说数独高级解题法唯一数变形二：透视变形22Hidden onlyone2用直观法时，屏蔽一列数最见的是这个数出现在其它规则中的某个位置2X2X2X另一种就是在另一规则中辅数只出现在一列（行）上，这样同样可用来屏蔽另一规则中的行Intersection Removal 第1页/共24页中级一点的解法 fishy约束对，强链：在某一规则中某个候选数仅出现两个单元中。非约束对，弱链：在某一规则中某个候选数仅出现在多个个单元中，当我没说。（相对于约束对来说，使用时有个名字方便）强链弱链以下为表示方便，用一条线段来表示一条规则，用实线表示强链用虚线表示弱链。AA用删除线字母表示删减此

2、辅数用划圈字母表示最终填此辅数用下划线表示不含此辅数第2页/共24页EAAX-wing两个相同辅数的强链由两个弱链连接，则两个弱链上的（强链上的格除外）其它格的辅数删减AAASword-fishAAAAJelly-fishESingles Chains ABCD由强弱强交替奇数个链长组成的链，若A是则E不是，若A不是则B是则C不是则D是，故无论A怎么E不均不包含此辅数。A EA B C D EE长度为5的单链ABCD单链的另一说法：单色链，把由强链连接的点间隔标为两个颜色（蓝绿），从某一点能同时看到单色链中的两个不同着色则此点上的辅数被删除。Colouring 第3页/共24页AAX-wing

3、AAAX-cycleAAGrouped X-cycle单链的端点在同一规则上组成环，则所有链上弱连接上端点以外的辅数删减掉。多于两个环节的一般改叫环，原理相同对于一个环节来说，如果几个格可以当做一个单元来处理的话，也可以当做X环来处理，叫做“联式X环”。（也适用于单链）第4页/共24页Muti-Color B+B+B-B-A-A+A+A+1,由强链连成的链图B2,由强链连成的放射图型A3,每个A+都可以看到一个B+或B-4,A-看不到任何一个B5,所有A+到B的弱链中既有A+到B+的也有A+到B-的=A-就是此辅数最短的B链只由一个强链组成第5页/共24页ABACBCCY-wingY-wing

4、由三个单元格组成中心为AB两辅数，两边分别为BC和AC，则能同时看到BC和AC的单元格中的辅数C被删减。ABACBCCY-wing chainsABABY-wing chains：Y-wing中AB格被奇数点的强链代替EBACBCCXY-chainsAEXY-wing：Y-wing中AB格被中间值E组成AE-EB链代替，则中间变量不限于一个可多个顺序传递。Y-wing不同于单链，它是由限制单元格辅数个数为前题的，所以并不要求所有连接都是强链第6页/共24页与唯一数一样，XY类的链也有相应的隐性表示.ABACBCHidden Y-wing由ABC的三个强链组成Y链，显然这三个格里只能出现这三个对

5、，其它候选数全部删减。B+B-B-左图是单色的一部分，但是它有一个非常重要的性质：传递。它可以加入到任意链环中进行链的传递延伸。.ABACBCB+A+Hidden XY-wing chains或XY-loop,XY-cycle.ABACBCHidden Y-wing chainsorX-cycle,X-loop.AB.AB第7页/共24页XZYZXYZZXYZ-Wing两个规则的交集中包含XYZ，其中一个包含XZ另一个包含YZ，则交集中其它点上的辅数Z删减XZYZWXYZZWXYZ-WingWZ第8页/共24页G守护者守护者：由偶数个强链组成的链接，两个端点的弱连接上其它候选数就是守护者，如果

6、守护者仅有一个那就可以确定它就是这个数；同时A，E格的辅数被删减。1,把ABCD看成单链删减E。2,由强链关系确定：D,C,B,A。3,AE所在规则内的”守护者”G被确定。守护者 Guardians Broken Wings, Turbot-Fish EABCD也可以看成单色（单链）和XY-chains来解。如果是单个格组成则可直接确定值第9页/共24页ABABAB双向环双向环由四个单元格组成中心为AB两辅数，两边分别为A和B的强链接，另一角为AB,与A和B在同一规则内。则这两个弱链接上其它的A/B被删减.寻找法:先找两个AB,如果从一个AB出发分别有A和B的强链,这两个强链的另一端正好能看到

7、另一个AB格.AB第10页/共24页Unique Rectangles 唯一矩阵12121212Deadly Pattern 致命样式如左图在两个宫中的两行两列组成矩形，不管填1还是2都会有两个解，这与数独唯一解的规则不符。12x.121212唯一矩阵 1若右下角为1或2则终盘中这4点可交换从而导致终盘不唯一，故右下角不能为1或2，删减之。注：要求4个格占据两行两列两宫。仅限于在两个宫内，分在4个宫内的不是。这才刚用到数独唯一解这个性质，如果有的网站出的题有多解就不能用这个了第11页/共24页ABCABCABAB唯一矩阵形 2由于Roof两格不能为AB组合，故Roof中必包含C，与Roof两格

8、属同一规则的其它格中辅数C被删减。FloorRoofCCABCABABCABC2B，竖着的样式ABCDABCDABABCDCDCD数对扩展ABDABCABABCDECDECDE三数扩展第12页/共24页ABCABABCABABDEABABCAB4B，两个都是C也不是必需的，在CD中必选一即可。ABCXABEFABABABM唯一矩阵 3（隐形）Roof只有3组含AB，如是M则前两组必为AB组合，故不是M，M被删减之。唯一矩阵 4(自宫)由于不能是AB组合，则C必存在于此，那AB必舍其一，就看哪个必需了。如果A是强链就删B害不了别人就害自己吧这个东西也有二数三数的扩展第13页/共24页空矩型Emp

9、ty Rectangle (ER) 如果一个宫内的4个角都不包含此辅数，它就叫空矩形。叫四角空更好。CDBA当十字中心C与一个强链AB组成矩形时，删减D矩形的变化若辅数在行上 - A - B - D,，若在列上则 D，故D上的辅数删减。第14页/共24页yaxaAL:在一个规则中的两个格（或多个）通过一个中间量a传递，在此规则中x或y至少有一个存在，即：如果不存在x则存在y，反之亦然。ybxaxyaAyx这样记录一个ALS集AaAyxbByx*ALS:两个AL集(AB)，若同色端点(a)在一个规则内，则另一个颜色的两个端点(b)所在规则交集上的格(*)同一辅数可以删除。x,yAbaaAyxbB

10、yz*xzCc第15页/共24页下的一个例题，A集一端是r4c1r4c3(找交集时看做一个格)，另一端r5c3，B集由34两个数传递，两端是r2c7和r6c7，C集由789三个数传递，两端分别是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,在一个宫的三个格（M组）里（同一行或列上

11、）只包含5个候选数；2,它们所在的两条规则（宫，行或列）各包含其中两（不重复）；3,在这两条规则其它格里的这两个和5个候选数中的另外一个被删减。证明： 由于AB在存在，组M不能同时包含A和B，同理也不能同时包含C和D，因为三个格要填三个数，所以三个格候选数为E、AB中的一个、CD中的一个，则与AB格所在的同一规则中，组M和AB必然包含ABE故此规则中所有候选数ABE删减，同理与CD格同一规则中的候选数CDE被删减。第17页/共24页这个东西确实不好说，叫列举吧。X,Y可有以下几种可能组合：1.3,22.3,5 （不可能，这样B就无数可填了）3.5,24.5,5 （太不可能了）5.7,2 （不可

12、能，这样A无数填了）6.7,5 （不可能，这样C无法填了）剩下可能的组合是：3,2；5,2；结果 X可填3和5，7被删减 Y只能填2，5被删减。第18页/共24页定义：定义：Bivalue Universal Grave (BUG)全双值坟墓：全双值坟墓：在所有未解开的格子里都有两个候选数，如果一个候选数出现在某个规则里，它一定出现两次。BUG-Lite ：它的局部是BUG，即如果去掉某些单元中的某些候选数，它就是一个BUG。poly-valued cell 聚值单元：在BUG-Lite里，候选数多于两个的单元。Localized BUG Move (LBM) ：在单元格中选择一或两候选数使它

13、成为一个BUG。non-BUG candidate 非非BUG候选候选：在LBM中被选出的那些候选数，所有的这些值不包含在BUG内。BUG+n ：一个BUG包含n个聚值单元，BUG+1即有一个聚值单元的BUG。原理：原理：BUG的出现将导致有零或多于一个的解，这与数独唯一解的规则相悖，所以BUG是不可能出现的，所以真正可能的值出现在非BUG候选数之中。结论结论1：如果通过LBM能形成BUG，则解中至少有一个来看到非BUG候选数。如果非BUG候选数只有一个，那它一定是解。结论结论2：任何包含全部非BUG候选数的推理都是有效的。结论结论3：任何包含删减全部非BUG候选数的推理都是无效的。结论结论4

14、：任何删减能能使其成为BUG+1都是有效的。结论结论5：结论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去掉它就是一个BUG，这样将会

15、出现两组解。R1C5就是聚值单元LBM就是将5取出使其剩余成为BUG，5就是”非BUG“候选数。此题中只有一个聚值单元，它就叫BUG+1由于解中至少有一个值来自于非BUG候选数，而些题中非BUG候选数只有一个”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 这是一个BUG+4的题”“后面的是非BUG候选数根据结论1,正解必需至少包含R1C3=9,R1C8=9,R9C8=1,R9C8=4,R9C9=3其中之一。对上述所有情况进行假设都能推出R1C85,根据结论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 | *-* 这个题用BUG在R6C4填8