数独假设法 - 试填与逻辑技巧的分界线及可以使用的场合

/约 3 分钟阅读

数独里的假设,是逻辑的一步还是瞎猜,取决于从假设中取出什么结论。本文在同一个盘面上比较试填、反证法与强制链的区别,说明「没有出现矛盾」为何不能确定任何东西,并整理可以使用假设的场合。

假设法算不算逻辑

数独的假设法,是先在某一格暂时放入一个候选数,再往下追看会发生什么的解法。做假设本身并不违反逻辑。它成为逻辑的一步还是变成瞎猜,取决于从假设里取出什么结论。可以取出的结论只有两种。一种是假设导出矛盾时,把这个假设删掉。另一种是两种相反的假设都导出同一结果时,确定这个结果。反过来,仅仅因为假设没有导出矛盾,什么也确定不了。用于分析与练习数独的免费软件 HoDoKu 的说明也明确写道:不产生矛盾的链什么也证明不了。只要守住这两种结论和一条禁令,从假设出发的推理就可以当作逻辑的一步。不守这些规矩,把试填的数字当成已确定的数字一路写下去,才是瞎猜。

试填、反证法与强制链的区别

三种方法都从「暂且认为某个候选数是对的」开始。不同之处在于,开始追之前有没有先定好要取出什么样的结论。试填把数字写进盘面,与已确定的数字同样对待,接着往下解。若一路无矛盾地填满,在唯一解的题里那就是答案。不过,一旦中途出现矛盾,就很容易弄不清哪些数字是试填的、该退回到哪里。反证法把假设当作一条线索来追,只看会不会出现矛盾。出现矛盾就删去该候选数,不出现就连同假设一起放弃,把盘面恢复原样。强制链则把一格里剩下的所有候选数,或一个数字所有可能的位置,分别假设后去追。只要每个分支都得到同一个结果,这个结果就与假设无关地成立。HoDoKu 把导出矛盾的链也一并归入强制链这一总称。为了便于区分,本文把靠矛盾删去候选数的称为反证法,把靠分支一致来确定的称为强制链。

试填、反证法与强制链的比较
方法假设什么何时可以确定要跟的线索数
试填某格的一个候选数 (写进盘面继续解)只有一路无矛盾地填满时1 条 (失败就要擦掉写下的全部)
反证法某格的一个候选数出现矛盾时,删去该候选数1 条
强制链一格的全部候选数,或一个数字的全部位置所有分支得到同一结果时与候选数或位置数相同

无论哪种方法,没有出现矛盾就停下的线索都确定不了任何东西。

在同一盘面上看反证法

图中的局面,是只用唯一候选数和隐性唯一数一路解下来、再也推不动的地方。格子的位置用「第几行第几列」表示,例如 r5c1 指第 5 行第 1 列。r5c1 的候选数是 2 和 3。在这里假设填 2,只用简单的确定往下追。第 5 行有了 2,候选数为 2 和 4 的 r5c8 就只能是 4。于是第 5 行已有 2 和 4,候选数为 2 / 3 / 4 的 r5c2 只剩 3。这时看第 1 列。能放 3 的只有 r4c1 和 r5c1。r5c1 已假设为 2,而 r4c1 与 r5c2 的 3 同在一宫。第 1 列再没有地方放 3。假设仅两步就导出了矛盾,所以 r5c1 的 2 被删去,剩下的 3 即为确定。反过来追假设为 3 的一边,只用简单的确定,一时推不出新的东西。在这个盘面上,带来信息的只有出现矛盾的 2 那一边。这个推理用一句话就能讲给别人听:如果 r5c1 是 2,第 1 列的 3 就无处可去。能这样简短地说明,是把反证法当作逻辑来用的一个标志。

在 r5c1 假设填 2
9
5
3
4
3
7
6
5
3
4
2
8
1
7
6
9
5
8
3
4
1
8
9
3
7
6
2
8
  • 3 无处可放的第 1 列
  • 由假设推出的 2 格
  • 假设填 2 的格

只靠唯一候选数与隐性唯一数已推不下去的局面。r5c1 的候选数是 2 和 3,r5c8 是 2 和 4,r5c2 是 2 / 3 / 4,r4c1 是 1 / 3 / 5。第 1 列中能放 3 的只有 r4c1 与 r5c1 两格。

为什么没有矛盾也定不下来

同一盘面上的 r4c4 候选数是 5 和 9。在这里假设填 5,只用简单的确定往下追,r6c4 成为 9,r7c4 成为 8,r9c4 成为 4,接着 r4c2 填入 9,r6c1 填入 5,然后就停住了。走了 5 步,一个矛盾也没出现。可是把这道题解到最后,r4c4 的答案是 9。填 5 的假设明明是错的,只是在手头技巧追得到的范围里,矛盾没有显露出来而已。矛盾只能在所用工具够得着的范围内被发现。所以,没有出现矛盾并不能证明假设正确。HoDoKu 说不产生矛盾的链什么也证明不了,正是这个意思。如果把没出问题的一边当成正解,用笔一路写下去,几步之后再卡住时,就分不清从哪里开始是试填的数字了。停下来的线索,应当连同假设一起放弃,把盘面恢复原样。

错误的假设也不出现矛盾
9
5
3
4
3
7
6
5
3
4
2
8
1
7
6
9
5
8
3
4
1
8
9
3
7
6
2
8
  • 由假设无矛盾地填出的 5 格
  • 假设填 5 的格

r4c4 与 r6c4 的候选数都是 5 和 9,r7c4 是 5 / 8 / 9,r9c4 是 4 / 5 / 9。假设填 5 后,简单的确定推了 5 步便停下,没有出现矛盾。在本题的答案里,r4c4 是 9。

