第 71 讲:试数
从此处开始,我们将开始阐述最后一个数独技巧的理论部分:没办法的办法(Last Resort)。它们一般是在学习的技巧都无法完成解题后,产生的一大数独技巧。它们一般毫无逻辑可言,或者说逻辑层面来讲,不适合人脑的思维和观察,诸如后续会介绍到的回溯法(Backtracking for Sudoku)。不过,这一类题目在比赛和其他的很多时候,使用起来可能比起相对于人脑可接受的逻辑技巧而言要好使一些,所以也受到竞赛流派的玩家喜爱。
当然了,这类技巧的使用与否,取决于你的目的。如果你只是为了完成题目呢,就不用过于在意技巧;而如果你想享受做题的过程,请尽量使用逻辑层面的技巧来解题。
Part 1 使用逻辑
我们要阐述一种无逻辑技巧:试数法(Bowman's Bingo)。它的使用比较轻松。
1-1 类似于链的基础使用方式

如图所示,我们随意设定一点的填数为真,比如这里设定r4c2 = 2为真,然后顺次可以发现r6c3 = 8、r6c9 = 5、然后使用r6c9 = 5对r3作排除,可以得到r4c6 = 5,然后对r5作排除,得到r5c1 = 5,于是r5内只有r5c2可以填3,于是r5c2 = 3。
随机发现c2,发现c2内1没有填数位置了。所以矛盾,因此最开始的假设是错误的,即应当是r4c2 <> 2。

这一幅图,是刚才的试数的填数显示过程,你可以仔细看一下。
我们再来看一则示例。
1-2 带有技巧结构的试数推导过程

如图所示,我们尝试假设r1c8 = 5,就会顺着箭头发现3、4、9的三数组结构,由于r1c8 = 5和三数组的关系,r3c8不能再放下5和3、4,所以r3c8只能填入8。

接着我们继续向下试数。得到r3c8 = 8后,我们就会按照箭头依次得到r3c4 = 6、r4c4 = 2,于是r4c89构成3、4的显性数对。
此时配合最初的三数组就可以发现,此时四个单元格只有3、4、9三种候选数,显然是不够填的,所以出现矛盾,故原本的假设错误,即r1c8 <> 5。
1-3 试数UR
下面我们来看看试数的UR结构。


如左图所示,我们假设r3c9 = 5,则r3c8 = 2,于是根据两个填数结论共同得到r3c2 = 4,于是r2c2 = 5。此时观察b2,发现b2此时只有r1c5可以放4,所以r1c5 = 4,于是根据r1c5和r3c2都填入的4得到b3的4的位置只能在r2c9。你也可以结合右图的推导过程来进行分析。
但发现,由于假设r3c9 = 5,得到了r23c29构成了关于4和5的UR的致命形式,所以假设错误,故r3c9 <> 5。
这一则示例是配合了试数和直推的逻辑进行UR的论证,所以称为试数UR。
Part 2 试数转链
当然了,有一部分简单的试数法,可以修改为链写法。

如图所示,这就是刚才的试数法的链写法。可以看到的是,实际上它被转换为了一个不连续环。不过第二则示例想要改成试数,就有点棘手了:因为假设r1c8 = 5的时候,需要借用这个假设才能得到r3c8的填数结论,相当于多出了一个分支,但分支不长。如果画成动态链,会有些“小题大做”。
Part 3 链和试数的异同
很多人在看了链这种技巧之后,发现它越发是试数,于是就有读者会考虑,链是不是就是一种特殊的试数过程呢?其实不然。
我们回顾一下试数的过程:试数是随机找点,假设为真,然后一格一格向单元格内推导填数,最终发现类似于“同一区域内有相同的数字出现”、“同一区域内没有某个数字可以填入”、“某一个单元格没有数字可填”、“某一个单元格同时填入两个数”之类的矛盾,从而推翻原定假设的过程。
我们再回顾一下链的过程:链也是随机找点,假设为假,然后按照真假性依次推理(注意,链的中途是可以插入其他技巧的,相邻的节点可以同真假,并且是以候选数为单位),最终得到某个相同的数为真,或者是同一区域下的另外一个数为真,从而删除头尾的交集的过程。
它们相同点在于,试数和链都使用真假来推导,而不同的是,试数可以发散寻找。也就是说,试数在某个情况下,不仅只按照“一条路试到尾”的过程,还可以按照两个甚至多个方向试数,在方向上灵活性很强;而链虽然有动态链形式,但链最初的结构,仅仅只是为了一个方向上进行假设和推导的。但是,由于链的节点是以候选数为单位的,所以推导的时候必然可以非常灵活。任意两个节点可以同真、同假或是一真一假。
试数的过程可以任意进行扩散,但如果题目稍难,试数就变得非常困难和复杂。而且,目前在出题层面上,有一种消去后门机制(Backdoor Deletion),可以去掉里面称为“后门”的东西,防止题目在找到这样的“后门”后,使得题目大大降低难度。而链就很好地避免了这一点。链是候选数层面的推导,只要避免“后门”出现在某种技巧的删数结论下,就完全可以避免试数成功。
之所以产生动态链,是因为在链的推导过程之中,一个方向上的推导已经无法完整得到删数了,此时将借助两个、甚至多个方向上的情况来导致矛盾。所以,强制链、动态链都不是试数。但是,试数和链是可以等价转化的。这也就是说,链可以转化为试数过程;而试数,也可以转化为链的写法。可这并不代表它们就是一个东西,推导层面、方式和证明手段的不同就决定了两种东西的本质区别。
链非常容易观察。因为链的强弱关系决定了两个数字之间具有什么样的位置关系和填数关系,毕竟链是一条路到头的推导。
最后,在计算机编程过程之中,这样的试数过程会被简化为从r1c1开始按从左到右、从上到下的顺序依次试数,直到推导出矛盾之后,原假设为假。这样的过程称之为回溯法(Backtracking),有些地方也被称为阿里阿德涅之线(Ariadne's Thread)。我们之后会介绍到。
后门分两种,一种是魔术格(Magic Cell),指的是数独盘面里,如果得到某单元格的填数,就能把一道难题的难度大幅度降低,那么这个单元格就叫做魔术格;另外一种,则是针对于候选数层面的“魔术候选数”,不过这个说法类比于魔术格可以理解:如果某个候选数的真假结论被得到,就能大幅度降低题目的难度的话,那么这个候选数就可以称为所谓的“魔术候选数”。不过术语里并没有这个词,只是用于类比和描述它罢了。
Part 4 带有试数思想的链
当然了,因为试数比起链来说,要好观察一些,所以这样的思想往往还被用于链之中。

如图所示,我们不标注出链的写法。这里简单阐述一下逻辑。
我们设定链头r8c9 <> 2,于是可以得到r78c9的7、9数对,于是得到r1c9只能填8,于是r1c4 = 1;于是r4c4 <> 1后,发现r4出现2、3、6、7的四数组结构。所以r4c8 = 1。
而刚才试数的过程之中,我们得到了r1c9 = 8,并且由于r4c8 = 1,所以r3c8不能填1、不能填8、只能填2,所以我们就得到了r8c9 <> 2时,r3c8 = 2,于是形成思路链条,删掉它们两格的交集的2,图中即r23c9和r9c8的2,都是可以删掉的。
这样的思维,基本的逻辑是链的假设,在中间插入了试数的风格,所以称为带有试数思想的链;当然了,反过来就称为带有链思想的试数法,不过我们就不作出介绍了。