数独链的思路 - 交替追踪强链接与弱链接的读法和记法

/约 4 分钟阅读

数独中关于链的讲解里,经常出现“r3c4 =8= r3c9 -8- r4c9”这样的写法。等号表示强链接,连字符表示弱链接;强弱交替相连且两端都是强链接时,能同时看到两端的格子就可以删去该候选数。本文在盘面上画出一条链,把符号逐个换成文字来读,并介绍同一条链的两种写法和区分链的种类的方法。

记法只靠三种符号就能读懂

链的讲解之所以看起来难,多半难在记法而不在思路。只要弄清符号的含义,再长的链也能从左往右读下去。需要记的符号有三种。第一种是格子的名称,r3c4 表示第 3 行第 4 列的格子,r 是行,c 是列。第二种是等号,用强链接连接两个对象。强链接是指两者中至少有一个必定为真的关系。第三种是连字符,表示弱链接,即两者不可能同时为真的关系。夹在符号中间的数字表示这是哪个数字的链接。因此,“r3c4 =8= r3c9”读作“r3c4 和 r3c9 中必定有一格是 8”,“r3c9 -8- r4c9”读作“r3c9 和 r4c9 不可能都是 8”。链就是把等号和连字符交替排列、两端都以等号结束的东西。两端都是等号时,能同时看到两端的格子里就不可能是这个数字。下表汇总了讲解中常见的符号。

链的记法中使用的符号
符号读法本文中的例子
r3c4第 3 行第 4 列的格子r3c4
=8=8 的强链接(其中一格必定是 8)r3c4 =8= r3c9
-8-8 的弱链接(两格不会都是 8)r3c9 -8- r4c9
(8)r4c5r4c5 的候选数 8(8)r4c9=(8)r4c5
(3=8)r4c9r4c9 格内的强链接(不是 3 就是 8)(3=8)r4c9
r1c6<>8r1c6 不是 8(从候选数中删去)r1c6<>8

等号和连字符的用法依照解题软件 HoDoKu 的讲解页面“Chains and Loops”中的记法。

如何找到强链接与弱链接

要把记法套到盘面上,必须能分辨哪里有强链接、哪里有弱链接。在基本的链中,强链接出现在两种地方。一种是某行、某列或某宫中,某个数字的候选格恰好只剩两个。不在其中一格,就只能在另一格。另一种是只有两个候选数的格子内部。这个格子不是 4 就是 7,所以格内的 4 和 7 由强链接相连。弱链接则多得多。同一行、列或宫中同一数字的候选数之间,无论候选格有几个,都由弱链接相连,因为同一个数字在一行里不能出现两次。由这个区别可以得出一个重要性质:候选格只有两个的行里,这两格既是强链接,同时也是弱链接。因此强链接可以代替弱链接使用,但候选格有三个以上的行中的弱链接,不能当作强链接使用。定义的细节请看词汇表中强链接和弱链接的条目,下面在盘面上确认读法。

在盘面上确认一条链

下面的盘面来自为本文自编的一道题,只用“候选数只剩一个的格子”和“数字只剩一个位置”两种方法推进,直到无法继续时的局面。在这个局面里再用显性数对、隐性数对、宫内指向对和区块行列消除法,能删去的只有宫内指向对删去的 r7c4 的 1,这里要追的 8 的候选一个也不会减少。这里只关注数字 8。8 的候选在第 3 行只有 r3c4 和 r3c9 两格,在第 4 行只有 r4c9 和 r4c5 两格,在第 8 宫 (下排中间的宫) 只有 r9c5 和 r8c6 两格。这就是三条强链接。另一方面,第 9 列的 r1c9、r3c9、r4c9、r5c9、r8c9 五格都有 8 的候选,第 5 列的 r4c5、r6c5、r9c5 三格也有。候选有三格以上,所以这里只能作为弱链接使用。把它们连起来,就得到 8 r3c4 =8= r3c9 -8- r4c9 =8= r4c5 -8- r9c5 =8= r8c6 这条链。强、弱、强、弱、强交替排列,两端的 r3c4 和 r8c6 都以强链接结束。能同时看到两端的空格是 r1c6 和 r7c4,其中 r1c6 与 r3c4 同在第 2 宫,与 r8c6 同在第 6 列。这两格中只有 r1c6 有 8 的候选,所以这条链可以删去 r1c6 的 8。

