专家 约 8 分钟
当唯一还能走的棋是「试着填一个」
其他技巧都在找图形。这一个只是假设一个值,然后顺着后果往下走,直到盘面自相矛盾。
一句话版本
反证链是在某一格假设一个值,顺着后果往下推。如果这个假设导致矛盾——某格一个候选都不剩,或某个数字在一个单元里有两个家——那这个假设就是错的。
挑候选最少的那格,两条分支各试一次。通常一条会崩,这一格就解出来了。
为什么这不是猜
这个区别很重要,不是抠字眼。
猜是你无法验证的假设。你填一个数,继续走,然后祈祷。如果后面崩了,你得倒回去,而且常常不知道错是从哪一步进来的。
反证链是一个证明。你假设一个值,推出矛盾,于是断言这个值不可能。矛盾是可核对的——你可以指着那一格说「它一个候选都不剩了」。这是一个合法的逻辑演绎,和 XY-Wing 里的两情况论证没有性质上的区别。
它和前面那些技巧的差别在范围,不在严谨性。XY-Wing 证明的是关于三格的结论;反证链证明的是关于这个假设所触及的一切,可能是整张盘面。
步骤
- 挑一个两候选的格子。 分支越少越省事,而两候选的格子只要崩一支就彻底解出来了。
- 假设候选甲。 轻轻写上去,纸面上就记在一边。
- 往下推。 只做被迫的推论:冒出来的裸单、被改动的单元里的隐性唯一数、以及你填下的数字带来的排除。不要再做第二个假设——一个假设两次的链就是一棵树,手推的树是管不住的。
- 盯矛盾。 实践中出现的是这三种:某格候选清零、某单元里某数字无处可放、同一个单元里同一个数字出现两次。
- 下结论。 这一支矛盾,甲就不可能,另一个候选就是答案。如果这一支一路推到完整解,那就是你的盘面——但要确认另一支也崩,否则这道题有两个解。
第 3 步的纪律,是把一条有用的链和一团浆糊分开的东西。每一步都必须是被迫的。你一旦引入第二个假设,就不再证明任何东西了。
真实盘面
一格,两个候选,两条分支的表现完全不同。
- R5C3 写着「3、6」。
- 假设 6:后果一路推下去很顺,盘面完整解开,没有冲突。
- 假设 3:推到某一步撞上死路——有一格最后一个候选也没了。
所以 3 不可能,R5C3 = 6。
证明全部在第二条分支里。你不需要第一条成功,你只需要一条崩掉。这个要求比看上去低得多,也正是反证在几乎任何卡死的盘面上都能用的原因。
实践中的几个变体
完整地测两支很慢,多数人大部分时间用的是更便宜的形式。
单候选推进。 假设一个值,推下去。矛盾了就结束;解完盘面也结束;如果只是没得推了又没矛盾,你什么也没学到——换一格,或者接受做完整测试的成本。
Nishio(逆推)。 假设某个候选为假再推。矛盾就证明这个候选为真。这往往更快,因为排除的传播面比填数更广。
单数字链。 跟着一个数字在一串单元里的可能位置走,找它位置分布上的矛盾。这是可以推广成「交替推理链」的那种形式。
三者都是同一个动作:假设、推进、撞矛盾。
陷阱
假设两次。 最常见的失败。你假设了一个值,推不动了,于是又假设一个接着走。你现在手里的是一个打扮成证明的猜测,结论一文不值。
漏掉矛盾。 候选清零好看见,同单元两个同样的数字也好看见。某单元里某数字无处可放这一种最常被漏,因为它要求你去检查那些你根本没碰过的单元。
看到「推得通」就收手。 一条分支推到完整解,并不能证明另一条会崩。如果两条都通,这道题有两个解,你学到的是关于题目的事,不是关于这一格的事。
用得太早。 反证链几乎能撬开任何盘面,所以它诱人去跳过那些图形技巧。这是个错误,原因有两个:它慢得多,而且它什么都没教你关于结构的事。先把梯子走完。
用在哪
反证属于最后,在鱼、翼和唯一性论证之后。它保证你永远不会真的卡死——而这个保证,正是它不该是你第一伸手的原因。
有一种情况它会插队:当你怀疑某个候选数是错的。如果盘面卡住、所有技巧都失效,一条很短的、立刻推出矛盾的反证链,是确认盘面上有东西错了的快速办法。那是诊断用途,不是解题,也是这个技巧最有价值的用法。
常见疑问
什么是反证链?
在某一格假设一个候选,把后果推下去,直到出现矛盾。崩掉的那个假设被排除,剩下那个就是答案。
试填算不算猜?
反证链不是猜。猜是你无法验证的假设;反证链是从某一支推出矛盾,等于证明了这一支是错的。
该从哪一格开始?
候选最少的那格,通常是两个。两候选的格子只有两条分支,而只要一条崩掉,这一格当场就解了。
什么时候用?
最后。鱼、翼、唯一性论证都失效之后。它永远管用——正因如此,它才该是你最后才伸手的东西。