强弱关系
数独中的“关系”描述的是不同填数情况之间的逻辑约束:某一格能否填入某个数字,可能影响另一格的填数。
例如,同一行中的数字x不能重复。如果确定单元格C中必须填x,就可以从这一行的其他单元格中删除候选数x。这种“一个填数成立,另一个就不能成立”的约束就是一种弱关系。
又如,同一行中必须有一个数字x。如果x原本只能填在两个单元格中,而其中一格被排除了,另一格就必须填x。这种“一个填数不成立,另一个就必须成立”的约束就是一种强关系。
节点
关系连接的对象称为“节点”。最简单的节点表示“单元格C中填入数字x”,记作[C:x]。这种只涉及一个单元格和一个候选数的节点称为“简单节点”,与后文介绍的组合节点相对应。
例如在下面的盘面中,可以用[R1C2:3]表示“在第1行第2列的单元格R1C2中填数字3”。
节点相当于逻辑推理中的“命题”,即一个可以判定为“真”或“假”的陈述。对于简单节点[C:x]:
- 为真,表示
C中填入的数字是x;证明它为真,就可以在C中填入x。 - 为假,表示
C中填入的数字不是x;证明它为假,就可以从C中删除候选数x。
候选数x仍保留在C中,只说明这一可能性尚未被排除,并不表示[C:x]已经为真。推理时也可以暂时假设一个节点为真或为假,再沿着关系推导其后果。
组合节点
有时需要把多个填数可能性作为一个整体考虑。例如,可以用一个“组合节点”表示“C1、C2、C3中至少有一格填x”,记作[C1:x, C2:x, C3:x]。它表示[C1:x]、[C2:x]、[C3:x]中至少有一个为真,是这些简单节点的逻辑“或”。
例如在下面的盘面中,[R4C6:8, R5C6:8, R6C6:8]表示“R4C6、R5C6、R6C6中至少有一格填8”。
组合节点[C1:x, C2:x, C3:x]的真假判定为:
- 当
C1、C2、C3中至少有一格填x时,组合节点为真; - 当这三格都不填
x时,组合节点为假。
证明组合节点为真,并不一定能确定具体在哪一格填数;证明它为假,则可以从组内所有单元格中删除候选数x。
弱关系
“弱关系”表示两个节点不能同时为真,也就是两者至少有一个为假。如果判定(或假设)一个节点为真,另一个节点就必然为假。
但弱关系中的两个节点有可能同时为假。但仅凭弱关系,一个节点为假时,无法确定另一个节点的真假。
在这里我们用符号“┉”(Unicode:U+2509)来表示两个节点之间存在弱关系:A┉B。如果画成示意图,则如下图所示:
弱关系在数独中普遍存在。
例如,数独规则要求同一行、列或宫中的每个数字恰好出现一次,不能重复。因此,(以行为例,列和宫同理),如果第n行的两个不同单元格RnCa、RnCb都含有候选数x,则有弱关系[RnCa:x]┉[RnCb:x]:这两个节点至多有一个为真,也可能都为假。
又如,数独中每个单元格只能填一个数字。因此,对于未填单元格RaCb中的任意两个不同候选数x、y,都有弱关系[RaCb:x]┉[RaCb:y]。这两个节点不能同时为真;如果该格最终填入其他数字,它们就都为假。
在下图左边的盘面中,[R4C2:8]┉[R4C8:8]表示在第4行中“R4C2中填8”和“R4C8中填8”之间存在弱关系。右边的盘面中,[R5C5:1]┉[R5C5:9]表示在单元格R5C5中,候选数1和9之间存在弱关系。
“看到”和“影响区域”
描述弱关系时,我们通常会说“节点A可以看到节点B”,表示两者不能同时为真。
对于前面一节中的两个示例盘面,可以分别说“R4C2中的8可以看到R4C8中的8”,以及“R5C5中的1可以看到R5C5中的9”。
当上下文中的候选数明确时,也可以直接说两个单元格“互相看到”。这通常表示两格位于同一行、列或宫。例如,“因为R4C2可以看到R4C8,所以这两格至多有一格填8”。
一个单元格的“影响区域”由与它同行、同列或同宫的其他单元格组成。因此,也可以用“x位于y的影响区域”来描述弱关系。例如,“R4C2位于R4C8的影响区域,所以如果R4C8中填了8,R4C2就不能再填8了”。
“同时看到”和“共同影响区域”
当一个节点分别与若干其他节点形成弱关系时,可以说它“同时看到”这些节点。“共同影响区域”则是这些单元格各自影响区域的交集。
例如在下面的盘面中,“R4C6可以同时看到R4C7和R5C4,因此当R4C7或R5C4中有任何一个是2时,R4C6都不能填入2”表示的是两个弱关系[R4C6:2]┉[R4C7:2]和[R4C6:2]┉[R5C4:2]。这两个弱关系也可以描述为“R4C6位于R4C7和R5C4的共同影响区域中,因此……”。
在用交替推理链删数时,如果链两端对应同一个候选数,通常可以得出“从能同时看到链两端的单元格中删除该候选数”的结论。
当弱关系中有组合节点时,“一个简单节点A能看到组合节点B”指的是“A能看到B中的每个简单节点”。对于相同候选数,也可以说A所在的单元格位于B中所有单元格的共同影响区域。
在下面的盘面中,简单节点[R6C7:7]可以看到组合节点[R6C1:7, R6C3:7],因为R6C7与组内两格都在同一行。简单节点[R8C3:7]只能看到组内的[R6C3:7],因此不能说它看到了整个组合节点。
“一个组合节点A能看到组合节点B”指的是“A中的每个简单节点都能看到B中的每个简单节点”。对于相同候选数,这意味着A中的每个单元格都位于B中所有单元格的共同影响区域。
在下面的盘面中,组合节点[R1C1:4, R2C1:4]可以看到组合节点[R3C2:4, R3C3:4],因为两组中的所有单元格都位于同一宫。但它看不到组合节点[R2C8:4, R2C9:4],因为R1C1看不到后者中的任何一格。
强关系
“强关系”表示两个节点不能同时为假,也就是两者至少有一个为真。如果判定(或假设)一个节点为假,另一个节点就必然为真;但仅凭强关系,一个节点为真时,无法确定另一个节点的真假。
在这里我们用符号“━”(Unicode:U+2501)来表示两个节点之间存在强关系:A━B。示意图如下:
例如,[R1C1:1]━[R1C8:1]表示“R1C1中填1”和“R1C8中填1”之间存在强关系。
对于简单节点,通过数独规则直接得到的强关系主要来自两种结构:双值格和共轭对。
双值格
当未填单元格C中只剩两个候选数x和y时,称C为“双值格”。由于每格必须填入一个数字,C中必定填x或y,所以[C:x]和[C:y]至少有一个为真,形成强关系[C:x]━[C:y]。
在下面的盘面中,除R3C9外,所有未填格都是双值格。以R1C1为例,[R1C1:2]━[R1C1:7]就是双值格型强关系。
共轭对
当某一区域(行、列或宫)中尚未填入数字x,且x只剩两个可填位置时,这两个位置对应的节点称为一个“共轭对”。例如,第n行中的x只能填在RnCa或RnCb中。由于这一行必须有一个x,[RnCa:x]和[RnCb:x]至少有一个为真,形成强关系[RnCa:x]━[RnCb:x]。列和宫中的情况相同。
在下面的盘面第1行中,候选数1只能出现在R1C1和R1C8中,因此[R1C1:1]━[R1C8:1]是共轭对型强关系。
组合节点间的强关系
如果一个区域中某个数字的所有可填位置可以分成两组,那么这两组对应的组合节点之间也存在强关系:一组都不填这个数字,另一组就必须有一格填它。
例如,左图第1宫中的候选数7只出现在R1C2、R2C2、R3C1、R3C3中,因此有[R1C2:7, R2C2:7]━[R3C1:7, R3C3:7]。右图第2行中的候选数6只出现在R2C2、R2C3、R2C7、R2C8、R2C9中,因此有[R2C2:6, R2C3:6]━[R2C7:6, R2C8:6, R2C9:6]。这两种结构分别出现在空矩形的“十字交叉区”和大行列远程数对的“枢纽”中。
逻辑推导得到的强关系
强关系也有可能是通过逻辑推导得到的:
在交替推理链中,可以推导出两端节点至少有一个为真,因此它们之间存在逻辑上的强关系。
在着色技巧中,同组的两种颜色代表互补的真假状态,因此一种颜色中的任意节点与另一种颜色中的任意节点之间都存在强关系。
可视作弱关系的强关系
双值格、共轭对,以及同一区域中由组合节点形成的强关系,都同时满足“至少一真”和“至多一真”,也就是恰好一真。因此,这些节点之间既是强关系,也是弱关系。换言之,由“能互相看到”的节点形成的强关系,本身也是一种弱关系。在链中需要弱关系的位置,可以将这类强关系视作弱关系。
但“强关系”这一逻辑定义本身只保证至少一真,通过推理得到的强关系不一定同时满足弱关系,不能一概把它当作弱关系使用。
实际上,在解题过程中,当需要弱关系时直接去找“可以看到”的关系即可,不必在意找到的关系是否同时构成强关系。
基于强弱关系的删数逻辑
强关系和弱关系的一个重要作用就是帮助删除候选数,用于简化盘面。
如果节点A和B之间存在强关系,而节点X能同时看到它们(即X分别与A、B形成弱关系),就可以确定X为假。
如上图所示,强关系保证A和B至少有一个为真,而它们中任意一个为真,都会通过弱关系使X为假。因此,即使尚不知道强关系哪一端为真,也可以确定X为假。
如果X是形如[C:x]这样的简单节点,则可以从单元格C中删除候选数x。
基于强弱关系的数独技巧
- 交替推理链:基于强、弱关系交替出现的链状结构进行推理的技巧。
- 着色:根据强关系给节点着色,并结合弱关系进行推理的技巧。