8 的链与删去 8 的 r1c6
9
6
5
7
8
7
9
2
6
4
7
9
3
9
7
5
4
1
6
2
7
9
5
1
5
6
9
7
6
8
4
7
5
9
5
9
7
6
4
7
4
9
5
6
  • 链的两端(r3c4 与 r8c6)
  • 链中间的 4 格
  • 删去 8 的格子(r1c6)

空格中有 8 的候选的是 r1c6、r1c7、r1c9、r3c4、r3c9、r4c5、r4c9、r5c1、r5c4、r5c8、r5c9、r6c1、r6c5、r6c7、r8c6、r8c7、r8c9、r9c5、r9c7、r9c8 共 20 格。强链接在第 3 行 (r3c4 与 r3c9)、第 4 行 (r4c9 与 r4c5)、第 8 宫 (r9c5 与 r8c6),弱链接在第 9 列 (r3c9 与 r4c9) 和第 5 列 (r4c5 与 r9c5)。

把符号换成文字来读

读链时,先假定左端的格子“不是这个数字”,再把符号逐个换成文字。遇到等号时读作“一方不是,另一方就是”,遇到连字符时读作“一方是,另一方就不是”。这两种读法交替出现,真和假也随之交替。以强链接结束的右端,一定会落在“真”上。下图是从左往右读这条链的过程。如果 r3c4 不是 8,顺着链走到最后,r8c6 就是 8。换句话说,r3c4 和 r8c6 至少有一格是 8。从右往左读也一样:如果 r8c6 不是 8,r3c4 就是 8。无论 r3c4 是不是 8,r1c6 都不是 8。链的基本思路在词汇表的“链”条目中,这里只讲符号的读法。

从左往右读 8 r3c4 =8= r3c9 -8- r4c9 =8= r4c5 -8- r9c5 =8= r8c6
  1. 假定 r3c4 不是 8

    先把左端当作假来开始读

  2. 因为 =8=,r3c9 是 8

    第 3 行的 8 的候选只有两格

  3. 因为 -8-,r4c9 不是 8

    与 r3c9 同在第 9 列

  4. 因为 =8=,r4c5 是 8

    第 4 行的 8 的候选只有两格

  5. 因为 -8-,r9c5 不是 8

    与 r4c5 同在第 5 列

  6. 因为 =8=,r8c6 是 8

    第 8 宫的 8 的候选只有两格

无论 r3c4 是不是 8 (不是时 r8c6 是 8),与 r3c4 同宫、与 r8c6 同列的 r1c6 都不能填 8。

两端是强链接时能删去什么

链能删去什么,取决于两端链接的种类。两端都是强链接、且两端是同一个数字时,能同时看到两端的格子可以删去这个数字。HoDoKu 在讲 X-Chain 时也写道,能同时看到链两端的格子可以删去该数字。这里容易误解的是,以为两端只有一端为真。链所保证的是“至少一端为真”,两端都为真也是可能的。实际上,把这个盘面解到最后,r3c4 和 r8c6 都是 8。即便如此,可以删去 r1c6 的 8 这一结论也不变。反过来,任一端以弱链接结束的链什么也删不掉。例如在 r3c4 =8= r3c9 -8- r4c9 处停下,能说的只有“如果 r3c4 不是 8,那么 r4c9 也不是 8”,哪一格都不会确定或删数。也有两端数字不同的链。HoDoKu 把这种形状称为 AIC 的第 2 型:两端是互相能看到的两格时,可以从起点格删去终点的数字,从终点格删去起点的数字。无论哪种形状,读链时的第一项检查都是两端是否以等号结束。

同一条链的两种写法

