图说数独高级解题法.ppt

《图说数独高级解题法.ppt》由会员分享，可在线阅读，更多相关《图说数独高级解题法.ppt（25页珍藏版）》请在三一办公上搜索。

1、直观法,2,2,2,4,3,1,5,6,7,8,9,唯一数,Hidden onlyone,Naked onlyone,直观法,辅数法,2,2,2,2,2,2,2,2,2,123456789,在同一规则中某一元素只在一个格中出现,在某一格中只有一个元素出现,规则：根据数独的性质，数独中每一行每一列及每个宫填不重复的1至9数字，这里将行列或宫统称为规则，这样不但便于理解而且还可以直接把它用来处理非常规数独，如锯齿，六角及其它种种大多都可用规则来表示等。,辅数：也就是可选数，一个人人都知的概念，首先假设一个单元格里可以填所有可选数，如果发现它所在的规则里由于某种原因某个数不能出现在些格中，就把它删除

2、掉。直接法不能解决时一般用这种方法。高级解法一般都要用到辅数来解。,12,12,12.,12.,Naked pairs,12,12,12.,12.,12.,12.,12,12,12.,12.,12.,12.,Hidden pairs,裸露对，显性数对：在一个规则中若两个格中只有两个候选数，则其它格子中这两个辅数被删减。,显式对，显性数对：在一个规则中若两个候选数只出现在两个格中，则这两个格子中其它辅数被删减。（与裸露对比）,三连数，四连数，五连数方法同,123,123,123.,123.,Naked Triples,123,123,123.,123.,123,Hidden Triples,12

3、3,123,123,123.,123.,123.,123.,123.,123.,123.,123,并不要求三个格都是123,，有12或13的格也行,Hidden Quads,唯一数变形一：个数变化,只有两个格包含辅数1和2,其它格都不包含,唯一数变形二：透视变形,2,2,Hidden onlyone,2,用直观法时，屏蔽一列数最见的是这个数出现在其它规则中的某个位置,2X,2X,2X,另一种就是在另一规则中辅数只出现在一列（行）上，这样同样可用来屏蔽另一规则中的行,Intersection Removal,中级一点的解法 fishy,约束对，强链：在某一规则中某个候选数仅出现两个单元中。,非约

4、束对，弱链：在某一规则中某个候选数仅出现在多个个单元中，当我没说。（相对于约束对来说，使用时有个名字方便）,强链,弱链,以下为表示方便，用一条线段来表示一条规则，用实线表示强链用虚线表示弱链。,A,A,用删除线字母表示删减此辅数用划圈字母表示最终填此辅数用下划线表示不含此辅数,A,E,A,A,X-wing,两个相同辅数的强链由两个弱链连接，则两个弱链上的（强链上的格除外）其它格的辅数删减,A,A,A,Sword-fish,A,A,A,A,Jelly-fish,E,Singles Chains,A,B,C,D,由强弱强交替奇数个链长组成的链，若A是则E不是，若A不是则B是则C不是则D是，故无论A

5、怎么E不均不包含此辅数。,A EA B C D E,E,长度为5的单链,A,B,C,D,单链的另一说法：单色链，把由强链连接的点间隔标为两个颜色（蓝绿），从某一点能同时看到单色链中的两个不同着色则此点上的辅数被删除。,Colouring,X-cycle X-cycle Grouped X-cycle,A,A,X-wing,A,A,A,X-cycle,A,A,Grouped X-cycle,单链的端点在同一规则上组成环，则所有链上弱连接上端点以外的辅数删减掉。,多于两个环节的一般改叫环，原理相同,对于一个环节来说，如果几个格可以当做一个单元来处理的话，也可以当做X环来处理，叫做“联式X环”。（也

6、适用于单链）,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链只由一个强链组成,AB,AC,BC,C,Y-wing,Y-wing由三个单元格组成中心为AB两辅数，两边分别为BC和AC，则能同时看到BC和AC的单元格中的辅数C被删减。,AB,AC,BC,C,Y-wing chains,AB,AB,Y-wing chains：Y-wing中AB格被奇数点的强链代替,EB,AC,BC,C,

