[数独高级技巧入门]链的逻辑及AIC

7

转载自独数之道
作者：叶卡琳娜

这个帖子主要想阐述链是什么，怎么使用链，以及链的逻辑过程，帮助大家首先了解原理，那么以后关于chain、wing之类的按照这个思路都非常容易理解。
首先我想说明下什么是“强”关系，什么是“弱”关系？
强关系是说A与B两个事件，假如A不成立，则B一定成立。
弱关系是说A与B两个事件，假如A成立，则B一定不成立。
举一个简单的例子帮助大家体会：


（图中被划短横线的格表示不含候选数1）
这是一个数独的宫，根据数独规则一个宫内出现数字1-9各一次，可以做出以下两点推断：
1.左上格不是1，则右中格一定是1；
2.左上格是1，则右中格一定不是1。
第一种推断得到这两格的1是强关系，所以可以说两格之间形成一条强链，强链我们通常以双横线表示（==）；
第二种推断得到这两格的1是弱关系，所以可以说两格之间形成一条弱链，弱链我们通常以单横线表示（——）。

再举一个例子：


（图中被划短横线的格表示不含候选数1）
上图可以做出三大点推断：
1.左上格是1，则中上格及右中格一定不是1；
2.中上格是1，则左上格及右中格一定不是1；
3.右中格是1，则左上格及中上格一定不是1。
这个例子里，存在着3条弱链，分别是（左上--中上）、（左上--右中）、（中上--右中）。

7

上面说的是同一数字的强弱关系，当然强弱关系可以不局限于一个数字，下面用例子来说明：

（图中被短横线划掉的格说明未知其候选数情况）
根据右上格的候选数仅有1与2可以做出以下推断：
1.如果该格不能是1，则一定为2；
2.如果该格是1，则一定不是2。
推断一说明数字1与2之间是强关系，形成强链；推断二说明其为弱关系，形成弱链。


（图中被短横线划掉的格说明未知其候选数情况）
右上格有3个候选数，我们可以做出以下推断：
1.如果这格为1，则不能为2或3；
2.如果这格为2，则不能为1或3；
3.如果这格为3，则不能为1或2。
数字1与2、2与3、1与3之间分别为一条弱链。

像第二张图这样的关系推断，大家可能会不以为意，但是这是理解强弱关系的一个很好的例子，对于后面将要叙述的内容也会有所帮助。

相信通过上面的说明大家已经了解了强弱链是什么，接下来我们将强弱链连接起来。
第一种情况：A==B--C==D
由A的真假情况可以做出以下BCD关系的枚举。
再次请大家注意本文开头所提到的强弱关系本质
1.强关系是说A与B两个事件，假如A不成立，则B一定成立。
2.弱关系是说A与B两个事件，假如A成立，则B一定不成立。



（图中红色部分表示根据上一个的真假情况必然是这样的推导）
可见A与D不全为假，即A与D一定有一个为真。
当A与D有等位群格位的交集时，即可做出相应删减。

7

（图示技巧名为Skyscraper）
根据强弱关系，我们找到了一条符合A==B--C==D的强弱链组：r3c1(2)==r3c7(2)--r9c7(2)==r9c2(2)。
根据上文提到的逻辑关系，可以得到r3c1=2与r9c2=2至少有一个成立，所以可以删去它们等位群格位的交集（即橙色区域）的候选数2。



•根据叶卡林娜前面对于强链的叙述，以下是一个双强链的实例，也是大家耳熟能详的 X-Wing。


1. 上左图，数字 4 在 C4,C8 形成 X-Wing。
2. 上右图，R2,R4 除了形成 X-Wing 的四格之外，其它格位不能存在数字 4，因此画 X 处就是可以删减候选数 4 的格位。


● X-Wing用之前提到的强弱强链观察可以找到2组，以上图为例：
　r2c4==r4c4--r4c8==r2c8，得到r2c4与r2c8的4至少有一个成立，所以可以删除R2其他格的候选数4；
　r4c4==r2c4--r2c8==r4c8，得到r4c4与r4c8的4至少有一个成立，所以可以删除R4其他格的候选数4。

