← StudyX Devlog

数独可以用假设(瞎猜)吗

Hiroki ObaraHiroki Obara · DeveloperSudoku365使用指南
数独可以用假设(瞎猜)吗

候选数全写好了,会的技巧也都找了一遍,下一格还是定不下来。眼前有一个只有两个候选数的格子,看起来随便填一个就能往下走。一直玩数独的人,会一次又一次遇到这种场面。

在之前的文章里,我写过瞎猜着填数字不算解题。不过,「先填个数字试试」其实有好几种。这篇文章写它们的区别,以及有理由可依的假设方法。

瞎猜、试错、反证法

「先填个数字试试」大致有三种形式。

瞎猜。 填进候选数中的一个,然后接着往下解。解到最后就结束了。中途卡住的话,就只能在不知道哪里错了的情况下拿起橡皮。

试错。 填进候选数中的一个往下解,出现矛盾就退回到那一格,改填另一个。这样反复下去,总会得到答案。电脑解数独的基本方法就是这个。英文维基百科的 Sudoku solving algorithms 把「回溯」,也就是往空格里按顺序填数字、违反规则就退回前一格的方法,说明为穷举搜索的一种。

反证法。 假设「如果这一格是4」,从那里沿着能确定的格子往下推。如果推出了矛盾,就得出「这一格不是4」的结论,把4从笔记里删掉。假设的数字不留在盘面上。

第三种和数学证明里的反证法是同一个形式。「假设是4会矛盾,所以不是4」,这个推理在逻辑上是对的。和瞎猜不同,结论有确实的理由。

反证法形式的假设

也有一种看法认为,反证法形式的假设是可以用的。理由可以举出两个。

一是有名字的技巧里,也有「如果这样的话」来想的。比如 XY-Wing,就是分情况来想的技巧:「中间的格子是 A 的话,这边是 C;是 B 的话,那边是 C;不管哪种,C 都在其中一格。」可以说是把两个小假设并排放在一起。详细写在 数独进阶技巧 里。

二是即使在高手之间,从哪里开始算「假设」,界线也并不清楚。英文的数独解说网站 SudokuWiki,把假设一个候选数、顺着推出矛盾的 Nishio 技巧,一边说成「半试错式的方法」,一边又当作有固定步骤的技巧来介绍。

另一方面,瞎猜和试错,也有人觉得与其说是在解题,不如说更接近对答案。一直填到最后看合不合,这件事电脑一瞬间就能做完。

反证法的用法

用反证法时,按下面的顺序进行。

  1. 选一个只有两个候选数的格子。 在候选数多的格子上假设,要推的范围会太大。
  2. 假设其中一个,只沿着能确定的格子推。 假设「这一格是4」,同行、同列、同宫的笔记里就去掉4。结果如果有格子只剩一个候选数,那一格也就确定了。就这样,只沿着一个个能确定的格子推下去。
  3. 找矛盾。 矛盾指的是:同一行、列或宫里出现两个相同的数字;出现一个候选数都没有的格子;某个数字在某一行、列或宫里无处可填。
  4. 出现矛盾,就删掉假设的数字。 已经知道「不是4」,就把原来那一格笔记里的4删掉。因为原本只有两个候选数,所以就确定是另一个了。
  5. 没有矛盾却推不下去时,就当作什么都没弄清楚。 把假设推出来的东西全部擦掉,回到原来的盘面。

第5点最重要。没有出现矛盾,并不能证明假设是对的,只是在能推到的范围里没有矛盾而已。如果留着假设继续往下走,本来想用的反证法就变成瞎猜了。

一个小例子

只示意形状。假设某一宫里有3个格子,笔记是这样的:

  • 格子A:4 或 7
  • 格子B:4 或 9
  • 格子C:4 或 9

假设A是4。B和C在同一宫,所以都不能是4,B和C都变成9。同一宫里有两个9,这是矛盾,所以A不是4。A确定是7。

其实,这个例子不用假设也能解。B和C是两个候选数都只有「4和9」的格子。4和9被这两个格子用完,所以同一宫的其他格子里都可以删掉4和9。这就是 初学者最先要学的基本技巧 里写的「两个格子的组合」。

用假设的一个收获就在这里。用假设找到的矛盾,多半是还没看出来的技巧换了一种说法。找到矛盾之后,回到盘面上想想为什么会矛盾。如果在那里发现了有名字的形状,下次不用假设也能做到同样的事。

用假设之前

反证法很费工夫。在想假设之前,有两件事要先确认。

一是笔记对不对。如果删掉了不该删的候选数,什么技巧、什么假设都不会正确地起作用。笔记的检查方法写在 数独卡住了怎么办 里。

二是难度。正如 数独的难度由什么决定 里写的,已经确认过 Sudoku365 的“简单”只用基本技巧、“困难”用到预约和两格、三格组合为止的技巧,每道题都能解到最后。在这个范围里卡住的话,与其假设,不如去找漏掉的技巧更快。“专家”里,很多题即使用上全部有名字的技巧也解不完,到这时,反证法这样的推理才派上用场。

在 Sudoku365 里试假设

Sudoku365 是我做的数独应用,可以在 iPhone、iPad 和 Android 上玩。4个难度各300题,共1200题,每道题的答案都只有一个。

在应用里试假设之前,有一点要知道。你填的数字会马上和答案对照。填错的数字显示成红色,计为一次错误,错3次游戏结束。填对的数字就那样定下来。也就是说,抱着假设的想法填数字,其实就变成了对答案。

所以,在应用里试假设时,不用数字,而用笔记。把推下去的格子的笔记改掉,出现矛盾时,把原来那一格笔记里假设的数字删掉。推的过程中改过的笔记,可以用“撤销”一步一步恢复。填数字时自动擦掉的笔记,也会随撤销恢复。不过,错误次数不会退回。

提示一开始有10个,每通关一道题加1个,看广告也加1个。假设也定不下来时,用提示填一格,再想想为什么那里是这个数字,也是不错的用法。

应用免费,带广告,可以一次性购买“移除广告”来关闭广告。第一道题怎么开始,写在 Sudoku365 入门里。

在 App Store 下载 在 Google Play 下载

Sudoku365每日数独,也能两个人玩