欢迎光临散文网 会员登陆 & 注册

第 49 讲:复杂致命结构初步

2021-08-25 11:06 作者:SunnieShine  | 我要投稿

本篇章将为大家介绍的是数独技巧里最难的四大技巧板块:致命结构、鱼(链列)、飞鱼导弹和网。这四个板块的难度可能超乎想象,可能刚开始学习,学会了,第二天就忘掉逻辑和证明了。所以这些技巧都值得反复去推敲,而且作用很大。

Part 1 致命结构的确切定义

在之前的内容里,我们简单描述了有关致命结构技巧的基本原理和运用,而在之前,它具有两种不同的证明致命形式的方式,一种是类似于数组置换产生两种填法的方法,例如唯一矩形和唯一环;另外一种则是类似于某一个行或列的涉及的单元格左右或上下对应交换形成致命形式的,例如拓展矩形。

那么,致命结构的确切定义呢?我们从这两种类型里提取出相同的方式:当所涉及的结构内部的填法相对于盘面而言不是唯一的填法的(即包括多种填法和无解填法,多种填法以UR为代表,无解填法以BUG为代表,即怎么填最终都会矛盾),而结构对盘面其余任何位置都是孤立的,即不会导致任何外界其它单元格的填数影响的,称为致命结构。

那么,以此我们将产生出非常多的变体形式的致命结构。接下来我们就来看看到底都有什么类型。

Part 2 致命结构的致命类型探讨

2-1 数组置换类型

思考一下UR形成致命形式的原理:内部可以发生交换,进而产生两种不同的、不造成外部影响的填数模式。那么我们试着把UR和UL这两种都是一样的变换形式的技巧结合在一起,看它能形成什么样的形状。

如左图所示,观察c1,我们发现6存在共轭对,这意味着,r78c1有且仅有一格是6,那么,另外一格都不应为9。那么我们接下来就要说明的就是,为什么另外一个单元格不应该是9。

如果r78c1有一个是6,而且此时另一格为9的话,算上r6c79、r7c67、r8c69这六个单元格的话,结构一定是致命的。我们此时把r78c1看成6、9数对。我们看成6、9数对后,观察结构所在的所有区域(r678c1679b6789)。因为结构不是UR那样规则的结构,所以我们只能尝试去利用假设的方式来看。r6、c79、b69内都有4、9数对、c6、b8内都有4、6数对、c1、b7内6、9数对、r78有4、6、9三数组,即如右图所示。

显然,结构里必定会产生两种相反的填数模式。但是显然,管它怎么填,这个结构涉及的各个区域上都已经产生了固定的数对或更高阶的数组。所以不管怎么交换实际上都是没有实质性效果的,完全影响不到其它位置。但是,就内部有不同的填数模式而言,就相当于已经产生了两种形式的填数模式了。而纵观整个盘面,我们把刚才结构存在的区域下的所有数组删数都清除掉,并把两种填数情况分裂为两个盘面对比来看的话,那么它们的剩余盘面则是完全一致的。换句话说,这两种不同的填法都直接可以得到同一个“剩余盘面”。数独唯一解,要求每一个单元格都只可以有一种填法(也就是整体的题目的每一个单元格来说,答案上只可能是唯一的一个数,别无其他可能),这样一来,结构就形成致命形式了(虽然不知道它这种致命形式到底叫什么名字)。

这种结构实际上叫做双值格致命结构(Bi-value Deadly Pattern),因为它对应的致命形式,每一个单元格都是双值格。那么有没有多值格致命结构(Multi-value Deadly Pattern)呢?是有的,不过我们这一节不介绍。

同时,我们得到了一个结论:如果一个盘面存在像上图这样的全双值格结构,并且形成不影响外界,但内部可发生交换的形式,那么题目一定不是唯一解的

2-2 行列交换类型

                                             

如图所示,如果r6c7(5)假的话,那么观察r46c234678这十二个单元格,横着看都是134789六数组,完全一样的。既然都是一模一样的六数组,很明显,r4的填数和r6的填数就可以完全交换一下,也就是说,r4c2和r6c2交换、r4c3和r6c3交换、r4c7和r6c7交换,诸如这样的方式。

这样把所有的六格的填数交换一下,上面的填数放到下面去,下面的填数放到上面去,这也完全对全盘没有丝毫的影响。所以,我们可以认定它是一种致命结构。

实际上,这一类型的致命结构是有互补视角的。我们回顾一下之前提到的一个问题:为什么结构上下对应的候选数会如此相似。比如上一题里,结构r4c2和r6c2的候选数情况完全一样,r4c3和r6c3也一样,其它也都是(除了删数的单元格r6c7这一组不一样以外)。

我们在之前的解答里,是这么说的:由于结构只是涉及行列的上下或左右对应位置的交换,所以它跟宫没有任何影响。而且实际上,在这些单元格的所处行列上,确实具有完全相同的数字作出了排除,所以候选数是一样的。

