# 为什么需要 17 条线索？你无法把数独再缩小的题目

经典数独为什么至少需要 17 条起始线索，才能保证恰有一个解？探索极限、证明过程，以及这对玩家意味着什么。

从数独中擦掉一个数字，你可能会让它变得更难。擦错了数字，你甚至可能把题目的唯一答案给毁掉。介于填满的棋盘与空白页面之间，存在一个难以逾越的上限：**17 条起始线索**。数独为什么在这里停下？

答案从一个很容易被忽略的问题开始：你的题目只有一个解吗？

## 一个完整棋盘，一个答案

在经典 9×9 数独里，每一行、每一列和每个 3×3 宫都必须恰好各出现一次数字 1 到 9。它们是[尼可利（Nikoli）公布的标准规则](https://www.nikoli.co.jp/en/puzzles/sudoku/)。棋盘上已经印出来的数字叫做 _已知数（givens）_，也就是线索（clues）。

一个完成的棋盘可能遵守所有这些规则，但却未必是由这些起始线索“唯一推出”的答案。如果存在两种不同的完整填写方式，玩家就无法判断出题者原本想要的是哪一种。

这就是“唯一性”如此重要的原因。一个表述良好的经典数独，会给你足够的信息，能准确确定**恰好一个**完成棋盘。如果你还不熟悉规则，我们的[数独入门指南](/en/blog/how-to-play-sudoku)是一个很好的起点。

## 看一条线索如何改变一切

这是一个刻意接近完成的题目。点号标记了空格。

```text
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 数独，都不可能恰好只有一个解**。他们的[原始研究论文](https://arxiv.org/abs/1201.0749)描述了穷举式的计算机搜索。既然存在“恰好 17 条线索”的唯一可解题，那么 17 就是最低要求。

这并不表示：任意挑出 17 个数字的位置与数值，就都能组成合法题目。关键在于它们的**位置与数值**。这个结果也只讨论经典数独；变体中的额外规则会改变问题。

为什么“排除 16”也能排除更小的数量？因为如果某个更小的题目也能只有一个解，你就可以从那个解里补上正确的线索，直到它的已知数达到 16。补上这些线索会保留它原本唯一的答案，这就会与研究结论矛盾。

## 你怎么证明不存在更小的题目？

找到一个“17 条线索”的题目，说明“至少做到 17 是可能的”。要证明“16 做不到”，就得把所有可能性都排除掉。

研究人员对完成的棋盘做了系统搜索，并考虑等价棋盘。他们使用了 _不可避免集合（unavoidable sets）_：那些必须包含线索的格子组，用来阻止出现替代的完成方式。他们还为枚举 _击中集合（hitting sets）_ 做了高效算法——也就是那些与上述集合相交的选择——并检查候选线索集合是否能保持唯一性。[论文解释了方法](https://arxiv.org/html/1201.0749v2)。

上面的矩形给出了这个想法的小例子：如果这四个格子都不放线索，那么两种填法都能存活。只要至少固定这四个格子中的一个，你就会挡住那种特定的互换。在一个较稀疏的题目里，往往需要同时挡住很多种可能替代。

## “最少线索”不等于“最难”

线索数量回答的是“印了多少信息”。但它并不能告诉你：下一步你会发现什么推理。仅仅数一数已知数的个数，并不能揭示下一步是显而易见的一步单解，还是你从未学过的某种模式。

还有一个有用的区别：_minimum（最少）_ 和 _minimal（极小）_。minimum 指的是经典数独中可能出现的**最小线索数量**。minimal 指的是：只要拿掉任何一个已知数，唯一性就会消失。把一题称为 minimal，并不表示它只有 17 条线索。

给你的下一盘题一个小练习：在填入前尝试解释每一次落子——“这是该宫里唯一可能放 4 的格子。”如果你一时解释不出来，就去检查候选数，或者尝试我们[数独解题常用方法](/en/blog/common-techniques-for-solving-sudoku)里的技巧。

下次你看到一个稀疏的数独时：先数线索——然后再去找出每一条线索“为什么重要”。