链的记法大致有两种流派,不同的讲解使用的写法也不同。一种是在格子之间夹上“=8=”或“-8-”,HoDoKu 称之为 Nice Loop 记法,本文到目前为止用的就是这种。链接属于哪个数字写在符号里面,所以只追踪一个数字的链很好读。另一种称为 Eureka 记法,把候选数字放在括号里写在格子前面,链接只用“=”和“-”表示。用 Eureka 写同一条链,就是 (8)r3c4=(8)r3c9-(8)r4c9=(8)r4c5-(8)r9c5=(8)r8c6。这种写法能像 (3=8)r4c9 这样表示格内的链接,所以适合中途换数字的链。两种写法中,等号是强链接、连字符是弱链接的对应关系都相同。符号的排列看起来再不一样,只要按顺序挑出等号和连字符,就能读成同一条链。如果末尾写着“=> r1c6<>8”,那就是这条链得出的结论。

用两种记法写同一条链
写法本文的链适合的链
Nice Loop 记法8 r3c4 =8= r3c9 -8- r4c9 =8= r4c5 -8- r9c5 =8= r8c6只追踪一个数字的链
Eureka 记法(8)r3c4=(8)r3c9-(8)r4c9=(8)r4c5-(8)r9c5=(8)r8c6含有格内链接的链
用文字写r3c4 和 r8c6 至少有一格是 8只想把结论告诉别人时

无论哪种记法,结论都是 r1c6<>8(r1c6 不是 8)。

链的种类取决于链接的材料

X-Chain、XY-Chain 这些链的名称,区别在于用什么材料构成链接。只要会读记法,即使记不住名称,也能确认链是否正确。X-Chain 是只用一个数字构成的链,本文的例子就是这种,所有链接都在格子与格子之间。XY-Chain 只排列有两个候选数的格子,格内是强链接,格子之间是弱链接。这个盘面的 r4c9 和 r4c5 都只有 3 和 8 两个候选,所以可以写出 (3=8)r4c9 这样的格内强链接。遥距数对(Remote Pair)是所有格子都有相同两个候选的 XY-Chain,据 HoDoKu 说明,要删去任何候选,链至少需要 4 格。AIC 是把这些材料不加限制地混合、交替排列的链的总称。HoDoKu 说,所有的链从根本上说都是 AIC。另外,4 格的 X-Chain 有时被称为 Turbot Fish,W-Wing 和 XY-Wing 也可以读成短链。

主要的链的种类与材料
名称强链接的材料弱链接的材料能删去什么
X-Chain某数字的候选只有两格的行、列或宫同一数字的候选之间能看到两端的格子中的该数字
XY-Chain有两个候选的格子内部相邻格子中的同一数字两端共同的数字,从能看到两端的格子中删去
遥距数对两个候选相同的格子内部这些格子之间4 格以上时,能看到两端的格子中的两个候选
AIC以上材料的组合以上材料的组合取决于两端的数字和位置

定义依据 HoDoKu 的“Chains and Loops”。

常见误读与识别方法

第一种是把弱链接当成强链接使用。这个盘面的第 5 列中,r4c5、r6c5、r9c5 三格有 8 的候选。由“r4c5 不是 8”推出“所以 r9c5 是 8”是错误的,因为 r6c5 仍可能是 8。写等号之前,最好重新数一数那一行、列或宫的候选是否真的只有两格。第二种是把等号读成“相等”。r3c4 =8= r3c9 并不是说两格都是 8,而是说至少有一格是 8。第三种是去读强弱没有交替的链。弱链接连续出现两次,就会从“不是”走到“不是”,什么也推不出来。第四种是从只能看到一端的格子中删去候选。能删的只有同时看到两端的格子,这个例子中是 r1c6 和 r7c4,其中有 8 的候选的只有 r1c6。第五种是在候选标记没有更新的情况下组链。如果刚确定的数字的影响还没反映到候选上,就可能把实际有三格的地方数成两格,造出并不存在的强链接。

读懂记法之后

读懂记法以后,回头再看那些本质上是短链的已有技巧,理解就能连贯起来。着色法沿着一个数字的强链接把格子分成两种颜色,用的材料与 X-Chain 相同。W-Wing 用一条强链接连接两个候选数相同的双候选格,可以读成一条短的 AIC。XY-Wing 可以看作由三个双候选格构成的 XY-Chain。把这些文章里的图用本文的等号和连字符重写一遍,哪里是强链接、哪里是弱链接就一目了然。词汇表中“链”“强链接”“弱链接”的条目,是本文所用词语的定义。