7

•有时运用不同的强弱强链，能达到相同的删减效果，下面就是一个例子：





•左侧使用的是r5c1==r5c9--r3c9==r1c7的强弱强链；

•右侧使用的是r3c2==r3c9--r5c9==r5c1的强弱强链。

•两种观察方法均可以删除r1c1的候选数1。



•上面的几个例子都是关于单一数的强弱强链的，在数独的解题技巧里我们将这类成为X-Chain。

•关于单一数链应用我们放在 双强链解法的运用 这个主题中继续讨论。

•当把链的条数增加的时候，也就是A==B--C==D--E==F时，也能够推导出A与F至少有一个为真，这边就不做枚举了，大家可以自行推导下。

•下面来看一些牵扯到异数的强弱强链的例子。

7

要说异数强弱强的关系肯定要提到XY-Wing了，下面是一个XY-Wing的例子：



（图中三格的候选数由点算即得）

通常解释XY-Wing原理的时候会用如果r4c2=1则r5c1=4；如果r4c2=9则r4c8=4，所以不论r4c2是1还是9，r5c1与r4c8中至少有一个是4，
从而得到r5c1与r4c8的等位群格位交集部分（图中蓝色格）不含4。

这样是不是有点猜测的味道呢？很多人都说高级技巧是把猜的东西合理化，其实不然。

用强弱强链的观点可以这样看r5c1(4)==r5c1(1)--r4c2(1)==r4c2(9)--r4c8(9)==r4c8(4)，
也是得到r5c1与r4c8中至少有一个是4，这样的观察是不是更逻辑化呢？欢迎大家提出你的看法。



与XY-Wing较相近的要数XY-Chain。



XY-Wing由三格组成，分别为xy格，xz格，yz格。XY-Chain不止三格，需要把一些格合并当作XY-Wing组成格之一来看。（这些我们会在相应主题再讨论）

下面来看一个例子：

这里就不用如果怎么则怎么来解释了，毕竟通过上面一些介绍，大家可以用强弱强这样的逻辑关系解释，不需要用如果怎么样的解释。
以XY-Wing的观点来看的话可以将r4c2作xy格，r4c9作xz格，{r5c1, r5c2}作为yz格。
以强弱链的观点来看略复杂，因为由4条强链组成，请大家以r4c9为起点依次观察交替的强链(红色)、弱链(绿色)。
可以得到两端点r5c1(1)、r4c9(1)至少有一个成立，所以可删除两者交集r5c89的候选数1。

7

有的时候我们可以把两格看作一组，例如在 双强链解法运用 中的第六题：



r4c1(7)==r5c4(7)--r5c2(7)=={r1c2, r2c2}(7)
得到{r1c2, r2c2}与r4c1至少有一个为7。
所以可以删除{r1c2, r2c2}与r4c1等位群格位的交集r1c3的候选数7。
-------------------------------------------------------------------------------------

XY-Chian的首尾若能连接起来就成为了XY-Cycle（Multi X-Wing）




上图中断开任意一条弱链（绿色表示）即成为XY-Chain的结构。

例如断开上端r8c57的弱链后，可以得到r8c5(7)与r8c7(7)至少有一个成立，即可删除这两格等位群格位交集的7（这里交集是R8除这两格外的格）。

其他三种断开弱链能够做何删减，大家可以自己尝试推导。


前面是例举了强弱强的关系，那么弱强弱的关系又能得到什么结论呢？
第二种情况：A--B==C--D
由A的真假情况可以做出以下BCD关系的枚举。

（图中红色部分表示根据上一个的真假情况必然是这样的推导）
可见A与D不全为真，即A与D一定有一个为假。

这样的关系有什么相应应用呢？欢迎大家提出你的看法。

7

既然强弱强看起来这么厉害，那么强强强会如何呢？
A==B==C==D
由A的真假情况可以做出以下BCD关系的枚举。