那么,我们参照这一点,换做互补的视角来看看。如图所示。

我们把r46提取出来,把之前涉及的12个单元格抛开不看,只看剩余的位置,即确定值。此时我们可以发现,当r6c9 = 5的时候,r46的所有确定值信息完全一样:都是2、5、6。显然,既然出现了一样的填数信息了,那么r46剩下的单元格就一定是完全一样的数字,那么上下就必然能产生对应位置互换的方法了,这样就产生了两种填数方法,故形成了致命形式,所以r6c9 <> 5。

所以,可以看到这个例子里,删数是互补视角上的r6c9(5),而原视角里删数则是r6c7(1348),即其它都删了,除了5没删。这就形成了鲜明的互补视角。所以,如果我们发现一个结构比较大的话,或者说一个疑似致命结构比较大的话,可以尝试使用互补视角来解决观察的问题。

那么,我们从这个视角里产生一个特殊的结论:如果同一个并排三宫里的两行或者两列没有任何的确定值信息,题目一定是多解的。所以,如果你看到这样的结构,那么题目一定是多解题(当然,其余位置如果产生显然的矛盾,这一种情况另说)。

接着,我们再来看一种更神奇的逻辑。

2-3 数字交换类型

2-3-1 反转唯一环

如图所示。此时我们换个思维。全盘只有这样涂色的五个单元格有确定值8和9。如果说r6c9(8)此时为真的话,r2c46、r5c69、r6c49就会构成关于8和9的确定值版本的唯一环结构。

那么我们现在要说明,确定值版本的唯一环结构在此时是致命的。由于是确定值,而确定值就可能包含提示数信息,所以显然不能直接交换。而如果我们可以尝试对于所有没有填数的单元格,又都含有候选数8和9的地方全部随便填入一种方式,只要不违背数独规则即可,然后对这些位置全部都互换一下。

我们假设此时盘面的解唯一的话,那另外一个盘也应当有唯一的解,而且是完全一样的解(除了这里8和9互换的地方不同外)。试想一下,一道唯一解的题会不会存在这样,有局部的数值进行互换之后,剩下却完全一致的盘面对应同一个解的情况?当然不存在。所以这便形成了致命形式。

我们将这种利用确定值形成唯一环(或唯一矩形)形式来反向证明出致命形式的模式,叫做反转致命形式(Reverse Deadly Pattern),它实际上包含两种情况,一种是前一个示例给出的拓展矩形的互补视角,称为反转拓展矩形(Reverse Extened Rectangle);而另一种就是这一节讲到的反转唯一矩形(Reverse Unique Rectangle)或反转唯一环(Reverse Unique Loop)。

请注意,在观察确定值的时候,一定要找到全盘所有的这些数字,不要单纯认为其中只要一部分形成了唯一矩形或唯一环就算可以了,实际上这是不对的,因为其它没有被勾选出来的这些确定值可能给剩余的单元格一些确定值,出数或删数的结论都是可以存在的,所以我们一定要找全盘的所有这两种确定值。

那么我们接下来来看一些反转唯一矩形的例子。

2-3-2 一个更大的反转唯一环

如图所示,如果r7c3(9)为真,则涂色的8个单元格将会构成唯一环形状的结构,而全盘所有的8和9都已经被涂出来,构成此形式。

显然,这样就会导致剩余盘面的8和9的填数位置没有其它的可确定的提示信息,使得8和9显然会出现两种不同的填入方式,使得出现多种填法,违背唯一解的要求。所以r7c3 <> 9。

2-3-3 反转唯一矩形

全盘只有三个位置有确定值1和2。如果r1c3(1)为真,就会构成确定值版本的唯一矩形,全盘别无其他关于1和2的提示信息,故1和2的填数无法继续判断和确定。所以这样的结构必然是致命的。

2-3-4 直推反转唯一矩形

如图所示,如果r1c12(4)都为假后,我们将立即产生一个直推反转唯一矩形(Direct Inference Reverse Unique Rectangle),从r1c2(8)开始,使得b7里只有r7c1可以填入8,且r1c1只能是1,此时全盘所有填入确定值1和8就确定下来,而且构成了唯一矩形的形状。

而之前说过,这种结构是必然会使得剩余盘面的1和8的填数可以产生置换,所以产生多种填法,进而违背数独的唯一解的要求。所以,我原假设r1c12(4)形成区块,即至少有一个是成立的,当作区块,删除b1和r1的其余位置的候选数4。

2-3-5 位于大列里的反转唯一环