7、XY-chains,AE,XY-wing：Y-wing中AB格被中间值E组成AE-EB链代替，则中间变量不限于一个可多个顺序传递。,Y-wing不同于单链，它是由限制单元格辅数个数为前题的，所以并不要求所有连接都是强链,链的隐含形式,与唯一数一样，XY类的链也有相应的隐性表示,.AB,AC,BC,Hidden Y-wing,由ABC的三个强链组成Y链，显然这三个格里只能出现这三个对，其它候选数全部删减。,B+,B-,B-,左图是单色的一部分，但是它有一个非常重要的性质：传递。它可以加入到任意链环中进行链的传递延伸。,.AB,AC,BC,B+,A+,Hidden XY-wing chains或X

8、Y-loop,XY-cycle,.AB,AC,BC,Hidden Y-wing chainsorX-cycle,X-loop,.AB,.AB,XZ,YZ,XYZ,Z,XYZ-Wing,两个规则的交集中包含XYZ，其中一个包含XZ另一个包含YZ，则交集中其它点上的辅数Z删减,XZ,YZ,WXYZ,Z,WXYZ-Wing,WZ,G,守护者：由偶数个强链组成的链接，两个端点的弱连接上其它候选数就是守护者，如果守护者仅有一个那就可以确定它就是这个数；同时A，E格的辅数被删减。,1,把ABCD看成单链删减E。2,由强链关系确定：D,C,B,A。3,AE所在规则内的”守护者”G被确定。,守护者 Guard

9、ians Broken Wings,Turbot-Fish,E,A,B,C,D,也可以看成单色（单链）和XY-chains来解。,如果是单个格组成则可直接确定值,双向环Bidirection-cycle,AB,A,B,AB,双向环,双向环由四个单元格组成中心为AB两辅数，两边分别为A和B的强链接，另一角为AB,与A和B在同一规则内。则这两个弱链接上其它的A/B被删减.寻找法:先找两个AB,如果从一个AB出发分别有A和B的强链,这两个强链的另一端正好能看到另一个AB格.,A,B,Unique Rectangles 唯一矩阵,12,12,12,12,Deadly Pattern 致命样式如左图在两

10、个宫中的两行两列组成矩形，不管填1还是2都会有两个解，这与数独唯一解的规则不符。,12x.,12,12,12,唯一矩阵 1若右下角为1或2则终盘中这4点可交换从而导致终盘不唯一，故右下角不能为1或2，删减之。,注：要求4个格占据两行两列两宫。仅限于在两个宫内，分在4个宫内的不是。,这才刚用到数独唯一解这个性质，如果有的网站出的题有多解就不能用这个了,ABC,ABC,AB,AB,唯一矩阵形 2由于Roof两格不能为AB组合，故Roof中必包含C，与Roof两格属同一规则的其它格中辅数C被删减。,Floor,Roof,C,C,ABC,AB,ABC,AB,C,2B，竖着的样式,ABCD,ABCD,A

11、B,AB,CD,CD,CD,数对扩展,ABD,ABC,AB,AB,CDE,CDE,CDE,三数扩展,ABC,AB,ABC,AB,ABDE,AB,ABC,AB,4B，两个都是C也不是必需的，在CD中必选一即可。,ABCX,ABEF,AB,AB,ABM,唯一矩阵 3（隐形）Roof只有3组含AB，如是M则前两组必为AB组合，故不是M，M被删减之。,唯一矩阵 4(自宫)由于不能是AB组合，则C必存在于此，那AB必舍其一，就看哪个必需了。如果A是强链就删B,害不了别人就害自己吧,这个东西也有二数三数的扩展,空矩型Empty Rectangle(ER),如果一个宫内的4个角都不包含此辅数，它就叫空矩形。

12、叫四角空更好。,D,B,A,当十字中心C与一个强链AB组成矩形时，删减D,矩形的变化,若辅数在行上-A-B-D,，若在列上则 D，故D上的辅数删减。,ya,xa,AL:在一个规则中的两个格（或多个）通过一个中间量a传递，在此规则中x或y至少有一个存在，即：如果不存在x则存在y，反之亦然。,yb,xa,xy,a,A,y,x,这样记录一个ALS集A,a,A,y,x,b,B,y,x,*,ALS:两个AL集(AB)，若同色端点(a)在一个规则内，则另一个颜色的两个端点(b)所在规则交集上的格(*)同一辅数可以删除。,x,y,A,b,a,a,A,y,x,b,B,y,z,*,x,z,C,c,ALS(Amo

13、st Lock Set Rule),+-+-+-+|459 1%479|%78 3%89|2%58 6|59 569 679|278 289 4|35 1358 13|8 3 2|5 6 1|7 9 4|+-+-+-+|*139 7*139|6 4 5|8 123 1239|6 28*134|9 28 7|34 13 5|24 289 5|238 1 238|49 6 7|+-+-+-+|7 4 39|23 259 6|1 235 8|12359 2569 1369|4 2589 2389|3569 7 239|2359 2569 8|1 7 239|3569 4 239|+-+-+-+A=R