（图中红色部分表示根据上一个的真假情况必然是这样的推导）
可以发现，AD一真一假，全为真，全为假都可能，所以虽然是强强强，也达不到任何效果，比弱强弱还不如。
这难道就是所谓的物极必反么？


那么既然强强强都没用，再加一个强，变成强强强强是不是会有点用处呢？
以前看过独数文章的朋友可能还记得有一个叫Guardians（守护者）的技巧，也有地方称之为Broken Wings或者Turbot-Fish。
其描述的是某一个候选数X的情况，当有偶数条强链，且两个端点处于同一unit时，这时可以删除两个端点上的候选数X，
如果该unit出这两端点格外只有一格含有候选数X，则该格一定就是X。


可以删除r2c3与r4c3的候选数5，守护者r9c3=5。

大家可以解释其中的原理么？

7

TTHsieh  对原理的解答：

单数链以强、弱方式构成环，称为 X-Cycle，无法构成环，则称为 X-Chain。
X-Cycle 的弱环节除节点外，单元内其它格位的相同候选数均可删除。
X-Chain 在开口处之两节点共同作用格的相同候选数均可删除。
________________________________________________________________________
本质上 X-Cycle 只是 X-Chain 的特例，因此统称为单链。
单链若由两条强链与一条弱链构成，就是习称的双强链，有摩天楼、双线风筝、鱼三种连结方式。
单链若由两条强链与两条弱链构成环，就是习称的 X-Wing。


________________________________________________________________________


上面三图中，从蓝色格出发到达红色格，根据它们之间的逻辑关系，可以得到红色格有相同的真假值。


上面二图中，从一个红色格出发到达另一红色格，根据它们之间的逻辑关系，亦可得到另一红色格有相同的真假值。

红色格若为假，没问题两个都可删除，红色格若为真，则违反数独原则也应当删除。
结论：红色格应予删除。


以分色法(Coloring)的推导方式是：若在某一单元出现相同的颜色，则色链中与该颜色相同的格位均应删除。

图1

图2

图3

上图1 删除白色, 上图2 删除蓝色, 上图2 删除白色


图4

图5

上图4 删除蓝色, 上图5 删除蓝色
从每一格位出发所得到的结论均相同。

7

在本帖7楼提到了守护者的结构，这看起来似乎与在7楼的另一个观点相矛盾。
但是事实并非如此，请注意观察守护者的例子，因为这里所有的强链都是在同一unit的强链，因此，根据数独规则，当然也符合弱链的定义，同一unit有两个相同数不是矛盾了么？
因此在17楼中的推理如果是基于A==B==C==D且A--B--C--D，即所有链既是强链也是弱链时，八种情况中的六种即可删除。


即只剩下 真假真假 与 假真假真 两种情况。

因此，事实上守护者是同时符合A==B==C==D==E与A--B--C--D--E的结构。
按照A的真假性可以做出如下推导：
1. A真 -> B假 -> C真 -> D假 -> E真
2. A假 -> B真 -> C假 -> D真 -> E假
可见A与E真假性相同。
当A与E处于同一个unit时（此为守护者的结构描述，见本帖第15楼），不能同时为真，所以只能全为假。
因此，也就产生了A与E所在unit其他格中的X是守护者一说。
大家也可参考8楼提出的说明。


再来看另一种涉及双数关系的技巧Y-Wing的逻辑关系：


用链的观点来看：r3c8(9)==r3c8(2)--r6c8(2)==r6c6(2)--r9c6(2)==r9c6(9)，因此可以删除r9c8的候选数9。

亦可这样理解，如果r3c8不为9，r3c8为2，则r6c8不为2，r6c6为2，r9c6不为2，即r9c6为9；

反过来，如果r9c6不为9，则r9c6为2，r6c6不为2，r6c8为2，r3c8不为2，即r3c8为9；

可见r3c8与r9c6至少有一个为9，因此可以删除r9c8的候选数9。

8773

额，先收下了，慢慢消化，不过，这应该是经验得来的吧，好好学学