如图所示,首先发现全盘的6和7只有b369里存在。当r2c7 = 7时,6和7的所有提示信息将构成反转唯一环的结构,使得其余任何一个地方都没有6和7的提示信息,即使题目能够继续完成下去,但到最终,6和7都无法继续往下,因为此时的6和7已经没有任何提示信息可以让它们往下完成了,这个时候,所有空位上可以放入6的地方也可以放入7,使得产生多种不同的填数结果。而题目是唯一解的,肯定不会允许这样的情况出现,所以这种结构应当是予以避免的,故原本的假设错误,故r2c7 <> 7。

2-3-6 另外一种位于大列里的反转唯一环

有些时候,反转唯一环的使用不像是上面的一些示例一样,它可能仅仅在并排的三个宫里。

如图所示,这个结构便是这样。请仔细观察左侧b124578里的8和9,可以发现到的是,8出现了很多,但9一个都没有。我们这么去思考:由于b124578并不存在任何8和9的提示信息,而其中的所有8都只是我们填入的数字,这并不足以说明它一定是题目的一部分。如果r2c7(1)和r5c9(1)同假,则两个单元格都只能填入9,使得b369里8和9的确定值构成了唯一环的类似形状。

和上一题类似,如果r2c7(1)和r5c9(1)同时去掉后,b369有关8和9的确定值已经填好,但b124578里的8和9却依然不可确定。虽然在这六个宫里,数字8都已经填好,但这些数字仅仅是作为自己填入的数字出现,所以并不是提示数,即无法固定到盘面上,它们的确定并非是完全成立的。换句话说,它们并不一定是正确的填数,所以和提示数不同。因此,作为这六个宫里的数字,8和9依旧可能产生多种不同的填法,因为b369填好的8和9的排布模式已经不能再给出有效的8和9的确定值,故其它剩余的8和9将会形成多种填法,即致命形式。

仔细揣摩这个推理思路就可以发现,它和之前的反转唯一环不太一样,但又有相似的推导思路,不过更加灵活了。

2-3-7 利用不同真的反转唯一矩形

如图所示,我们尝试假设r78c2(9)区块为假作为开头,则r6c2(6)为真。显然,全盘只有这三处有6和9,如果此时r4c2 = 9,则构成反转唯一矩形的致命形式。所以r4c2(9)为假。接着,后面的逻辑就不用多作解释了。

2-3-8 另一则利用弱关系的示例

如图所示。链的推导就不过多阐述了,我们来看r4c6(6)-r7c1(3)的成立的原因。如果它们同真,必然会导致r4上填入2、3的位置被挤入到r4c12里,而此时r7c1(3)为真,r7c2是2,那么r47c12就只有2和3,构成类似于唯一矩形的环状结构,而全盘所有确定值2和3已经被我们确定下来,如果这么填数的话,2和3将不再存在确定值,导致2和3在余下的部分里可以互换形成两种填法,进而违背唯一解的要求。

所以规避这个内容,我们认定r4c6(6)-r7c1(3)是成立的,所以引出了这一条不连续环,得到了删数。

2-3-9 推导更麻烦的反转唯一矩形

如图所示,假设r1c8(1)为假,则ALS区域{r1c8, r2c7}里必然得到r2c7(4)为真,所以r1c9(4)为假。不过由于刚才假设r1c7(1)为假,所以r1c8(7)是为真的,因此r1c9此时不会含有数字7,那么r1c9只能填入3了;接着,当r1c9(3)为真时,r1c2(3)为假,而刚才假设r1c8(7)为真的缘故,所以显然此时r1c2(8)必须为假。否则全盘所有确定值7和8就固定下来,而构成唯一矩形的形状,导致7和8的剩余盘面将产生可交换的情况,导致非唯一填法,违背唯一解的要求。所以r1c2(8)为假,故r1c2此时只能使得r1c2(1)为真。

所以r1c28里必须有一个1是成立的,所以删除它们的交集,即r1c1(1)。

实际上可以看出,这是一个环结构,不过麻烦的地方在于,它的内部嵌套了众多的分支,所以这里就不讨论其它地方的删数了(你可以尝试找找看,到底还有没有额外的删数)。

那么,我们根据这一个致命形式,可以得到一个结论:如果全盘没有出现至少两种数字的任何确定值,则题目一定是多解的

2-3-10 完全分离的两个反转唯一矩形?

下面我们来看一种比较特殊的情况,不过它稍微需要一点链。

如图所示。我们先尝试认为链结构是对的,并认为处于r56c26的3和8会构成反转唯一矩形的致命形式,稍后我们再作出原因的说明。我们先来看链结构:假设r6c2(3)为假,则按照链结构,顺次得到r6c2(5)为真、r6c5(5)为假、r1c5(5)为真、r1c6(5)为假,并最终得到r12c6(28)毛刺显性数对为真。

当链头r6c2(3)为真时,我们认为反转唯一矩形成立,则可以删除r6c6(8);如果链尾r12c6(28)为真时,显然也可以删除r6c6(8),所以r6c6 <> 8。