两个候选数都追的强制链

这次把 r4c4 的候选数 5 和 9 都追一遍。假设为 5 的分支里,r6c4 成为 9,r7c4 成为 8,r9c4 成为 4。假设为 9 的分支里,r6c4 成为 5,r7c4 仍是 8,r9c4 仍是 4。r4c4 必定是两者之一,所以两个分支共同得到的 r7c4 的 8 与 r9c4 的 4,不论哪个假设成立都是对的。这就是强制链的确定。单看一个分支什么也说不了的局面,把两个分支并排一比,便得到了两个确定。其实这个结论也能由显性数对得出:r4c4 与 r6c4 分占 5 和 9,第 4 列的 5 和 9 被这 2 格用尽,于是 r7c4 是 8,r9c4 是 4。许多有名字的技巧,都可以看作把这类两分支推理折叠成短小形状的结果。在动手找强制链之前,先确认有名字的技巧能否得出同样的结论,要追的步数和要写的东西都会少一些。

两个分支结果相同的格
9
5
3
4
3
7
6
5
3
4
2
8
1
7
6
9
5
8
3
4
1
8
9
3
7
6
2
8
  • 分占 5 和 9 的 2 格
  • 任一分支都确定的格

无论 r4c4 是 5 还是 9,r7c4 都是 8,r9c4 都是 4。同样的结论也能由第 4 列里用尽 5 和 9 的显性数对得到。

逻辑与瞎猜的分界在哪里

逻辑与瞎猜的分界,不在于做不做假设,而在于结论是否依赖假设。用反证法删去的候选数,是假设被证明为错的结果,撤回假设后依然成立。用强制链确定的数字,无论从哪个假设出发都相同,撤回假设后也依然成立。试填一路写下的数字,一旦撤回假设,就连同依据一起消失。只把撤回假设后仍然成立的结论留在盘面上,按这个标准划线就容易多了。另一个参考是线索的长短与分支的多少。像上面那样 2 到 5 步就结束的线索,可以在脑中追完,解完后也说得清楚。一旦分成 3 个以上的分支,或线索拉长到十几步,手工去追就会骤然变难。HoDoKu 把中途分叉又汇合、或依赖前面步骤结果的链称为强制网,归入最后手段一类,并说除非经验非常丰富,否则很难手工找到。在同一类别里,对于只是放个数字看能不能解出来的暴力求解,它写道那其实算不上技巧。与其说逻辑与瞎猜之间有一条清晰的线,不如把它看作从说得清的短推理逐渐过渡到穷举的一段范围,这更接近实际解题的感受。

适合与不适合使用假设的场合

用假设用到什么程度,要看解题的目的。在练习技巧的时候靠假设突破,就会错过发现该局面本该用的技巧的机会。另一方面,把会的有名字的技巧都试过仍推不动时,挑一个候选数只有 2 个的格试一条反证,是手工解题中合情合理的一步。下表整理了各种场合下假设的用法和理由。共同的一点是:在把结论留到盘面上之前,先确认它在撤回假设后是否依然成立。

适合与不适合使用假设的场合
场合假设的用法理由
简单的确定与基础技巧都已用尽从候选数只有 2 个的格出发,只试一条反证短线索能在脑中跟完,也说得清结论
候选数为 2 个的格还剩很多两个分支都跟到底,取共同的结果两边都相同的结果不依赖假设
正在练习技巧不用假设,去找有名字的技巧靠假设突破就失去了找技巧的练习
只想把题解完若要试填,用别的颜色或小字写试填的数字失败时一眼看出要擦掉哪些
不知道是否只有唯一解的题试填填满了,也不要当作唯一答案无法排除还有别的解
线索越拉越长仍无结论先放弃这个假设,把盘面恢复原样中途的错误难以察觉,恢复也费事

要紧的不是用不用假设,而是只把不依赖假设的结论留在盘面上。

常见错误与辨别方法

使用假设时的错误,大多出在取结论的方式上。第一种,是把没有出现矛盾的一边当成确定,上一节 r4c4 的例子就是这样。辨别方法是看确定的理由是否只能说成「因为没出现矛盾」。第二种,是在一个假设之中再叠加另一个假设。在第一个假设之下,第二个假设导出矛盾,能删去的也只是「第一个假设成立时」的第二个候选数,并不能从整个盘面上删除。在嵌套假设里删掉的候选数,放弃外层假设时就要恢复。第三种,是只追一个分支,就断定另一个分支也会一样。强制链要把所有分支都追到底才成立。第四种,是在候选标记有遗漏或错误的盘面上做假设。候选数的清单若有错,由此得到的矛盾与一致都会导出错误的结论。开始假设之前先把候选标记检查一遍,这类错误大多可以避免。第五种,是放弃假设后忘了收拾。沿着试填线索删掉的候选数若没有恢复,下一步推理就建立在错误的候选清单上。跟着假设删候选数时先做个记号,放弃假设时把带记号的候选数全部写回去。

依赖假设前先试的技巧

把假设法留作有名字的技巧都用不上时的最后手段,就不太会妨碍进步。在伸手去做假设之前,最好依次试一试显性数对与隐性数对、宫内指向对与区块排除、X-Wing、XY-Wing 和着色法。其中 X-Wing、XY-Wing 与着色法,都是按某个候选数为真或为假来分情况,只取在所有情况下都成立的部分,因此与短的强制链有着相同的骨架。着色法甚至可以理解为:针对一个数字沿着强链接前进,用颜色把假设的线索留在盘面上的方法。卡住时该按什么顺序检查,以及靠猜填数后会引发的连锁错误,相关文章里都有整理。不靠假设解完的题越多,就越容易分辨哪些局面真正需要假设。