数独假设法 - 试填与逻辑技巧的分界线及可以使用的场合
数独里的假设,是逻辑的一步还是瞎猜,取决于从假设中取出什么结论。本文在同一个盘面上比较试填、反证法与强制链的区别,说明「没有出现矛盾」为何不能确定任何东西,并整理可以使用假设的场合。
假设法算不算逻辑
试填、反证法与强制链的区别
三种方法都从「暂且认为某个候选数是对的」开始。不同之处在于,开始追之前有没有先定好要取出什么样的结论。试填把数字写进盘面,与已确定的数字同样对待,接着往下解。若一路无矛盾地填满,在唯一解的题里那就是答案。不过,一旦中途出现矛盾,就很容易弄不清哪些数字是试填的、该退回到哪里。反证法把假设当作一条线索来追,只看会不会出现矛盾。出现矛盾就删去该候选数,不出现就连同假设一起放弃,把盘面恢复原样。强制链则把一格里剩下的所有候选数,或一个数字所有可能的位置,分别假设后去追。只要每个分支都得到同一个结果,这个结果就与假设无关地成立。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 就无处可去。能这样简短地说明,是把反证法当作逻辑来用的一个标志。
- 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 说不产生矛盾的链什么也证明不了,正是这个意思。如果把没出问题的一边当成正解,用笔一路写下去,几步之后再卡住时,就分不清从哪里开始是试填的数字了。停下来的线索,应当连同假设一起放弃,把盘面恢复原样。
- 由假设无矛盾地填出的 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。许多有名字的技巧,都可以看作把这类两分支推理折叠成短小形状的结果。在动手找强制链之前,先确认有名字的技巧能否得出同样的结论,要追的步数和要写的东西都会少一些。
- 分占 5 和 9 的 2 格
- 任一分支都确定的格
无论 r4c4 是 5 还是 9,r7c4 都是 8,r9c4 都是 4。同样的结论也能由第 4 列里用尽 5 和 9 的显性数对得到。
逻辑与瞎猜的分界在哪里
逻辑与瞎猜的分界,不在于做不做假设,而在于结论是否依赖假设。用反证法删去的候选数,是假设被证明为错的结果,撤回假设后依然成立。用强制链确定的数字,无论从哪个假设出发都相同,撤回假设后也依然成立。试填一路写下的数字,一旦撤回假设,就连同依据一起消失。只把撤回假设后仍然成立的结论留在盘面上,按这个标准划线就容易多了。另一个参考是线索的长短与分支的多少。像上面那样 2 到 5 步就结束的线索,可以在脑中追完,解完后也说得清楚。一旦分成 3 个以上的分支,或线索拉长到十几步,手工去追就会骤然变难。HoDoKu 把中途分叉又汇合、或依赖前面步骤结果的链称为强制网,归入最后手段一类,并说除非经验非常丰富,否则很难手工找到。在同一类别里,对于只是放个数字看能不能解出来的暴力求解,它写道那其实算不上技巧。与其说逻辑与瞎猜之间有一条清晰的线,不如把它看作从说得清的短推理逐渐过渡到穷举的一段范围,这更接近实际解题的感受。
适合与不适合使用假设的场合
用假设用到什么程度,要看解题的目的。在练习技巧的时候靠假设突破,就会错过发现该局面本该用的技巧的机会。另一方面,把会的有名字的技巧都试过仍推不动时,挑一个候选数只有 2 个的格试一条反证,是手工解题中合情合理的一步。下表整理了各种场合下假设的用法和理由。共同的一点是:在把结论留到盘面上之前,先确认它在撤回假设后是否依然成立。
| 场合 | 假设的用法 | 理由 |
|---|---|---|
| 简单的确定与基础技巧都已用尽 | 从候选数只有 2 个的格出发,只试一条反证 | 短线索能在脑中跟完,也说得清结论 |
| 候选数为 2 个的格还剩很多 | 两个分支都跟到底,取共同的结果 | 两边都相同的结果不依赖假设 |
| 正在练习技巧 | 不用假设,去找有名字的技巧 | 靠假设突破就失去了找技巧的练习 |
| 只想把题解完 | 若要试填,用别的颜色或小字写试填的数字 | 失败时一眼看出要擦掉哪些 |
| 不知道是否只有唯一解的题 | 试填填满了,也不要当作唯一答案 | 无法排除还有别的解 |
| 线索越拉越长仍无结论 | 先放弃这个假设,把盘面恢复原样 | 中途的错误难以察觉,恢复也费事 |
要紧的不是用不用假设,而是只把不依赖假设的结论留在盘面上。
常见错误与辨别方法
使用假设时的错误,大多出在取结论的方式上。第一种,是把没有出现矛盾的一边当成确定,上一节 r4c4 的例子就是这样。辨别方法是看确定的理由是否只能说成「因为没出现矛盾」。第二种,是在一个假设之中再叠加另一个假设。在第一个假设之下,第二个假设导出矛盾,能删去的也只是「第一个假设成立时」的第二个候选数,并不能从整个盘面上删除。在嵌套假设里删掉的候选数,放弃外层假设时就要恢复。第三种,是只追一个分支,就断定另一个分支也会一样。强制链要把所有分支都追到底才成立。第四种,是在候选标记有遗漏或错误的盘面上做假设。候选数的清单若有错,由此得到的矛盾与一致都会导出错误的结论。开始假设之前先把候选标记检查一遍,这类错误大多可以避免。第五种,是放弃假设后忘了收拾。沿着试填线索删掉的候选数若没有恢复,下一步推理就建立在错误的候选清单上。跟着假设删候选数时先做个记号,放弃假设时把带记号的候选数全部写回去。