下面我们来思考,这样的结构为什么依然是成立的。为什么我们之前说,“不允许在结构之外出现这些数字的任意确定值”,但这个例子里却出现了,但依旧可行呢?这是因为,外部出现的3和8,依旧完全构成了反转唯一矩形的形式,即构成了唯一矩形一般分属于两个宫的构型。这样的话,即使有这些3和8的确定值,它对外部的其余3和8也是不会产生任何影响的。所以,这两个反转唯一矩形实际上是毫无关系,但都对外部不产生其余的影响,故这两个分离的反转唯一矩形此时都是完全成立的。

那么,既然成立了,那么推导逻辑和删数原理也就全部正确了,我们就不再作出说明,下面我们来看一则带强制思维的、这样分离的反转唯一矩形的例子。

2-3-11 分离的反转唯一矩形的另一则示例

下面来看最后一个比较难的例子。

如图所示,如果我们尝试假设r4c6 = 4,则根据图上给出的链的顺序,可以分别得到r5c7 = 4、r6c3 = 4、r2c5 = 4。而此时可以发现,当这些数字填入后,全盘所有的4和9分为了两个反转唯一矩形的构型出现在盘面上。刚才我们说到,这样的两个完全分离的反转唯一矩形互不影响,而也都不会影响到外部的其余4和9,导致其余4和9的确定值无法继续得到,故产生无法填完4和9,即产生多个填数方法的致命形式。

所以,为了规避这个形式的出现,r4c6 <> 4,这便是这个例子的结论。

2-4 对称翻转类型

2-4-1 宇宙法

如图所示,我们将所有1和2的确定值构成一组,3和6一组,4和7一组,5和8一组,9此时没有合适的构成一组。那么你就会发现,这个盘面有一个神奇的现象:拿1和2一组来说,所有1的中心对称的位置恰好都是2,而反过来也是一样;3和6也是这样,所有3的中心对称的单元格上一定是6,其它的也都是这样。

那么我们就可以思考一个问题了。既然确定值的信息是完全中心对称的,那么我们随意在一处地方找到一种技巧,那么与之中心对称的位置就一定会找到与之对应的同一种技巧。比如我们在r34c34上发现了一个环,那么r67c67就一定存在一个环。因为确定值是中心对称的,所以如果有1的技巧,就在对应中心对称的地方找得到2的技巧,因为1和2是中心对称的,其它的技巧也都同理。

而r5c5是这个盘面的对称中心。如果题目是唯一解的,r5c5就不应当放“可以构成一组的两种数字的其中一种”。比如说,r5c5如果是1的话,那与之中心对称的那一个单元格就必然是2。可是r5c5已经是对称中心了,就意味着它的中心对称的位置就是它自己。所以显然要使得r5c5 = 1就必须r5c5 = 2,这样是根本不可能的,所以1和2都不可能放进去。同理,3和6是一组显然不能同时填入;4和7一组不能,5和8一组也不能。所以r5c5只能填入唯一的一个没有配对的数字9了,所以r5c5 = 9。

这种技巧利用了盘面的高度对称性来进行解题,所以是一种非常强大的技巧,但这种技巧也依赖于高度对称的盘面,所以不对称的盘面显然就无法使用这个技巧了。这种技巧叫做宇宙法(Gurth's Symmetrical Placement),中文名称是由中国数独/谜题国家队选手邱言哲命名的,因为宇宙一词的英文为Universe,它的词根就是类似于全盘、全局的意思。

我们再来看一种对称类型:轴对称。

2-4-2 轴对称类型的宇宙法

全盘所有确定值下,4和7一组、5和8一组、6和9一组,剩下的1、2、3各自单独一组。

注意,这里叙述的是单独一组,不是一起的。

关于捺对角线对称的话,r4c4、r5c5、r6c6下就只能为1、2、3,不能是其他数字(这三格恰好在对称轴上)。否则的话,4和7一组,比如r6c6是7的话,为了满足对称性,r6c6还应是4才可以,这样是不符合数独规则的,同样的,6和9也不行,5和8也不行,就只能是1、2、3了。

虽然它们各自一组,但我们依然无法确定到底r4c4是1,是2,还是3。所以我们只能大致知道,这三格一定都只有候选数1、2、3。不过呢,由于三格恰好同宫(b5),所以这三格构成三数组,可以确定删除b5内的其余候选数1、2、3以及这三格内的所有其余候选数。于是,盘面瓦解。

至此,我们就讲完了基本的致命结构基本变换类型,这些变换类型既相似又有各自明显独特的地方。不过,我们之前提到的内容都还算比较容易。接下来我们来看的几个技巧就比较困难了,虽然都是数组置换类型的致命结构。


第 49 讲:复杂致命结构初步的评论 (共 条)

分享到微博请遵守国家法律