欢迎光临散文网 会员登陆 & 注册

第 28 讲:双强链

2021-05-20 17:33 作者:SunnieShine  | 我要投稿

何为链,链是什么?链是一种动态、灵活的证明思路链条。

Part 1 摩天楼(Skyscraper)

如图所示,我们观察到一个特别的结构。首先是r39,r39上都有关于4的共轭对,分别是r3c48(4)和r9c47(4)。而奇怪的是,它长得很像之前学习到的一种数独技巧:孪生二链列,而且用这个技巧完全可以得到应有的所有删数。而现在我们用另外一个视角来看这个结构。r3c8(4)一共有两种可能:要么r3c8 = 4,要么r3c8 <> 4。那么我们来看一下,当r3c8 <> 4时,会怎么样呢?

当r3c8 <> 4时,由于r3(4)共轭对,所以r3c4 = 4,所以r9c4 <> 4了。于是,r9(4)共轭对就用起来了:因为r9c4 <> 4,所以r9c7 = 4。那么缩略一下说法,就是当r3c8 <> 4时,r9c7 = 4。

而r3c8 = 4是另外一种情况,这意味着r3c8自己可以直接填4。

所以综上,一共只有两种填数情况,却导致了r9c7和r3c8里面至少一个单元格是填4的,所以r9c7(4)和r3c8(4)共同对应的地方,就不应该填入4;否则它将使得这两个单元格都不能放4,出现违背结论的矛盾。

那么,为什么说“至少有一个单元格”,而不是“有且仅有一个单元格”呢?这一点,我们在Wing结构一节里面已经提到过一部分原因,这里针对这个题目再阐述一下:虽然看似r3c8拥有填4和不填4的两种填法是“互斥”的两种情况,但是“当r3c8 <> 4时,r9c7 = 4”成立,也并不意味着“当r3c8 = 4时,r9c7 <> 4”就一定成立。所以r3c8 = 4时,也是有可能使得r9c7 = 4的。所以我们说r9c7和r3c8至少有一格是填4的。

由于r3c8(4)和r9c7(4)至少一个单元格填4,所以不管怎么个情况,它们共同对应的地方,就不应该再含有候选数4,所以删除掉它们。对应图中的话,就应该为r1c7, r7c8 <> 4。

这个技巧称为摩天楼(Skyscraper),而摩天楼是属于双强链(Two-strong-link Chain)里面的一个特殊的结构。那么,什么是双强链呢?双强链,顾名思义,也就是有两个强关系的链。那,什么是强关系呢?接下来我们来介绍一下,关于标准链的基本术语及内容。

Part 2 基本链理论和术语

我们从刚才的示例之中,学习到了双强链的其中一个特殊结构:摩天楼。我们定义出几种说法,为了方便观察和理解:

  • (True),指的是某一个候选数直接填入到盘面之中的情况,即用等号=表示的情况;

  • (False),指的是某一个候选数从盘面之中消失的情况,即用不等号!=或<>表示的情况;

  • 强关系(也称强链关系,Strong Inference):如果某一候选数为假,则得到另外一个候选数为真的,就称这两个候选数有强关系;

  • 弱关系(也称弱链关系,Weak Inference):如果某一候选数为真,则得到另外一个候选数为假的,就称为两个候选数有弱关系;

  • 节点(Node):结构的每一个真假讨论的点都是一个节点;

  • 链头链首(Head),指的是链结构在推导过程之中的第一个节点;

  • 链末链尾(Bottom),指的是链结构在推导过程之中的最后一个节点;

  • 交集共同作用域(Intersection),指的是链头和链尾共同对应的地方(或者说,都可以看得到的地方)。

那么来总结一下刚才的推导方式:

分某一个候选数的真假两种填数情况进行讨论,当其为假时,引出一个真和假的交替推导序列,然后得到尾部为真的情况。而因为头部还有可能为真,所以头尾的两个候选数至少有一个为真,因此删除头尾两候选数的交集。

那么,这个“真和假的交替推导序列”就被称为标准链(简称,Alternating Inference Chain,简称AIC)。一般而言,只要我们画出标准链结构,就可以直接在图上体现逻辑,也就可以不需要给不知道逻辑的小伙伴讲解了。

Part 3 链的呈现方式

链可以用文本形式或图像形式呈现,下面来说明一下,如何使用文本形式表达。

我们使用候选数1==候选数2候选数1=候选数2的方式,表示两个候选数形成强关系,例如r3c4(4)==r3c8(4)或r3c4(4)=r3c8(4)都表示这两个数形成了强关系;而使用候选数1--候选数2或候选数1-候选数2的方式表示两个候选数形成弱关系,例如r3c4(4)--r9c4(4)或r3c4(4)-r9c4(4)都表示这两个数形成了弱关系;而图上的链写作

另外,如果候选数涉及相同数值,那么可以直接写单元格,而省去候选数数值,将它写在最后,比如前面的示例里的文本书写格式可以简化为

下面来说一下如何使用图像呈现链结构。一般来说,我们呈现链结构的时候,将使用箭头画法,来表示推导的顺序和方向。并用实线箭头表示强关系,虚线箭头表示弱关系。如图所示,这是前面示例的链画法。

Part 4 原理进一步剖析

4-1 链的头尾可以同真吗?

