数独高阶技巧入门之六——ALS

​在这个系列的第一篇(链及其简单应用)以及第四篇(简单异数链)中已经简单介绍过ALS结构的定义,即n格中存在n+1个不同的候选数 (双值格可视为特殊的ALS结构) 。根据数独规则,在组成ALS的候选数中,必然有且只有一个为假,显然这些候选数各自的数字集两两互为强关系(不可同假,必有一真)。单独的ALS结构不能用来解决问题,但是如果将ALS作为节点把链或者数个ALS联结起来,就有可能利用ALS中各候选数字集互为强关系的特性构成链实现有效的删减,在一些复杂的盘势中起到解题的作用。

需要注意的是,在利用ALS解题的过程中,必须时刻牢记将ALS中的候选数字集作为整体看待。

 
图1-ALS

​图1中除去双值格外,存在ALS结构R2C28{135},B6{289},C3的{3456}数组可视需要灵活拆分为{346}、{3456}2组ALS结构。

一、RCC(Restricted Common Candidate)

要将两个ALS-A和B联结起来,需要用到严格共享候选数RCC。该候选数必须在ALS-A、ALS-B中都有出现,且只能出现在同一个Unit中 (该Unit用来连接两个ALS,可称之为联结单元,为了保证RCC与所在ALS中的其他候选数集构成强关系,联结单元以外的ALS中不能出现该候选数。)

 
图2-RCC01

上图中,存在3组ALS,分别是ALS-A=R1{3678},ALS-B=B2{356}和ALS-C=C6{2567},其中ALS-A、B在B2有RCC=6;ALS-A、C在C6有RCC6;ALS-B、C则不存在RCC( ALS-C在B2外存在6)。

我们可以看到,ALS-A、B的两个RCC 6同处于B2,两者互为弱关系,不能同真,必有一假,而取假值的RCC所在的ALS会从n格n+1个候选数变为n格n个候选数,这样AlmostLocked Sets就去掉了“Almost”变成了Locked Sets,据此可以对它所在Unit其他位置进行相应删减。

在本例中,若R2C5的6为假,则ALS-B变为{35}的数组,可删去图3左大九宫格黄色格中的3;若R1C6的6为假,则ALS-A变为{378}的数组,可删去图3右大九宫格黄色格中的3。我们可以看到,不管哪个6为假,图中“/”所在格内的3都会被删去。

 
图3-RCC02

​二、ALS-XZ

(一)Singly Linked ALS-XZ

我们把上述例子中的删减技巧称为Singly Linked ALS-XZ,具体规则为:若两个ALS可以通过一组RCC(X)联结起来,且两个ALS中除RCC外还有相同的候选数Z,则可删去这两个ALS中Z共同作用格内的其他Z。再来看两个例子:

 
图4-AXZ01

​图4中ALS-A=R1C67{679},ALS-B=R3C289{6789},RCC=6(X),两个ALS中除RCC 6之外,还有相同的候选数7(Z),故可删去两个ALS中7共同作用格亦即R3C56中的7。

 
图5-AXZ02

​图5中ALS-A=B4{34568},ALS-B=B7{378},RCC=3(X),Z=8,可删去两个ALS中8共同作用格即R789C3中的8。

(二)Doubly Linked ALS-XZ

图4、5两例都是两个ALS由一组RCC联结起来的情况,如果存在两组RCC的话,情况就会变得非常有趣。

 
图6-DAXZ01

图6的盘势就是如此,R3的ALS-A={1258}和R9的ALS-B={128}可以通过两组RCC 1和2联结起来。我们在前文曾提到,同组RCC之间互为弱关系,不能同真,取假值的RCC所在的待定数组会去掉待定变成数组。在本例中,如图7所示, 若绿格中的RCC 2取假值,则ALS-A就会变成{158}数组,进而导致紫格中的RCC 1只能为假,使ALS-B变成{28}数组;若绿格中的RCC 1取假值,则ALS-A就会变成{258}数组,进而导致紫格中的RCC 2只能为假,使ALS-B变成{18}数组。

 
图7-DAXZ02

​显然,不管两组RCC中的哪个取假值,最终结果都会导致两个ALS变成Locked Sets(绿{158}紫{28}或绿{258}紫{18},绿色格中的{58}和紫色格{8}可对所在单元其他格进行摈除),可各自删去Locked Sets所在Unit除RCC之外的相关候选数(本例中是R3C3的5和R9C8的8)。此外,若同组RCC同时为假(比如绿格和紫格中的1为假),就会导致另一组RCC同时为真,这种情况不可能出现,故同组RCC之间必须有一个为真,由此可删去同组RCC所在Unit的相关候选数(R5C2的1和R25C9的2)。

