数独三数组解法 - 显性三数组与隐性三数组的区分方法
数独的三数组有两种:3 格的候选数合起来只有 3 种的显性三数组,以及 3 个数字的位置只限于 3 格的隐性三数组。本文在一个盘面的同一行里找出这两种,说明两者数的东西与删除的地方有何不同,如何根据空格数决定先找哪一种,以及常见的数错之处。
三数组数的是什么
从数对到三数组有何不同
数对与三数组最大的不同,在于对每格候选数个数的要求。显性数对要求 2 格都只有同样的 2 个候选数。显性三数组则不要求 3 格都带着同样的 3 个候选数。每格的候选数可以是 2 个,也可以是 3 个,只要 3 格合起来的种类不超过 3 种就成立 (据解题软件 HoDoKu 的讲解)。逐一讲解解题技巧的网站 SudokuWiki,把构成显性三数组的候选数排列归纳为下表的 4 种形态。容易漏看的是最后一种。像 {1,6}、{6,8}、{1,8} 这样,每格都只有 2 个候选数,任取 2 格比较,候选数都不一样。若用找数对的眼光去看盘面,因为找不到候选数相同的 2 格,就会直接略过。隐性三数组也一样,3 个数字不必在 3 格里都留有候选。即使某个数字的位置只有 2 格,只要 3 个数字的位置合起来落在 3 格之内即可。
| 形态 | 3 格的候选数示例 | 只有 2 个候选数的格子 |
|---|---|---|
| 3/3/3 | {1,6,8} {1,6,8} {1,6,8} | 0 格 |
| 3/3/2 | {1,6,8} {1,6,8} {1,6} | 1 格 |
| 3/2/2 | {1,6,8} {1,6} {6,8} | 2 格 |
| 2/2/2 | {1,6} {6,8} {1,8} | 3 格 |
形态的分法依据 SudokuWiki 的 Naked Candidates 页面。无论哪种形态,3 格的候选数合起来都是 1、6、8 三种。
在盘面上看显性三数组
下面的盘面来自为本文自编的一道题,只用“候选数只剩一个的格子”和“数字只剩一个位置”两种方法推进,直到无法继续时的局面。在这个局面里,把显性数对、隐性数对、宫内指向对、区块行列消除法用到无法继续为止,删掉的也只有 r5c4 和 r6c4 的 1,第 1 行的候选数一个也没有减少。r 表示行,c 表示列,r1c3 指第 1 行第 3 列的格子。第 1 行有 6 个空格,候选数是 r1c3 {1,6}、r1c4 {4,6,7}、r1c5 {3,4,6,7,8}、r1c6 {6,8}、r1c7 {1,8}、r1c8 {1,3,7,8}。看 r1c3、r1c6、r1c7 这 3 格,候选数合起来只有 1、6、8 三种。3 格各填 1 个数字,所以 1、6、8 会被这 3 格用完。因此可以从第 1 行的另外 3 格中删除 1、6、8。删掉的是 r1c4 的 6、r1c5 的 6 和 8、r1c8 的 1 和 8,共 5 个。这就是上一节表中 2/2/2 的形态。另外,r1c3 与 r2c3 同为 {1,6},在第 1 宫和第 3 列构成显性数对。不过这两个单元里都没有别的空格,所以这个数对删不掉任何候选数。
- 显性三数组的 3 格 (1、6、8)
- 候选数被删除的 3 格
第 1 行空格的候选数:r1c3 {1,6}、r1c4 {4,6,7}、r1c5 {3,4,6,7,8}、r1c6 {6,8}、r1c7 {1,8}、r1c8 {1,3,7,8}。三数组删掉 r1c4 的 6、r1c5 的 6 和 8、r1c8 的 1 和 8,共 5 个候选数。
把同一行读成隐性三数组
这次从数字的一侧再数一遍第 1 行。第 1 行还缺的数字是 1、3、4、6、7、8 这 6 个。逐个数字数位置:3 只能填在 r1c5 和 r1c8,4 只能填在 r1c4 和 r1c5,7 只能填在 r1c4、r1c5、r1c8。把 3、4、7 的位置合起来,正好落在 r1c4、r1c5、r1c8 这 3 格之内。3 个数字被关在 3 格里,所以这 3 格必定填 3、4、7,没有其他数字的余地。这就是隐性三数组,可以从这 3 格中删除 3、4、7 以外的候选数。删掉的是 r1c4 的 6、r1c5 的 6 和 8、r1c8 的 1 和 8,与显性三数组删掉的 5 个完全相同。删除之后,r1c4 为 {4,7},r1c5 为 {3,4,7},r1c8 为 {3,7}。r1c5 的 8 被删掉后,第 5 列里 8 的位置只剩 r6c5,于是 r6c5 确定为 8,盘面由此继续推进。其中有 2 个数字的位置只有 2 格,但只看 3 和 4 并不构成数对,因为 3 的位置与 4 的位置不是同样的 2 格。同一行的两种读法删掉了相同的候选数,这并非偶然,原因在后面的小节说明。
先找哪一种三数组
两种三数组的起点不同。找显性三数组,要从候选数少的格子开始。在每个单元里挑出候选数为 2 个或 3 个的格子,寻找候选数合起来只有 3 种的 3 格组合。候选数有 4 个以上的格子,不可能是显性三数组的一格。找隐性三数组,要从位置少的数字开始。在单元里挑出位置只有 2 格或 3 格的数字,寻找位置合起来落在 3 格之内的 3 个数字。若有位置只剩 1 格的数字,应先把它当作隐性单数确定下来,再考虑三数组。HoDoKu 指出,找较大的隐性组合需要良好的短时记忆,并写道在标好候选数之后,很多解题者更愿意用较大的显性组合。下表整理了两种三数组各自数什么、从哪里删除候选数。
| 要点 | 显性三数组 | 隐性三数组 |
|---|---|---|
| 数什么 | 3 格候选数合起来的种类 | 3 个数字能填的格子 |
| 从哪里找起 | 候选数为 2 个或 3 个的格子 | 位置为 2 格或 3 格的数字 |
| 成立条件 | 3 格的候选数合计 3 种 | 3 个数字的位置合计 3 格 |
| 删除什么 | 单元其他格子里的这 3 个数字 | 3 格之内这 3 个数字以外的候选数 |
| 本盘面的例子 | r1c3、r1c6、r1c7 的 1、6、8 | r1c4、r1c5、r1c8 的 3、4、7 |
在有 6 个空格的单元里,只要有一种三数组,其余 3 格里就有另一种三数组。
空格数决定的表与里
设某个单元有 n 个空格。若其中 k 格构成显性组合,那么剩下的 n - k 格,就是剩下 n - k 种数字的隐性组合。因为 k 种数字被关在 k 格之内,其余的数字只能填进其余的格子。SudokuWiki 也这样说明:显性组合的另一面是隐性组合,隐性组合的另一面是显性组合。这个盘面的第 1 行有 6 个空格,所以 3 格的显性三数组,另一面正是 3 格的隐性三数组。在有 7 个空格的单元里,3 格隐性三数组的另一面是 4 格的显性四数组。有 5 个空格时,3 格显性三数组的另一面是 2 格的隐性数对。由此可以决定从哪一面找。两面删掉的候选数相同,所以找到较小的那一组就够了。空格在 6 个以下的单元里,任何组合总有一面不超过 3 格。有 8 个空格的单元里,3 格显性组合的另一面是 5 格隐性组合,3 格隐性组合的另一面是 5 格显性组合,所以只要从 3 格的一面去找就能兼顾两者。选定单元后,先数空格,再从组合大小不超过空格一半的那一面开始找。
同时落在行与宫里的三数组
有时三数组的 3 格同时落在一行和一个宫里。行与宫的交叉正好是 3 格,所以这是 3 格全部在交叉之内的情形。HoDoKu 称之为锁定三数组:显性组合若同时限定在行和宫之内,就可以从两个单元删除候选数。列与宫的交叉也一样。例如某一行第 1 到 3 列这 3 格的候选数合起来只有 3 种,就能从该行其余 6 格,以及包含这 3 格的宫的其余 6 格中删除这 3 个数字。在一个单元里找到三数组后,最好确认这 3 格是否也落在另一个单元里。据 HoDoKu 说明,交叉只有 3 格,所以不存在锁定四数组。
常见错误与辨别方法
之一,是只找 3 格都带着同样 3 个候选数的形态。2/2/2 的形态里,没有一格带着第 3 个数字,只扫一眼候选数很难察觉。养成数 3 格候选数合起来有几种的习惯,就能不论形态都找得到。之二,是把候选数合起来有 4 种的 3 格当成三数组。{1,6}、{6,8}、{1,3,8} 合起来是 1、3、6、8 四种,什么也删不掉。之三,是 3 格不在同一个单元里。若 2 格在同一行,第 3 格只是与其中一格同宫,就没有让 3 个数字填满的单元。之四,是在隐性三数组中,漏看 3 个数字之一在单元的其他格子里还有位置。在这个盘面里,若 7 也能填在 r1c3,3、4、7 的位置就扩展到 4 格,不构成三数组。之五,是弄错删除的地方。若对显性三数组删除 3 格之内的候选数,或对隐性三数组,把 3 格里剩下的其他数字 (此盘面中为 1、6、8) 从单元其他格子删除,就会连正确答案一起删掉。这些错误,只要在删除之前再确认一次,自己数的是格子的候选数还是数字的位置,就能避免。