什么是数独的链:强链和弱链的思路

读数独高级技巧的讲解,常会看到“强链”(strong link)、“弱链”(weak link)和“链”(chain)这几个词。它们说的都是候选数之间的关系。
前面的文章分别讲了 X-Wing、剑鱼、XY-Wing 和 Unique Rectangle,每篇讲一种形状。这篇文章讲它们背后的强链、弱链和链的思路,用一个盘面一步一步看。
用词和前面几篇一样:横的叫“行”,竖的叫“列”,3×3的粗框叫“宫”,某一格还可能填的数字叫“候选数”。格子的位置写成“第4行第8列”。
强链和弱链
英文的解题技巧网站 HoDoKu 的 Chains and Loops 页面,这样定义两种链:
- 用弱链连起来的两个候选数,不会同时为真。
- 用强链连起来的两个候选数,不会同时为假。
同一页面还换了一种说法:弱链是“如果 a 为真,b 就为假”,强链是“如果 a 为假,b 就为真”。强链就是“两个里一定有一个对”,弱链就是“两个不会都对”。
同一个数字形成的链
假设在一行、一列或一个宫里,某个数字只有两格可以填。这个数字总要填在某一格,所以一格不是,另一格就是。这就是强链。HoDoKu 的页面也说,这种强链需要同一个候选数在一个行、列或宫里正好出现两次。
同一行、列或宫里的同一个数字的候选数,不管有几个,都不会有两个同时成立。这就是数独的规则本身,所以任选两个,都是弱链。
SudokuWiki 的 Weak and Strong Links 页面里有一个例子:列里9的候选数多于两个。页面说明,因为多于两个,所以得不出强的推论。
同一格里形成的链
不同的数字,在同一格里也能连成链。如果一格只有两个候选数,比如6和8,那么不是6就是8。这也是强链。HoDoKu 的页面写道,在只有两个候选数的格子里,这两个候选数之间有强链。
一格只能填一个数字,所以同一格里不同的候选数之间,总是弱链。有三个以上候选数的格子,形不成强链。
归纳一下,强链出现在下面两种情况:
- 在一行、一列或一个宫里,某个数字正好有两格可以填(同一个数字,两个格子)
- 一格正好有两个候选数(同一个格子,两个数字)
SudokuWiki 把前者叫做 bi-location,后者叫做 bi-value。
强链也可以当弱链用
某个数字在一行里只有两格可以填时,这两格既满足“一定有一个对”,也满足“不会都对”。HoDoKu 的页面写道,用强链连起来的两个候选数,总是也用弱链连着,所以在链里可以把强链当弱链用,反过来则不行。
链怎么连
HoDoKu 把链说成是一串推论:从一个前提出发,比如“这一格的这个候选数不成立”,一直推到一个结果。
把链连起来时,强链和弱链要交替使用。从定义就能看出原因。强链是从“假”推到“真”,弱链是从“真”推到“假”,交替连接,推理才能一直走下去。
只用一个数字的链叫做 X-Chain。按照 HoDoKu 的页面,X-Chain 以强链开始,以强链结束;能同时看到链两端的格子,都可以删去这个数字。
例题盘面
下面的盘面是一道题解到一半的样子。这道题的答案只有一个。“·”是空格。
1 2 3 4 5 6 7 8 9
第1行 5 6 3 | 7 1 · | · · 2
第2行 7 9 1 | 6 · · | · 5 ·
第3行 4 8 2 | 3 5 9 | 7 1 6
第4行 3 7 · | 2 4 1 | 8 · ·
第5行 · · · | 9 6 7 | · 3 ·
第6行 · 1 · | 5 · · | · 4 7
第7行 · 5 · | · · · | · 7 ·
第8行 · · 7 | · 9 · | · · ·
第9行 9 3 · | 1 7 5 | · 2 ·
空格有37个。这个盘面里,没有只剩一个候选数的格子,也没有在某行、某列或某宫里只剩一个位置的数字。
找6的链
看数字6。6可以填的格子是下面的○。
1 2 3 4 5 6 7 8 9
第1行 5 6 3 | 7 1 · | · · 2
第2行 7 9 1 | 6 · · | · 5 ·
第3行 4 8 2 | 3 5 9 | 7 1 6
第4行 3 7 ○ | 2 4 1 | 8 ○ ·
第5行 · · · | 9 6 7 | · 3 ·
第6行 ○ 1 ○ | 5 · · | ○ 4 7
第7行 ○ 5 ○ | · · ○ | ○ 7 ·
第8行 ○ · 7 | · 9 ○ | ○ ○ ·
第9行 9 3 ○ | 1 7 5 | ○ 2 ·
第4行的空格有三个,在第3列、第8列和第9列。第9列的第3行已经有6,所以第4行的6只能填在第3列或第8列。第4行第3列和第4行第8列用强链连着。
第9行的空格也有三个,在第3列、第7列和第9列。同样去掉第9列,6只能填在第3列或第7列。第9行第3列和第9行第7列也是强链。
第3列里,6可以填的是第4行、第6行、第7行和第9行四格。候选数有四个,所以第4行第3列和第9行第3列之间不是强链。它们在同一列,是弱链。
四个候选数的链
把这三条链按强、弱、强的顺序连起来。
- 如果第4行第8列不是6,根据第4行的强链,第4行第3列是6。
- 如果第4行第3列是6,根据第3列的弱链,第9行第3列不是6。
- 如果第9行第3列不是6,根据第9行的强链,第9行第7列是6。
也就是说,第4行第8列和第9行第7列,至少有一个是6。这条链以强链开始、以强链结束,正是 HoDoKu 说的 X-Chain 的形状。
1 2 3 4 5 6 7 8 9
第1行 5 6 3 | 7 1 · | · · 2
第2行 7 9 1 | 6 · · | · 5 ·
第3行 4 8 2 | 3 5 9 | 7 1 6
第4行 3 7 ◎ | 2 4 1 | 8 ◎ ·
第5行 · · · | 9 6 7 | · 3 ·
第6行 · 1 · | 5 · · | × 4 7
第7行 · 5 · | · · · | · 7 ·
第8行 · · 7 | · 9 · | · × ·
第9行 9 3 ◎ | 1 7 5 | ◎ 2 ·
和两端的第4行第8列、第9行第7列都在同一行、列或宫里的6的候选数,是两个×。
- 第6行第7列和第4行第8列在右边中间的宫里,和第9行第7列在第7列里。
- 第8行第8列和第4行第8列在第8列里,和第9行第7列在右下的宫里。
不管哪一端是6,这两格都不能是6。所以可以从第6行第7列和第8行第8列删去6。
用同一格里的链确定
第8行第8列的候选数是6和8两个。因为第8行有7和9,第8列有1、2、3、4、5、7,右下的宫有2和7。在这一格里,6和8用强链连着。6删掉以后,第8行第8列就是8。
之后,按顺序填只剩一个候选数的格子和只剩一个位置的数字,这个盘面就能一直解到最后。
Skyscraper 和 X-Wing
上面用到的形状有名字。HoDoKu 的 Single Digit Patterns 页面这样说明 Skyscraper:只看一个数字,找出这个数字只有两个候选数的两行。如果其中两个候选数在同一列,那么另外两个里一定有一个成立,能同时看到这两格的候选数都可以删去。这个盘面的第4行和第9行,在第3列对齐,另外两格分在第8列和第7列。Chains and Loops 页面写道,长度为4的 X-Chain 有时叫做 Turbot Fish;Single Digit Patterns 页面则说 Skyscraper 是 Turbot Fish 的一种特殊形式。
X-Wing 也可以同样用链来解释。在 X-Wing 那篇的盘面里,第3行和第6行的2,都只能填在第2列和第9列。第3行第2列和第3行第9列是强链,第6行第2列和第6行第9列也是强链。
- 如果第3行第2列不是2,第3行第9列就是2。
- 如果第3行第9列是2,同在第9列的第6行第9列就不是2。
- 如果第6行第9列不是2,第6行第2列就是2。
两端的第3行第2列和第6行第2列都在第2列。其中一个是2,所以第2列的其他格子可以删去2。把同一条链倒过来走,第9列的其他格子也可以删去2。和 Skyscraper 的不同在于,两行里另外两格也在同一列。
假设和链
数独可以用假设(瞎猜)吗 那篇写的是先假设填一个数字,再看会不会出现矛盾的做法。
上面的链也是从“如果第4行第8列不是6”开始的。但它没有选定其中一种情况往下走。不论第4行第8列是不是6,结论都一样:第6行第7列和第8行第8列不能是6。每一步都是强链或弱链,都来自行、列、宫的规则。
链的前提是笔记写得正确。强链来自“只有两个候选数”,所以如果哪里漏写了一个候选数,就会把不是强链的关系当成强链。笔记的写法写在数独候选数(笔记)的写法里。
关于 Sudoku365
Sudoku365 是一款可以在 iPhone、iPad 和 Android 上玩的数独应用。盘面是标准的 9×9。有简单、中等、困难、专家四个难度,每个难度 300 题,共 1200 题。有每天一道的每日挑战和连续记录,还可以通过蓝牙两个人对战或合作。
打开“笔记”,就可以在格子里写候选数。把设置里的“从笔记中移除数字”(默认开启)打开,填入正确的数字时,相关格子里相同的笔记会自动擦掉。选中一个格子时,同一行、列、宫和相同数字的格子会高亮。
应用免费,带广告,可以一次性购买“移除广告”来关闭广告。一个人每天坚持的用法写在 Sudoku365 使用技巧 里,第一道题怎么开始,写在 Sudoku365 入门 里。
Sudoku365每日数独,也能两个人玩查看应用 →