9 Sudoku 下载

为什么我这道数独有不止一个解?

四种真正的原因、那个一定会造成第二个解的矩形图形、17 这个数字到底说了什么,以及一个求解器真正是怎么验证唯一解的。

一道数独只有在恰好只有一个解的时候,才算得上是一道题。这不是审美偏好,而是推理得以成立的前提。如果两张不同的完整盘面都能对得上题面上的已知数,那么总会走到某一步,任何逻辑都告诉不了你该往哪边走,唯一的出路就是挑一边试试看。

如果你真的碰上了这种局面,现实中的原因只有四种。

一、你前面填错了

这是压倒性最常见的一种,而且它伪装得很好。二十步之前填错的一个数字,通常不会立刻炸出矛盾,它炸出来的是一个「两个格子看起来可以互换」的局面——因为本来能把这两个格子区分开的那条约束,已经被那个错数毁掉了。

检验起来很快:把你自己填进去的每一个数字,都按行、列、宫的规则核一遍。只要某个数字在同一个单元里出现了两次,答案就在这儿,题目本身没有任何问题。会标错的 App 会当场告诉你;在纸上就得自己一格一格核。

二、致命矩形

这一种是真的会保证出现两个解,值得学会认。

设想四个格子正好落在一个矩形的四个角上:两行、两列,而且——这一点最关键——只跨了两个宫。再设想这四个格子全是空的,而且每个格子都只能填同样的两个数字,比如 2 和 5。

那么不管你解出来的是哪张盘面,你都可以把这四个角整体对调:矩形上的每个 2 换成 5,每个 5 换成 2。每一行里两个数字仍然各一个,每一列里仍然各一个,两个宫里也仍然各一个——因为每个宫正好装着矩形完整的一条边。盘面上其他任何地方都没被动过。所以第二个同样合法的解一定存在。

「只跨两个宫」这个条件,才是这件事成立的关键。如果四个角分别落在四个不同的宫里,对调会破坏宫的约束,这个图形也就无害了。

老手会反过来用它:在一道自己信得过是合格题的盘面上,既然致命图形不可能出现,那就可以把会造出这个图形的那个候选数删掉。但这条推理只有在题目确实验证过唯一解时才站得住,所以它是个捷径,算不上一个技巧。

三、已知数挖得太多了

如果这道题是你自己出的,或者是你从一张完整盘面上往下删数字得到的,唯一性并不会自动成立。你每挖空一格,就删掉了一条约束,而越过那条界线的那一刻,没有任何东西会提醒你。

已知的下限是 17。2012 年,McGuire、Tugemann 和 Civario 用穷举计算机搜索确认:不存在只有 16 个已知数还能保持唯一解的数独,而 17 个已知数的题目确实存在。

要看清这句话说了什么、没说什么:17 是整个问题空间的地板,不是任何一道题的保证。绝大多数 17 个已知数的摆法都有很多个解,25 个已知数的摆法里也有一大堆是多解的。数量几乎什么都说明不了,只有真去数一遍才算数。

四、出题程序压根没验过

有些题目来源——免费的盘面打印网站、老旧的 App、从别处扒来的题库——只管挖到某个已知数数量就直接发货。验证唯一解是要花真金白银的算力的,而省掉这一步在玩家撞上歧义局面之前完全看不出来。到那时,玩家多半还会以为是自己填错了。

真正的验证长什么样

验证唯一性意味着数解的个数,而不是求出一个解。求解器照常跑它的搜索,但不在找到第一张完整盘面时停下,而是继续往下找。让这件事变得便宜的窍门是提前退出:你从来不需要知道总共有多少个解,只需要知道是一个还是多于一个,所以计数上限设成二,一旦找到第二个立刻放弃搜索。

静心数独在每一次挖空之后都会做这件事。格子是成对地按中心对称拿掉的,每拿掉一对,求解器就以上限二数一次解。只要结果不是恰好一个,这一对立刻原样填回去,生成器换个地方继续。没通过检查的题目根本走不到你面前,所以在这个 App 里出现歧义局面,永远意味着是第一种原因。

一张速查表

常见问题

一道唯一解的数独最少需要几个已知数?

十七个。2012 年 McGuire、Tugemann 与 Civario 的穷举搜索证明了不存在唯一解的 16 个已知数的数独,而合法的 17 个已知数的题目是已知存在的。这是整个题目空间的地板,并不是某一道 17 个已知数的题目自动具备的性质。

有两个解的题还能玩吗?

你可以把它填完,但没法把它推出来。总会走到某一步,你要在两个都自洽的选项之间做选择,而没有任何逻辑理由偏向其中一边。多数人会认为,从那一刻起它就不再是数独了。

怎么判断一道题是不是唯一解?

只能用求解器去数解的个数,没有肉眼可判的办法。唯一的例外是致命矩形:四个空格子分别落在两行、两列、两个宫构成的矩形四角上,且候选数都是同样的两个,那么不用再验,它至少有两个解。

这个 App 会不会出现有两个解的题?

不会。生成过程中每挖掉一次格子都会验证唯一性,任何破坏唯一性的挖空都会被立刻撤销。不唯一的题目根本不会被生成完,更谈不上被显示出来。

拿真题试一遍

静心数独按「解题真正需要的最难技巧」给每道题定难度,题目在交到你手上之前就验证过唯一解,提示会说出用的是哪一种技巧,而不是只把数字填进去。免费、离线、无广告、无账号。

在 App Store 下载

相关文章

全部指南