为什么需要 17 条线索?你无法把数独再缩小的题目
从数独中擦掉一个数字,你可能会让它变得更难。擦错了数字,你甚至可能把题目的唯一答案给毁掉。介于填满的棋盘与空白页面之间,存在一个难以逾越的上限:17 条起始线索。数独为什么在这里停下?
答案从一个很容易被忽略的问题开始:你的题目只有一个解吗?
一个完整棋盘,一个答案
在经典 9×9 数独里,每一行、每一列和每个 3×3 宫都必须恰好各出现一次数字 1 到 9。它们是尼可利(Nikoli)公布的标准规则。棋盘上已经印出来的数字叫做 已知数(givens),也就是线索(clues)。
一个完成的棋盘可能遵守所有这些规则,但却未必是由这些起始线索“唯一推出”的答案。如果存在两种不同的完整填写方式,玩家就无法判断出题者原本想要的是哪一种。
这就是“唯一性”如此重要的原因。一个表述良好的经典数独,会给你足够的信息,能准确确定恰好一个完成棋盘。如果你还不熟悉规则,我们的数独入门指南是一个很好的起点。
看一条线索如何改变一切
这是一个刻意接近完成的题目。点号标记了空格。
5 3 4 | 6 . 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | . . 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
它一共有 78 条线索并且只有一个解。第一行需要一个 7。第四行则需要在第四列放 7,并在第五列放 6。
现在把 第一行第四列的 6 擦掉。此时有四个空格,并且有两种填法:
| 格子 | 填法 A | 填法 B |
|---|---|---|
| 第 1 行第 4 列 | 6 | 7 |
| 第 1 行第 5 列 | 7 | 6 |
| 第 4 行第 4 列 | 7 | 6 |
| 第 4 行第 5 列 | 6 | 7 |
其他数字都保持不变。两种填法都满足每一行、每一列、每个宫,以及所有剩余线索。那四个格子组成了一个矩形,其中的 6 和 7 可以互换而不违反任何规则。我们检查了解的数量:原题恰好只有一个完成方式;擦掉之后,恰好变成两个。
删除某条线索不会让“已经能成立的那个解”失效——因为它仍然会满足所有剩余线索。真正可能发生的是:它会让另一种答案也变得可行。哪怕这题有 77 条已知数,它仍然是有歧义的,所以仅仅线索数量多,并不能保证唯一性。
为什么 17 是最低值
Gary McGuire、Bastian Tugemann 和 Gilles Civario 证明了:任何含 16 条已知数的经典 9×9 数独,都不可能恰好只有一个解。他们的原始研究论文描述了穷举式的计算机搜索。既然存在“恰好 17 条线索”的唯一可解题,那么 17 就是最低要求。
这并不表示:任意挑出 17 个数字的位置与数值,就都能组成合法题目。关键在于它们的位置与数值。这个结果也只讨论经典数独;变体中的额外规则会改变问题。
为什么“排除 16”也能排除更小的数量?因为如果某个更小的题目也能只有一个解,你就可以从那个解里补上正确的线索,直到它的已知数达到 16。补上这些线索会保留它原本唯一的答案,这就会与研究结论矛盾。
你怎么证明不存在更小的题目?
找到一个“17 条线索”的题目,说明“至少做到 17 是可能的”。要证明“16 做不到”,就得把所有可能性都排除掉。
研究人员对完成的棋盘做了系统搜索,并考虑等价棋盘。他们使用了 不可避免集合(unavoidable sets):那些必须包含线索的格子组,用来阻止出现替代的完成方式。他们还为枚举 击中集合(hitting sets) 做了高效算法——也就是那些与上述集合相交的选择——并检查候选线索集合是否能保持唯一性。论文解释了方法。
上面的矩形给出了这个想法的小例子:如果这四个格子都不放线索,那么两种填法都能存活。只要至少固定这四个格子中的一个,你就会挡住那种特定的互换。在一个较稀疏的题目里,往往需要同时挡住很多种可能替代。
“最少线索”不等于“最难”
线索数量回答的是“印了多少信息”。但它并不能告诉你:下一步你会发现什么推理。仅仅数一数已知数的个数,并不能揭示下一步是显而易见的一步单解,还是你从未学过的某种模式。
还有一个有用的区别:minimum(最少) 和 minimal(极小)。minimum 指的是经典数独中可能出现的最小线索数量。minimal 指的是:只要拿掉任何一个已知数,唯一性就会消失。把一题称为 minimal,并不表示它只有 17 条线索。
给你的下一盘题一个小练习:在填入前尝试解释每一次落子——“这是该宫里唯一可能放 4 的格子。”如果你一时解释不出来,就去检查候选数,或者尝试我们数独解题常用方法里的技巧。
下次你看到一个稀疏的数独时:先数线索——然后再去找出每一条线索“为什么重要”。
评论
分享想法、提出问题,或帮助其他数独玩家。
正在检查登录状态…
正在加载评论…