至此我们可以给出Doubly Linked ALS-XZ的具体规则:若两个ALS可由两组RCC X1,X2联结,则这两个ALS中除RCC之外的候选数可分别对该ALS所在Unit的其他格进行摈除,同时,两组RCC可分别对该组所在Uint其他格进行摈除。

我们再来看两个例子。

 
图8-DAXZ03

​本例中ALS-A=R2C239 {2479},ALS-B=R4C23 {124},X=2,4。根据规则可删去:

1、R2其他位置的7、9(红色);

2、B4和R4其他位置的1(红色);

3、C2其他位置的2以及C3其他位置的4(红色)。

 
图9-DAXZ04

​本例中ALS-A=R23C4 {467},ALS-B=R2C23,R3C23 {14678}, X=4,6(注意ALS-B中的6虽然出现了两次,但因为都位于R2,仍是有效的RCC)。根据规则可删去:

1、C4以及B2其他位置的7(红色);

2、B1其他位置的1、7、8以及C2其他位置的1(ALS-B中的1都位于C2,这两个1必有一个成立)(红色);

3、R2其他位置的6和R3其他位置的4(红色)。

三、ALS-XY-Wing

前文介绍的AlS-XZ是两个ALS-A、B籍由RCC X联结以实现删减的情况,可记为z-A-x-B-z,如果将中间的x替换为一个分别和A、B两组ALS都有RCC的ALS-C,ALS-XZ的删减规则依然可以适用,这种情形可记为z-A-x-C-y-B-z(ALS-C中与A、B分别联结的两个RCC不能相同,大家可以思考下,为什么会有这样的要求)。来看实例:

 
图10-AXY01

​图10盘势中,ALS-A=R7C156 {3678}(绿色),ALS-B=R579C8 {2389}(橙色),ALS-C=R9C34 {179}(紫色),X,Y=7,9, Z=3。ALS-C中的7与绿色A中的7是一组RCC,ALS=C中的9与橙色B中的9是另一组RCC,ALS-A、B中相同的候选数3和8,但只有3存在共同作用格,可删去R7C7的3(红色)。

 
图11-AXY02

图11盘势中ALS-A=R1C78 {247},ALS-B=R25C4 {679},ALS-C=R259C9 {3467}, X,Y=4,6, Z=7,可删去R1C4中的7(红色)。

四、ALS Chain

ALS Chian也可称为ALS-XY-Chain,是ALS-XY-Wing的扩展,如果存在多个可以利用RCC联结起来的ALS,且首尾两个ALS中存在相同的候选数,则这两个ALS中的相同候选数集可对其共同作用格内的候选数进行摈除。ALS Chain的删数逻辑从本质上来说依然是链,其工作原理是:利用ALS内候选数集的特性,构造出一个强弱相间且首尾两端为强关系的数链来实现对相关候选数的删减

来看实例:

 
图12-ACH01

图12盘势中,R1C4789的ALS{24569}与R8C4的ALS{56}通过RCC 5取得联结,ALS{56}与R58C3的ALS{256}通过RCC 6取得联结(双值格亦可看做ALS),ALS{256}与B1的ALS{23469}通过RCC 2取得联结,ALS{24569}与ALS{23469}中除去RCC 2外还存在共同候选数4、6、9,其中6、9数字集有共同作用格,可删去共同作用格内的候选数6、9(红色)。

本例亦可用链来解释,如图12中所示,红色实线箭头表示强链,虚线箭头表示弱链, ALS{24569}中的2、4、6、9数字集分别与5构成强关系;ALS {256}中的6与2的数字集构成强关系;ALS{23469}中的3、4、6、9数字集分别与2构成强关系,最终形成强弱交替的一条异数链,从而实现了对相应候选数的删减。

 
图13-ACH02

图13的盘势则是将利用双值格完成了ALS Chain的联结:R2的ALS{23567}(绿色框)通过RCC 7与R2C7的ALS{37}联结;R2C7的ALS{37}通过RCC 3与R7C7的ALS{37}联结;R7C7的ALS{37}通过RCC 7与B8的ALS{237}联结,ALS{23567}与ALS{237}中,除RCC 7外,还存在共同候选数2、3,其中3的数字集存在共同作用格,可删去相应位置的候选数3(红色)。



作者:零时四分_719b
链接:https://www.jianshu.com/p/6a9ca234f1aa
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
原文地址:https://www.cnblogs.com/asdyzh/p/10144987.html