Sudoku Explained

专家 约 8 分钟

当唯一还能走的棋是「试着填一个」

其他技巧都在找图形。这一个只是假设一个值,然后顺着后果往下走,直到盘面自相矛盾。

一句话版本

反证链是在某一格假设一个值,顺着后果往下推。如果这个假设导致矛盾——某格一个候选都不剩,或某个数字在一个单元里有两个家——那这个假设就是错的。

挑候选最少的那格,两条分支各试一次。通常一条会崩,这一格就解出来了。

为什么这不是猜

这个区别很重要,不是抠字眼。

猜是你无法验证的假设。你填一个数,继续走,然后祈祷。如果后面崩了,你得倒回去,而且常常不知道错是从哪一步进来的。

反证链是一个证明。你假设一个值,推出矛盾,于是断言这个值不可能。矛盾是可核对的——你可以指着那一格说「它一个候选都不剩了」。这是一个合法的逻辑演绎,和 XY-Wing 里的两情况论证没有性质上的区别。

它和前面那些技巧的差别在范围,不在严谨性。XY-Wing 证明的是关于三格的结论;反证链证明的是关于这个假设所触及的一切,可能是整张盘面。

步骤

  1. 挑一个两候选的格子。 分支越少越省事,而两候选的格子只要崩一支就彻底解出来了。
  2. 假设候选甲。 轻轻写上去,纸面上就记在一边。
  3. 往下推。 只做被迫的推论:冒出来的裸单、被改动的单元里的隐性唯一数、以及你填下的数字带来的排除。不要再做第二个假设——一个假设两次的链就是一棵树,手推的树是管不住的。
  4. 盯矛盾。 实践中出现的是这三种:某格候选清零、某单元里某数字无处可放、同一个单元里同一个数字出现两次。
  5. 下结论。 这一支矛盾,甲就不可能,另一个候选就是答案。如果这一支一路推到完整解,那就是你的盘面——但要确认另一支也崩,否则这道题有两个解。

第 3 步的纪律,是把一条有用的链和一团浆糊分开的东西。每一步都必须是被迫的。你一旦引入第二个假设,就不再证明任何东西了。

真实盘面

把 R5C3 的候选逐个试:填 6 一路推下去不产生矛盾;填 3 会推出矛盾(某格没有任何可填的数)。题目只有唯一解,所以这一格是 6。

一格,两个候选,两条分支的表现完全不同。

所以 3 不可能,R5C3 = 6。

证明全部在第二条分支里。你不需要第一条成功,你只需要一条崩掉。这个要求比看上去低得多,也正是反证在几乎任何卡死的盘面上都能用的原因。

实践中的几个变体

完整地测两支很慢,多数人大部分时间用的是更便宜的形式。

单候选推进。 假设一个值,推下去。矛盾了就结束;解完盘面也结束;如果只是没得推了又没矛盾,你什么也没学到——换一格,或者接受做完整测试的成本。

Nishio(逆推)。 假设某个候选为假再推。矛盾就证明这个候选为真。这往往更快,因为排除的传播面比填数更广。

单数字链。 跟着一个数字在一串单元里的可能位置走,找它位置分布上的矛盾。这是可以推广成「交替推理链」的那种形式。

三者都是同一个动作:假设、推进、撞矛盾。

陷阱

假设两次。 最常见的失败。你假设了一个值,推不动了,于是又假设一个接着走。你现在手里的是一个打扮成证明的猜测,结论一文不值。

漏掉矛盾。 候选清零好看见,同单元两个同样的数字也好看见。某单元里某数字无处可放这一种最常被漏,因为它要求你去检查那些你根本没碰过的单元。

看到「推得通」就收手。 一条分支推到完整解,并不能证明另一条会崩。如果两条都通,这道题有两个解,你学到的是关于题目的事,不是关于这一格的事。

用得太早。 反证链几乎能撬开任何盘面,所以它诱人去跳过那些图形技巧。这是个错误,原因有两个:它慢得多,而且它什么都没教你关于结构的事。先把梯子走完。

用在哪

反证属于最后,在鱼、翼和唯一性论证之后。它保证你永远不会真的卡死——而这个保证,正是它不该是你第一伸手的原因。

有一种情况它会插队:当你怀疑某个候选数是错的。如果盘面卡住、所有技巧都失效,一条很短的、立刻推出矛盾的反证链,是确认盘面上有东西错了的快速办法。那是诊断用途,不是解题,也是这个技巧最有价值的用法。

常见疑问

什么是反证链?

在某一格假设一个候选,把后果推下去,直到出现矛盾。崩掉的那个假设被排除,剩下那个就是答案。

试填算不算猜?

反证链不是猜。猜是你无法验证的假设;反证链是从某一支推出矛盾,等于证明了这一支是错的。

该从哪一格开始?

候选最少的那格,通常是两个。两候选的格子只有两条分支,而只要一条崩掉,这一格当场就解了。

什么时候用?

最后。鱼、翼、唯一性论证都失效之后。它永远管用——正因如此,它才该是你最后才伸手的东西。