显然,这一点在刚才的题目文字里已经说明了。链头假设为假的时候,可以得到链尾为真;而链头还可能为真,所以删去交集。虽说两种假设是互斥的,但不代表结论就必须和假设一样互斥。结论的内容是通过假设得到的;但结论可能通过其它渠道得到,并不是仅通过唯一的方式来得到,而且我们在这个题目的解尚未得到之前,任何情况都是可能存在的,甚至我们可以找到两条链,得到同一个候选数既可以真又可以假。你可能会说,这不是不可能吗?这是可能的,原因在于我们是通过我们自己设定的假设前提才得到的结果,而假设和结论实际上并没有直接的关系。所以,链的头尾可以同真。

从数学的角度出发,高中你一定学过命题与逻辑一节,我们提到过,原命题和否命题的真值无直接关系(也就是说。原命题不管是真还是假,否命题都无法确定其真假性)。而我们可以注意到,候选数a假得到候选数b真和候选数a真得到候选数b假显然是互为否命题的,而它们并没有直接的真假性的关联,所以一个命题即使能够得到,也推不出另外一个命题。

我们来这一则示例里的摩天楼技巧,再对比题目的解来看,就可以发现,链的头尾确实是同真的。

可以看到,r5c6(2)和r9c4(2)在终盘下确实同真,而题目确实是唯一解的。

4-2 链的长度有什么结论吗?

在刚才介绍了相关术语之后,我们就可以把之前的逻辑用强弱关系重新解释一遍了。

设r3c8(4)为假,则r3c8(4)和r3c4(4)有强关系,r3c4(4)和r9c4(4)有弱关系,r9c4(4)和r9c7(4)有强关系。

因为逻辑的推导是“假 -> 真 -> 假 -> 真”这样,设开头为假,并且真假交替出现的,所以AIC具有两个基本特性:

  • 链必须以强关系开头、强关系结尾;

  • 链强弱关系是交替出现的。

那么,还有一个由这两点可以得到的推论。必须强关系开头、强关系结尾,并且强弱关系交替出现,那么结构只可能是“强弱强”、“强弱强弱强”等等了,那么强关系数量始终会比弱关系数量多一个。那么强关系设有n个的话,弱关系就得有(n-1)个,那么组合形成的AIC就有(2n-1)个。因为n是正整数,所以(2n-1)就应该是一个单数(正的奇数)。所以,AIC的长度(Length),即AIC涉及的强弱关系的总数,就一定是一个单数。而节点数量一定比长度大1,所以节点数应该为2n个,则为一个双数(正的偶数)。

那么,双强链,顾名思义,这种结构必须只能有两个强关系;而它具有两个强关系和一个弱关系,所以双强链的长度一定为3。

4-3  “强-强-强”也是链?

再来看一则问题。比如示例上的c4(4)。因为c4(4)也是共轭对,所以它肯定可以满足强关系的定义:当r3c4 <> 4时,r9c4 = 4。那为什么r3c9(4)和r9c4(4)就必须得是弱关系?

因为我们在使用链的过程之中,强弱关系是交替出现的。换句话说,真假情况是交替出现的,而当AIC的开头r3c8(4)假设为假后,推理到r3c4(4)时,就已经是真了,所以r3c4(4)和r9c4(4)使用的是弱关系的定义。虽然,这里确实也满足强关系这一说法。

也就是说,网上给出的一部分资料,写的是“‘强强强’的标准链结构亦成立”,这种说法是错误的,它犯了本质性的错误。希望你务必引起注意和重视。

在阐述了基本表达方式后,接下来我们继续介绍双强链结构。

Part 5 双线风筝(Two-string Kite)

如图所示,如果r1c9(8)为假,则r1c5(8)真,r3c4(8)假,r7r4(8)真。但是,r1c9(8)还可以为真。所以两种情况之下,r1c9(8)和r7c4(8)至少一个为真。故删除两个候选数共同对应的位置,即r7c9(8)。

链文本表示如下:

这个结构称为双线风筝(Two-string Kite)。

Part 6 普通双强链

如图所示,假设r1c3(7)假,可以得到r5c9(7)为真,所以r1c3(7)和r5c9(7)至少一个为真,故删除交集。

这个结构称为普通的双强链。

根据技巧的发现者描述,双强链一共分为摩天楼、双线风筝和普通的双强链三种,而由于双线风筝和摩天楼的形状较为特殊,技巧发现者优先发现这两种结构,并随即为其取名。后续的不属于双线风筝和摩天楼的则没有自己单独的名称。

摩天楼的两个强关系是产生于同两行或两列的,而双线风筝的两个强关系则产生于某行和某列。如果不满足上述两个要求的,就是普通的双强链。换句话说,摩天楼的强关系是“平行”的,而双线风筝的强关系则是“垂直”的,而强关系既不平行也不垂直,只能算是普通的双强链结构。

Part 7 共轭对和强关系的异同

那么,双强链的基本构型我们就学到这里。之所以阐述双强链,是因为有两大好处:一来是为了让你更清晰地掌握链这个数独技巧,从较短的链开始学习;二来,这种结构由于简单,所以非常好观察,只需要我们经常去关注共轭对就好。不过,根据之前的理论,我们发现,共轭对就产生于同一个区域下只有两个位置可填的情况,而定义恰好也满足强关系的。

实际上,强关系的定义比共轭对更宽泛一些,共轭对指的是同区域下只有两个位置可填的相同数字,或是同一双值格下的两个候选数。但跨区域下的不同数字,共轭对并不包括在内,而强关系在之后,我会告诉大家如何去寻找和使用这样的特别情况。所以你只需要记住一点,因为目前的强关系的定义可以完全用共轭对实现,所以我们就用共轭对来寻找吧!共轭对找起来会很快的哦!

第 28 讲:双强链的评论 (共 条)

分享到微博请遵守国家法律