链的逻辑(Chain)
链是数独高级技巧的核心,所有数独盘势都可以通过各种或简单或复杂的链来解出答案。
链的本质是命题之间的关系,在解数独时,每个填数的步骤都可以表现为“A 格中填入 1”、“B 格中填入 2”这样非真既假的直言命题形式,如果条件不充足,命题真假不能判定。我们把数独中这种命题之间的真假关系称为 链。
用链解题的逻辑在于,藉由命题真假值的推导,根据链两端点命题的真假来判断其共同作用格内候选数的真假。
强关系和弱关系
链可以分为 强链(Strong Links)与 弱链(Weak Links),分别由强关系和弱关系构成:
- 强关系是说 A 与 B 两个事件,假设 A 不成立,则 B 一定成立(不可同假,必有一真)。
- 弱关系是说 A 与 B 两个事件,假设 A 成立,则 B 一定不成立(不可同真,必有一假)。
举个简单的例子:
| 1 | — | — |
| — | — | 1 |
| — | — | — |
这是一个数独的宫(短横线表示不含候选数 1),根据数独规则,一个宫内出现数字 1-9 各一次,可以做出以下两点推断:
- 左上格不是 1,则右中格一定是 1;
- 左上格是 1,则右中格一定不是 1。
第一种推断得到这两格的 1 是强关系,可以说这两格之间形成一条强链,用双横线(==)表示。
第二种推断得到这两格的 1 是弱关系,可以说这两格之间形成一条弱链,用单横线(--)表示。
再举一个例子:
| 1 | 1 | — |
| — | — | 1 |
| — | — | — |
上面一宫可以做出三点判断:
- 左上格是 1,则中上格和右中格一定不是 1;
- 中上格是 1,则左上格和右中格一定不是 1;
- 右中格是 1,则左上格和中上格一定不是 1。
这个例子里,存在着 3 条弱链,分别是:左上 -- 中上、左上 -- 右中、中上 -- 右中。
上面说得是同一数字的强弱关系,当然强弱关系可以不局限于一个数字,下面用例子来说明:
| 12 | — | — |
| — | — | — |
| — | — | — |
根据左上格的候选数仅有 1 和 2 可以做出以下推断:
- 如果该格不是 1,则一定是 2;
- 如果该格是 1,则一定不是 2;
推断一说明数字 1 与 2 之间是强关系,形成强链;推断二说明 1 与 2 之间是弱关系,形成弱链。
| 123 | — | — |
| — | — | — |
| — | — | — |
左上格有 3 个候选数,我们可以做出以下推断:
- 如果这格位 1,则不能为 2 或 3;
- 如果这格为 2,则不能为 1 或 3;
- 如果这格为 3,则不能为 1 或 2;
数字 1 与 2,2 与 3,1 与 3 之间分别为一条弱链。像这样的关系推断,是理解强弱关系的一个很好的例子,对于后面将要叙述的内容也会有所帮助。
链是如何工作的
通过上面的说明,你已经了解了强弱链是什么。接下来我们将强弱链连接起来,看看会发生什么。
第一种情况:A == B -- C == D(强弱强)
由 A 的真假情况可以做出以下 BCD 关系的枚举(红色部分表示根据上一个的真假情况必然是这样的推导)。
请再次注意本文开头所提到的强弱关系本质:
- 强关系是说 A 与 B 两个事件,假设 A 不成立,则 B 一定成立(不可同假,必有一真)。
- 弱关系是说 A 与 B 两个事件,假设 A 成立,则 B 一定不成立(不可同真,必有一假)。
| A | B | C | D |
| 真 | 真 | 假 | 真 |
| 真 | 假 | 真 | 真 |
| 真 | 假 | 真 | 假 |
| 真 | 假 | 假 | 真 |
| 假 | 真 | 假 | 真 |
可见 A 与 D 不全为假,即 A 与 D 一定有一个为真,也就是 A == D,二者为强关系。当 A 与 D 有等位群格位的交集时,即可做出相应删减。
第二种情况:A -- B == C -- D(弱强弱)
由 A 的真假情况可以做出以下 BCD 关系的枚举。
| A | B | C | D |
| 真 | 假 | 真 | 假 |
| 假 | 假 | 真 | 假 |
| 假 | 真 | 真 | 假 |
| 假 | 真 | 假 | 真 |
| 假 | 真 | 假 | 假 |
可见 A 与 D 不全为真,即 A 与 D 一定有一个为假,也就是 A -- D,二者为弱关系。这种情况下不能直接用来删减 AD 共同作用格的候选数。
第三种情况:A == B == C == D(强强强)
由 A 的情况可以做出以下 BCD 的枚举。
| A | B | C | D |
| 真 | 真 | 真 | 真 |
| 真 | 真 | 真 | 假 |
| 真 | 真 | 假 | 真 |
| 真 | 假 | 真 | 真 |
| 真 | 假 | 真 | 假 |
| 假 | 真 | 真 | 真 |
| 假 | 真 | 真 | 假 |
| 假 | 真 | 假 | 真 |
可以发现,AD 一真一假、全为真、全为假,都有可能。所以虽然是强强强,也达不到任何效果。
注意
基于强强强的关系并不能得到任何结论。所以在某些数中提到的“强弱强和强强强都可以得到端点是强关系”这句话是完全错误的,并且给人以是强关系就一定是弱关系的错觉。强和弱这两个关系并无谁包含谁,而是独立的、不同的逻辑。
在实际解题过程中,如果 B 和 C 是限定在同数、同单元或同格,我们需要撇开 B 和 C 是强关系的逻辑,而使用 B 和 C 是弱关系的逻辑,即些链时应该用 A == B -- C == D,来得到 A == D 的结论。
故当 A 和 B 同时符合强关系和弱关系时,我们需要根据实际情况来决定使用哪一种。
由以上推导我们可以总结,在数独解题过程中,链的工作模式是:找到数独盘势中的强链,用弱链将之连接,在此过程中保证强弱交替,以强链始以强链终,则链的两端互为强关系,必有一真,若其存在共同作用格,则可对共同作用格内的相应候选数进行删减。
链的简单应用
下面来看一个例子:
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | 9 | 7 | 4 | 1 | 6 | 8 | |||
| R2 | 7 | 8 | 4 | 2 | 6 | 5 | 9 | 3 | 1 |
| R3 | 1 | 6 | 9 | 3 | 8 | 7 | 4 | ||
| R4 | 1 | 7 | 5 | 8 | 9 | 2 | 4 | 6 | 3 |
| R5 | 8 | 3 | 6 | 5 | 1 | ||||
| R6 | 6 | 2 | 3 | 1 | 8 | ||||
| R7 | 5 | 8 | 1 | 2 | 6 | 4 | |||
| R8 | 6 | 1 | 4 | 7 | 3 | 8 | |||
| R9 | 4 | 7 | 5 | 8 | 9 | 1 | 6 |
根据强弱关系,我们找到了一条符合 A == B -- C == D 的强弱链组:
R3C1(2) == R3C7(2) -- R9C7(2) == R9C2(2)
根据上文提到的逻辑关系,可以得到 R3C1 = 2 与 R9C2 = 2 至少有一个成立,所以可以删去它们等位群格位的交集(★ 格)的候选数 2。
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | ★ | 9 | 7 | 4 | 1 | 6 | 8 | ||
| R2 | 7 | 8 | 4 | 2 | 6 | 5 | 9 | 3 | 1 |
| R3 | 2 | 1 | 6 | 9 | 3 | 8 | 2 | 7 | 4 |
| R4 | 1 | 7 | 5 | 8 | 9 | 2 | 4 | 6 | 3 |
| R5 | 8 | 3 | 6 | 5 | 1 | ||||
| R6 | 6 | 2 | 3 | 1 | 8 | ||||
| R7 | ★ | 5 | 8 | 1 | 2 | 6 | 4 | ||
| R8 | ★ | 6 | 1 | 4 | 7 | 3 | 8 | ||
| R9 | 4 | 2 | 7 | 5 | 8 | 9 | 2 | 1 | 6 |
我们可以从强弱关系的逻辑把上述这条链走一遍,共有以下两种情况:
- R3C1 = 2
- R3C1 ≠ 2,则 R3C7 = 2(强关系),R9C7 ≠ 2(弱关系),R9C2 = 2(强关系)
也就是 R3C1 和 R9C2 至少有一个是 2(强关系)。如果 R3C7 和 R9C7 之间用强关系的逻辑看的话,从 R3C7 = 2 是无法得到 R9C7 ≠ 2 的,这条推理也就到此为止,无法进行下去。
注意
很多人认为强关系包括了弱关系。因为“非 A 即 B”的逻辑是不包含“是 A 非 B”的逻辑的,所以这当然是错误的观点。强弱关系是两种不同的逻辑,且是相互独立的。
有时运用不同的强弱强链,能达到相同的删减效果,下面就是一个例子:
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | 5 | 9 | 7 | 6 | 4 | ||||
| R2 | 4 | 7 | 8 | 1 | 6 | 9 | 5 | ||
| R3 | 6 | 3 | 5 | 9 | 4 | 8 | 7 | ||
| R4 | 5 | 8 | 9 | 4 | 6 | ||||
| R5 | 8 | 6 | 4 | 5 | 9 | 3 | |||
| R6 | 9 | 4 | 6 | 7 | 5 | 8 | |||
| R7 | 5 | 6 | 1 | 3 | 4 | 2 | 9 | ||
| R8 | 3 | 4 | 2 | 9 | 6 | 1 | 5 | 8 | 7 |
| R9 | 8 | 9 | 7 | 2 | 4 | 5 | 6 | 1 | 3 |
方法 1:使用 R5C1 == R5C9 -- R3C9 == R1C7 的强弱强链。
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | ★ | 5 | 9 | 7 | 1 | 6 | 4 | ||
| R2 | 4 | 7 | 8 | 1 | 6 | 9 | 5 | ||
| R3 | 6 | 3 | 5 | 9 | 4 | 8 | 7 | 1 | |
| R4 | 5 | 8 | 9 | 4 | 6 | ||||
| R5 | 1 | 8 | 6 | 4 | 5 | 9 | 3 | 1 | |
| R6 | 9 | 4 | 6 | 7 | 5 | 8 | |||
| R7 | 5 | 6 | 1 | 3 | 4 | 2 | 9 | ||
| R8 | 3 | 4 | 2 | 9 | 6 | 1 | 5 | 8 | 7 |
| R9 | 8 | 9 | 7 | 2 | 4 | 5 | 6 | 1 | 3 |
方法 2:使用 R3C2 == R3C9 -- R5C9 == R5C1 的强弱强链。
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | ★ | 5 | 9 | 7 | 6 | 4 | |||
| R2 | 4 | 7 | 8 | 1 | 6 | 9 | 5 | ||
| R3 | 6 | 1 | 3 | 5 | 9 | 4 | 8 | 7 | 1 |
| R4 | 5 | 8 | 9 | 4 | 6 | ||||
| R5 | 1 | 8 | 6 | 4 | 5 | 9 | 3 | 1 | |
| R6 | 9 | 4 | 6 | 7 | 5 | 8 | |||
| R7 | 5 | 6 | 1 | 3 | 4 | 2 | 9 | ||
| R8 | 3 | 4 | 2 | 9 | 6 | 1 | 5 | 8 | 7 |
| R9 | 8 | 9 | 7 | 2 | 4 | 5 | 6 | 1 | 3 |
以上两种观察方法都可以删除 R1C1 的候选数 1。
上面的几个例子都是关于单一数的强弱强链,在数独的解题技巧里,我们将这类称为 X-Chain。当把链的条数增加的时候,也就是 A == B -- C == D -- E == F 时,也能推导出 A 与 F 至少有一个为真,这里就不做枚举了。下面来看一下牵扯到异数的强弱强的例子。
要说异数强弱强的关系肯定要提到 XY-Wing 了,下面是一个 XY-Wing 的例子(紫色三格中的候选数由点算即得):
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | 8 | 5 | 4 | 3 | 7 | 6 | 9 | 1 | 2 |
| R2 | 2 | 4 | 5 | 9 | 8 | ||||
| R3 | 6 | 9 | 2 | 1 | 8 | 5 | |||
| R4 | 2 | 1=9 | 7 | 6 | 5 | 3 | 9=4 | ||
| R5 | 1=4 | 8 | 6 | 9 | 3 | 2 | ★ | 5 | ★ |
| R6 | 5 | 7 | 1 | 2 | |||||
| R7 | 9 | 2 | 8 | 5 | 6 | 3 | 7 | ||
| R8 | 5 | 7 | 1 | 8 | 9 | 4 | 6 | 2 | 3 |
| R9 | 6 | 4 | 3 | 1 | 2 | 7 | 5 | 8 | 9 |
如果 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(4) == R4C8(4),这样观察起来才会更加逻辑化。
与 XY-Wing 较相近的要数 XY-Chain。
XY-Wing 由三格组成,分别为 xy 格、xz 格、yz 格。XY-Chain 不止三格,需要把一些格合并当做 XY-Wing 组成格之一来看。下面来看一个例子:
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | 4 | 1 | 5 | 2 | 6 | 3 | 7 | ||
| R2 | 2 | 3 | 8 | 1 | 9 | 7 | 6 | 4 | 5 |
| R3 | 6 | 9 | 7 | 8 | 4 | 5 | 1 | 3 | 2 |
| R4 | 3 | 6=8 | 4 | 7 | 9 | 5 | 8=1 | ||
| R5 | 1=7 | 7=6 | 5 | 3 | 8 | 4 | ★ | ★ | |
| R6 | 6 | 4 | 3 | 7 | |||||
| R7 | 9 | 2 | 3 | 4 | 7 | 1 | 8 | 5 | 6 |
| R8 | 8 | 4 | 1 | 9 | 5 | 6 | 2 | 7 | 3 |
| R9 | 6 | 3 | 8 | 2 | 9 | 1 | 4 |
以 XY-Wing 的观点来看的话,可以将 R4C2 作 xy 格,R4C9 作 xz 格,{R5C1, R5C2} 作为 yz 格。
以强弱强的观点来看略复杂,因为有 4 条强链组成,以 R5C1 为起点依次观察交替的强链和弱链,可以得出以下结论:
R5C1(1) == R5C1(7) -- R5C2(7) == R5C2(6) -- R4C2(6) == R4C2(8) -- R4C9(8) == R4C9(1)
可以得到两端点 R5C1(1) 与 R4C9(1) 至少有一个成立,可以删除两者交集(★ 格)的候选数 1。
有的时候我们可以把两格看作一组,如下例子:
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | 8 | 7 | ★ | 7 | 1 | 6 | 4 | 3 | |
| R2 | 3 | 7 | 4 | 8 | 5 | 1 | 9 | ||
| R3 | 9 | 1 | 6 | 3 | 4 | 5 | 2 | 7 | 8 |
| R4 | 2 | 8 | 4 | 3 | 5 | 1 | |||
| R5 | 5 | 7 | 1 | 7 | 8 | 3 | 4 | 2 | 6 |
| R6 | 4 | 6 | 3 | 1 | 5 | 2 | 8 | 9 | 7 |
| R7 | 1 | 3 | 6 | 7 | 4 | 9 | 8 | ||
| R8 | 7 | 8 | 2 | 3 | 9 | 1 | 6 | ||
| R9 | 6 | 5 | 1 | 8 | 7 | 3 |
R1C4(7) == R5C4(7) -- R5C2(7) == {R1C2, R2C2}(7)
得到 {R1C2, R2C2} 与 R1C4 至少有一个为 7,所以可以删除它们等位群格位的交集 R1C3 的候选数 7。
XY-Chain 的首尾若能连接起来就成为了 XY-Cycle。
| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | |
| R1 | 9 | 8 | 7 | 5 | 6 | 1 | 2 | 4 | 3 |
| R2 | 2 | 1 | 3 | 5 | 6 | ||||
| R3 | 6 | 5 | 4 | 3 | 1 | ||||
| R4 | 5 | 9 | 8 | 6 | 2 | 7 | 3 | 1 | 4 |
| R5 | 1 | 7 | 6 | 4 | 5 | 3 | 8 | 2 | 9 |
| R6 | 4 | 3 | 2 | 9 | 1 | 8 | 6 | 5 | 7 |
| R7 | 3 | 6 | 4 | 2 | |||||
| R8 | 8 | 9 | 4=7 | 6 | 7=1 | 3 | 5 | ||
| R9 | 7 | 3 | 4=9 | 9=1 | 6 | 8 |
R8C5(4) == R8C5(7) -- R8C7(7) == R8C7(1) -- R9C7(1) == R9C7(9) -- R9C5(9) == R9C5(4) -- R8C5(4) == R8C5(7)
断开任意一条弱链即成为 XY-Chain 的解构。例如断开上端 R8C5 -- R8C7 的弱链后,可以得到 R8C5(7) 与 R8C7(7) 至少有一个成立,即可删除这两格等位群格位交集的 7(即 R8 除这两格外的格)。其它三种断开弱链能够作何删减,可以自己尝试推导。
总结
通过上面对链的阐述和具体例子的讲解,我们可以做出以下几条总结:
很多人用真或假来找链,例如“某格不是某个数则……”。这并不是链的观察方法,而且这也会导致很多人觉得链就是试数,只是一种比较高级的假设罢了。观察链的关键不是在找起点,而是 找强链,然后用弱链把它们连接起来,找两端的共同作用格。是否有共同作用格决定了起点和终点的位置。比如先找到了一条强链 A == B,又找到另一条强链 C == D,其中 B 和 C 这两点恰好符合弱关系的定义,则可以得到 A == D,一旦它们有共同作用格,即可进行删减,假如没有共同作用格,那再找一条 E == F,尝试与端点 A 或者 D 连接,以此类推。
“非 A 即 B”不包含“是 A 非 B”,两者有交集(此时按需要使用哪一种逻辑),但是没有包含关系。原命题跟否命题的真假关系不一定。一般在观察的时候,都是最基本的,基于数独规则的:每格智能含一个数,每个数在每个单元(行、列、宫)只能出现一次。所以处于同格的两格数以及处于同单元的相同数符合弱关系的“是 A 非 B”,当一个单元仅有两个空格可以是某个数字时符合强关系的“非 A 即 B”。
单数链以强弱方式构成环,称为 X-Cycle;无法构成环,称为 X-Chain。X-Cycle 的弱环节除节点外,单元内其他格位的相同候选数均可删除。X-Chain 在开口处之两节点共同作用格的相同候选数均可删除。本质上 X-Cycle 只是 X-Chain 的特例,因此统称为单链。单链若由两条强链与一条弱链构成,就是习称的双强链,有摩天楼、双线风筝、鱼三种连接方式。单链若由两条强链与两条弱链构成环,就是习称的 X-Wing。