14、4C1,R4C3,R5C3 B=R2C7,R5C7,R6C7 C=R1C3,R1C4,R1C6,R1C8 x=9 y=5 z=4 7,8,9|4-C-5:4 5/1,3-A B-3,4/9.*.9*=r4c9#9,r6c2#9 can be eliminated,下的一个例题，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，

15、由于C集包含5(r1c8=5，弱链)则B集中不包含5,由AL定义B集中包含9则r4c9,r6c2不包含9,故：r4c9,r6c2中的9删减。,Sue-de-Coq(Two-Sector Disjoint Subsets),ABCDE,AB,CD,ABE,CDE,1,在一个宫的三个格（M组）里（同一行或列上）只包含5个候选数；2,它们所在的两条规则（宫，行或列）各包含其中两（不重复）；3,在这两条规则其它格里的这两个和5个候选数中的另外一个被删减。,证明：由于AB在存在，组M不能同时包含A和B，同理也不能同时包含C和D，因为三个格要填三个数，所以三个格候选数为E、AB中的一个、CD中的一个，则与

16、AB格所在的同一规则中，组M和AB必然包含ABE故此规则中所有候选数ABE删减，同理与CD格同一规则中的候选数CDE被删减。,Aligned Pair Exclusion(APE),这个东西确实不好说，叫列举吧。,X,Y可有以下几种可能组合：3,23,5（不可能，这样B就无数可填了）5,25,5（太不可能了）7,2（不可能，这样A无数填了）7,5（不可能，这样C无法填了）剩下可能的组合是：3,2；5,2；结果 X可填3和5，7被删减 Y只能填2，5被删减。,BUG(Bivalue Universal Grave)principle,定义：Bivalue Universal Grave(BUG)

17、全双值坟墓：在所有未解开的格子里都有两个候选数，如果一个候选数出现在某个规则里，它一定出现两次。BUG-Lite：它的局部是BUG，即如果去掉某些单元中的某些候选数，它就是一个BUG。poly-valued cell 聚值单元：在BUG-Lite里，候选数多于两个的单元。Localized BUG Move(LBM)：在单元格中选择一或两候选数使它成为一个BUG。non-BUG candidate 非BUG候选：在LBM中被选出的那些候选数，所有的这些值不包含在BUG内。BUG+n：一个BUG包含n个聚值单元，BUG+1即有一个聚值单元的BUG。原理：BUG的出现将导致有零或多于一个的解，这与

18、数独唯一解的规则相悖，所以BUG是不可能出现的，所以真正可能的值出现在非BUG候选数之中。结论1：如果通过LBM能形成BUG，则解中至少有一个来看到非BUG候选数。如果非BUG候选数只有一个，那它一定是解。结论2：任何包含全部非BUG候选数的推理都是有效的。结论3：任何包含删减全部非BUG候选数的推理都是无效的。结论4：任何删减能能使其成为BUG+1都是有效的。结论5：结论1，2，3适用于BUG-Lite。,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 5

19、7 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，这样将会出现两组解。,R1C5就是聚值单元,LBM就是将5取出使其剩余成为BUG，5就是”非BUG“候选数。,此题中只有一个聚值单元，它就叫BUG+1,由于解中至少有一个值来自于非BUG候选数，而些题中非BUG候选数只有一个”5“，故此格的解就是5.,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-+

20、-+-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 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删减掉。,*-*|4 28 19|3 6 89|5 7 12|5 7 3|4 1

21、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是最快的解法,也可以通过两个单链删除另外的两个候选数8,还可以通过蓝红圈标识的单色把金色圈的8删减,Force chain,大多数的书上最后一页都写上这个东西”强制链”,但很多人不把它归为技术解法.,说起来应该很简单:假设一种情况成立看情况如果发现与规则不符则.,1,单值强制链:尝试某单元的候选数,如果某个数推出不符规则的值则删减之;2,单元强制链:尝试某单元的全部候选,如果都能推同单元格有确定值K或无候选数j则此格确定;3,规则强制链:尝试某规则中所有候选K,如在所有情况下某单元格有确定值(为某值或无某值)则确定;,