链 - 数独吧

level 7

jcvb 楼主

链
1.链是什么？
链是数独高级技巧的核心，它表示两个命题间的关系。
命题有真假之分，我们可以通过分析链来判断某个命题是真还是假。
在数独中，我们要判断真假的命题都是：“某某格子应该填入某某数。”“A1=3”，“E7=8”，……诸如此类。分析出了它们的真假，我们就相当于是填出了一个数字。本文中约定把这些命题表示为“格子（数）”，例如A1(3)，E7(8)，等等。
链分强链关系、弱链关系两种：
强链：两个命题不可以同时为假，本文中用==（双横线）表示；
弱链：两个命题不可以同时为真，本文中用--（单横线）表示。
讲了这么多，我们来先找几条链试试吧。
例1：

1. H2(4)—H4(4)
如果H2和H4都填4，会有什么结果？结果是一行里出现了重复数字，违反了数独规则。于是我们可以判断H2(4)和H4(4)不能同时为真，即它们呈弱链关系。
2. D1(4)==I1(4)
我们仔细观察，会发现第1列除了D1和I1，其他格子都不可能填入4了。那么无论如何，它们两格中至少有一个4，即不能同假，呈强链关系。
3. G2(1)==G2(6)
刚才的两条链都是不同格子间的同一个候选数，这条却是同一个格子中不同的两个候选数。我们可以把上面两条叫做单链，这条和第4条叫做多链。G2要么填入1要么填入6，不可能是其他的数字了。所以它们俩不能同假（要不然G2就没数填了），呈强链。
其实，第2、3两条链也可以看成是弱链，因为他们即符合强链的定义，又符合弱链的定义（不能同真）。
4.G6(1)—G6(8)
一个格子内只能填一个数，而如果1和8都成立那么G6就有2个数了。所以它们不能同时成立，呈弱链。
上面这些都是链的4种基本情况，理解它们后我们就可以往下看第2节了。
2.链的基本应用
链之所以被称作链，是因为它们能够像链条一样串起来用：

例2：

这是一条长度为3的2的单链。乍看一下它只是3条单链连在一起罢了，难道它还有什么别的性质吗？当然。
由E3(2)==H3(2)—H4(2)==D4(2)我们可以推理出E3(2)==D4(2)，即它们不同假。
（初学者可以跳过证明部分不看，只需记住最后得出的两条定理）
证明：假如E3!=2且D4!=2（即同假，不满足强链），那么我们可以根据两条强链推断出G3=2且G4=2，而G3(2)—G4(2)，矛盾！所以E3(2)==D4(2)。
一般地，如果A==B—C==D，则A==D。
用类似的办法，我们还可以由E3(2)—H3(2)==H4(2) —D4(2)推出E3(2)—D4(2)。

一般地，如果A—B==C—D，则A—D。
这两条定理好像是把长链条拆开再换条短的上去，证出它们对我们有什么帮助呢？

我们来观察一下例2中的E6(2)，显然有
E6(2)—D4(2)和E6(2)—E3(2)。
由于我们已经得出了E3(2)==D4(2)，那么我们可以进一步得到
E6(2) —E3(2)==D4(2)—E6(2)。
我们根据定理2再得出
E6(2)—E6(2)
这条链看着有些怪怪的，它的两端都是同一个命题E6(2)。但它确实合法且非常重要！它的两端实际上是一个命题，而一个命题不“同”真就是“不真”，也就是假！

2010年04月30日 06点04分 1

level 7

jcvb 楼主

于是，我们得出了E6!=2。
例3：

A1(6)==A4(6)—C6(6)==E6(6)—E1(6)==A1(6)
根据定理2得到
A1(6)==A4(6)—E1(6)==A1(6)
根据定理1
A1(6)==A1(6)
这种情况和例2刚好相反，我们可以由此得到A1=6。
注意例3的图示，A4(6)和C6(6)明明呈强链关系，为什么标注的却是弱链？因为他们即呈强链又呈弱链，在本例中根据需要我们选择了它的弱链关系，而强链关系用不上。
例4：

H9(1)—H2(1)==H2(4)—I1(4)==I1(2)—I6(2)==I6(7)—I8(7)==I8(1)—H9(1)，删减H9的1。
一般地，A==B—C==D……==A，则A为真。
一般地，A—B==C—D……—A，则A为假。
（强弱交替，长度为奇数）这就是链的基本用法。
3．Grouped链
刚才我们讨论的链都是结点为一个格子的，现在我们要讨论结点是多个格子（区块）的链。
例5：

A9(9)—A3(9)==E3(9)—E8(9)=={D9,F9}(9)—A9(9)，利用这条链删除A9的9。
其中{D9,F9}(9)的含义可以解释为“D9,F9两格中有一格填9”。
为什么E8(9)=={D9,F9}(9)呢？因为在6宫内，能填9的地方只有E8,D9,F9三格，这个9要么放在E8要么放在D9,F9中，所以它们呈强链。
为什么{D9,F9}(9)—A9(9)呢？因为9列中只能出现一个9，不可能A9和D9,F9内都出现，所以它们呈弱链。
4．唯一矩形和链
合格的数独都必须是唯一解，唯一矩形技巧就是利用这个性质而做出删减的。
例6：

观察AB57四格：如果B5的3和B7的2都不成立，那么这四格将成为一个唯一矩形，这是不符合数独唯一解规定的。所以B5(3)和B7(2)不同假，即两者成强链关系 B5(3)==B7(2)。
于是，B6(3)—B5(3)==B7(2)—F7(2)==F7(3)—{F4,F6}(3)==D6(3)—B6(3)，删减B6的3。

例7：