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

第 17 讲:UR 的变体

2020-08-24 21:59 作者:SunnieShine  | 我要投稿

前文我们讲过了UR的基本推理逻辑和思维,今天我们来看它们的一些变体。

请注意,本篇章的内容比较多,而且越来越难,所以我不建议你一次看完,老老实实一个一个去理解吧。

Part 1 区块类型(UR Type 2)

如图所示,这个结构就是上一讲的结构的拓展版。我们可以看到,如果r8c13(5)都没有了的话,r38c13就会构成关于3和9的唯一矩形,至于推导过程这里就不再过多重复了哈。反正就是有3和9的数对,然后结构涉及的区域r38、c13和b17内,都会有这样的39显性数对,于是乎,这个结构内就有两种“互换”的填数情况,但都对其余单元格不造成除了3和9外的任何删数或出数影响,这样来违背唯一解的说法的。因此结构不允许存在,故r8c13(5)里至少有一个5是格里面应该填的数。

那么,不管哪一个格是5,这两个5就形成了一种类似于区块组的结构,那么,b7和r8其余单元格都不应该有5的出现了,所以,r7c3, r8c7, r9c1 <> 5。

另外,这样的结构称为区块类型类型2UR Type 2),或者第二类唯一性测试Uniqueness Test 2)。

你以为UR就这么简单吗?我们要开始增大讨论的难度了!我们来看另外一则示例。

如左图所示,这个例子里存在一个XY-Wing结构,并且我们通过删数后,存在右图的这种疑似的UR结构。

在删除掉r8c1(4)之后,有一个特别的结构就浮出水面了:在r89c19处,只有一格只有3和9,其它都是3、4、9这三个候选数。如果说,这三个4全部没有的话,剩下的所有3、9就会构成致命形式。所以,r8c9、r9c19之中至少一格是4。不管那个单元格是4,这三个4共同对应到的地方,就不应该是4,而{r8c9, r9c19}(4)共同对应的地方应该为r9c78(4),故结论为r9c8 <> 4。

这个结构罕见之处在于,它不能单独直接存在于盘面之中,而必须通过某个删数之后,才会形成,比如这里的r8c1(4)。虽然看似这个例子跟区块已经无关了,不过它实际上想表示的是类似于区块的“所有区块的候选数不可同时被删除掉”的这一性质,所以这个构型依然被称为区块类型,不过它和区块已经没有什么关系了,只是借用区块这个名字而已。不过,在外国人的命名规范里,这种类型有时候被称为类型5UR Type 5)或第五类唯一性测试Uniqueness Test 5)。

我们再来看一个“类型5”的例子。

如图所示,这个例子里,r7c8(1)和r8c5(1)不可同时被删除掉,否则会形成致命形式,所以至少有一个1是对的,所以删除交集,即r7c4(1)。

Part 2 数组类型(UR Type 3)

这一节,将讲述UR和数组交织的使用逻辑。

2-1 UR+显性数对

如图所示,如果r7c2(6)和r7c3(7)同时从盘面上消失,那么结局是什么呢?结局就是r47c23会形成唯一矩形致命的形式。但是,r7c2(6)和r7c3(7)又不能同时都填进去。如果同时都填进去,即r7c2 = 6的同时r7c3 = 7,这样会明显导致r7c5没有数字可填,这样就违反了数独的填数规则,所以,r7c2(6)和r7c3(7),有且仅有一个数是最终正确的。

然后呢?然后看刚才的r7c5啦。如果r7c2(6)和r7c3(7)只有一个是对的,那不管是6对还是7对,都会和r7c5形成数对结构嘛。有人会说了,数对还能这么用?当然了,同一个区域下,两个格内只有两种不同候选数,不就叫数对嘛。即使r7c2(6)对还是r7c3(7)对,始终都是针对于数字6和7的情况,而恰好,隔壁r7c5这个单元格就需要“接纳”一个关于6和7的单元格来构成数对。不管是只有6或7的其中一个候选数的单元格,还是有6和7两个候选数的单元格,依然是一种“数对”,但数对结构并不确定,只能确定其中一格,另一格则确定不了到底是r7c2还是r7c3,所以我称它为“待定的”数对。那么最后的结论呢,就是r7c8 <> 7了。

这个结构由于带有一个数组(虽然是“待定的”,但是我们也保留了数组的名词,所以这一类嵌套了数组使用的UR类型,称为数组类型类型3UR Type 3),或第三类唯一性测试Uniqueness Test 3)。

实际上这种数组由于最终位置是不固定的,所以这种数组有一个术语称为待定数组Almost Locked Set,简称ALS),不过这里我们不作详细的讨论,因为待定数组可以脱离UR单独使用,而且会非常精彩,所以我们此处将不作出详细的原理说明,仅仅是UR层面够用即可。

接着,我们来看看显性三数组的示例。

2-2 UR+显性三数组

如图所示,我们的思维依然将r46c4两格按照绿色和橙色分成两类。分成两类的好处就是方便和简化讨论的情况总数:

  • 两格都填绿色的候选数;

  • 一格填绿色的候选数,一格填橙色的候选数;

  • 两格都填橙色的候选数。

如果都是绿色的候选数,则UR直接形成致命形式,所以这条直接行不通。

如果两格都填橙色的候选数,可以观察到,c4里涂色仅橙色的单元格目前就有4个了(算上r46c4,因为它们现在只填橙色候选数),而r5c4和r9c4也都只有橙色数字,且只有数字1、2、7。这样一来,c4里存在四个单元格只能放1、2、7三种数字的话,必然就有一格放不了任何数(毕竟只能一个1、一个2、一个7)。所以,这一条也会矛盾。

所以,r46c4里只可能一格是绿色的候选数,而另一个单元格填的是橙色的候选数。这样一来,r59c4两格刚好需要一格与之构成三数组结构,多了不行,少了不够。所以现在就好比产生了一个关于1、2、7的显性三数组了。所以c4除开r4569c4外的其余单元格都不能填入数字1、2、7,把它们都删除。不过这个示例有点不幸的是,只有一个删数r8c4(1)。

我们再来看一个带显性四数组的示例。

2-3 UR+显性四数组

如图所示,依然按照r5c12填入绿色候选数和橙色候选数来分析。中途的逻辑就不讨论了,因为前面的思路和这里是一样的。

发现r5c12必须是一个单元格填入绿色的候选数数值,一个单元格填入的是橙色候选数数值后,就保证了恰好有一个橙色的候选数,随后发现r5c369都只有候选数1、2、6、7,此时形成关于1、2、6、7的四数组(虽然不确定具体r5c1是橙色的数还是r5c2是橙色的数,但保证了r5c12里起码得有一个1、2、6、7的数了,这样就能形成数组)。

于是,我们能删除掉r5里除开r5c12369外的其余单元格的候选数1、2、6、7。

接下来我们来介绍三则带隐性数组的示例。

2-4 UR+隐性数对

如图所示,和刚才的例子推理逻辑基本一致,只是这里得反过来看。如果把r12c6里的1和2看成橙色的候选数,而其它的所有候选数均算作一组的话,那么针对于r12c6而言,依然是三种情况:

  • 两格都是橙色的候选数数值;

  • 一格是橙色的候选数数值;

  • 没有一格填入橙色的候选数数值。

那么就来讨论一下。如果都是橙色的1和2的话,显然它会和r12c2两格形成UR的致命形式(毕竟都只剩1和2了),所以这种情况显然是不可能的。

如果没有一格是1和2,显然也不行。这是因为1和2是两种不同的数,但r1如果没有了r12c2的话,就不再有1和2的合适的位置放下两个数,可以从图上看出,现在c3里只剩下r3c6可以放1或2,而这一个单元格仅能放一个数,所以1和2里总会有一个数放不下到c3上,导致这个数字在c3里无法出现,便产生了矛盾。所以这种情况依然是矛盾的。

所以,还是只得r12c6里一格是橙色的填数1或2。这样一来,r3c6和r12c6的其中一格就形成了1和2的隐性数对,所以r3c6就不能填入1和2以外的其它数字;而r12c6是选取一个单元格填入1或2,而另外一个单元格则是可以填任意情况的,所以这两个单元格是无法确定填数结果的,所以,总的来说,这个例子的删数只有r3c6(34)。

2-5 UR+隐性三数组

如图所示,和刚才的逻辑一样,我们依然讨论r5c23的填数情况。中间的逻辑就不推理了,这里给出结论:r5c23里必须有一个单元格填入的是1或6,而r5只剩下两个单元格,可以放6和9了。这样一来,r5c2368里必然只存在3个单元格能放下1、6、9,而且是恰好放满,不多不少。所以这三个单元格里就不再可能填1、6、9以外的其它候选数了。不过r5c23是确定不了填数1和6的,所以我们只能保证r5c68是放1、6或者9的,所以这个题目能够删除的数字只产生于r5c68里,而且删数必须是非1、6、9的其余候选数。

我们来看最后一个例子。

2-6 UR+隐性四数组

如图所示,这是最后一个例子,也是最复杂的一个例子。我们来看看这个例子到底有何神奇的地方。

首先还是按照r7c89来讨论填数情况,并最终得到r7c89里必须有一个单元格放6或者7,于是,此时发现r7里恰好有四个单元格能放下4、6、7、8。所以r7c89的其中一格和r7c123一并形成4、6、7、8的隐性四数组结构,而r7c123才是能确定填数的情况的,所以删数将从r7c123里产生:删除非4、6、7、8的候选数。

2-7 数组显隐性可互补,那么UR里的数组呢?

既然数组的显隐性互补,那么UR里的数组是否也满足互补的要求呢?实际上,是的,我们随意找出一则示例就可以看出来。

例如上述的隐性四数组的例子,我们看互补的情况,这个时候应当看的是剩余的单元格r7c456,不过和显隐性互补不同的是,此时r7c89依然要看。

在互补后,实际上r7形成的是1、2、3、9的显性四数组,这也是合适的,毕竟r7c7是确定值被占据了一个单元格。

Part 3 共轭对类型(UR Type 4)

3-1 基本推理

我们再来看最后一则UR的类型。思路看起来简单,但有点难理解。

如图所示。可以发现,这个结构里,r4c15是2、7的显性数对,而且,这个例子还有一个现象,虽然不是很能引起注意,不过依然很重要的一个推导条件:r5上数字2只有r5c15两处。这一点很重要,为什么呢?

试想一下,r4c15又只能放2和7,而r5c15里其中一个单元格2,则另外一格就不允许填7。不然的话,四格就只有2和7了,这便形成了致命形式。

3-2 别急,结论还不知道,我们来看看问题

或许你会问,既然我们都填好了数字,就像图上这样,那凭什么能说明它依然形成致命形式呢?毕竟数字填好了就动不了了,怎么还产生两种填法呢?那么我们来看看。

我们假设最终是r5c1是填2的,要是r5c5是7的话,就会产生如下的填数格式:

不过,看似填好了,但客观来说,它确实存在另外一种与之匹配的填数格式:

虽说填好了,但依然可以产生“置换”,原因很简单:因为它们是填入数,而非提示数,数字就能发生变换,毕竟它不固定。这样也算有两种填法。

实际上,官方的解释方式是这样的:即使已经填好一种填法后,因为填数是行、列、宫内成为数对形式的,所以实际上就一定客观存在能与之交换的另外一种填法,这种客观存在的填法不受候选数是否存在的约束。或者换句话说,UR形成两种填数的情况,并不受候选数的约束,只要四格的填数构成a、b、a、b的形式的填法,就必然会产生a和b置换的另外一种填法,哪怕其中一格不存在其候选数a或者b,防止其置换。

所以,置换是客观存在的,并不受到候选数情况的约束。因此,致命形式依然是能够形成的。

3-3 那么,结论呢?

还记得推理的结果吗?r5c15里,因为有一个是2,所以另外一格就不允许是7,否则相当于r5c15形成了2和7的数对结构,而上面也是2和7的数对,将会客观存在两种填法,导致出现致命形式。所以,r5c15的任意一个候选数7都是不允许存在的,也因此,r5c15两处的7都应该被删除。

这个就是我们所谓的共轭对类型类型4了(UR Type 4),也称为第四类唯一性测试Uniqueness Test 4)。

3-4 有一些想说的

这种删除方式更加新奇。它利用了2的填数情况只能位于结构内部的特性,得到了致命形式,从而排除了这么一个假设。这里要介绍一个术语:共轭对Conjugate Pair)。共轭对指的就是这里的这个r5的这俩数字2。

共轭对的定义是:在同一区域下,只有两处可填某一个候选数的单元格下的这两个相同的候选数;或是同一个只有两个候选数的单元格下的这两个不同的候选数。

解释起来有点复杂,说白了就是:因为r5上只有两处可填2的位置r5c15,所以r5c1(2)和r5c5(2)就是共轭对。

共轭对的特征是,两个数有且仅有一个正确。这一点希望你记住,不止是这一节才会用到,后面链以及更靠后的地方,也会使用到这一个特征。

那么,我们再来看另外的使用共轭对的示例类型。

3-5 二链列类型(UR Type 6)

如图所示,可以从示例里看到,所有4的填数位置仅出现于r46c37四格里。那么这样的话,4的位置只可能有如下两种填法:

  • r4c3和r6c7同为4;

  • r6c3和r4c7同为4。

这是不是很像是一个二链列结构呢,因为二链列的最终填法也是交叉的两种情况?我们接着来看。我们发现,结构的左下角和右上角(r6c3和r4c7)两格,都只有4和9两个候选数。如果左上角和右下角(r4c3和r6c7)都同时是4的话,这必然会使得同为4和9两个候选数的两个只可以填入9。这样,就形成了关于4和9的致命形式。虽然已经填入,但因为终归是自己填入的数字,所以依然可以产生4和9的交换写法,这样就跟四格都是4和9两个候选数的唯一矩形致命形式没有本质上的区别了。所以,为了避免致命形式出现,4的位置只可能是另外一种情况:r6c3和r4c7同为4。

这个结构因为运用了二链列的思路,所以被称为二链列的类型;而我们在使用二链列的思路的时候,原理依然是借助了“共轭对”的方式的:如果r4c3 = 4时,则r6c3 <> 4,而r6有4的共轭对,所以r6c7 = 4。反过来也是一样的:如果r6c7 = 4时,则r4c7 <> 4,而r4有4的共轭对,所以r4c3 = 4。所以,它依然归到共轭对里。

这里简单提一下的是,有一些数独分析软件把这种类型归到类型6UR Type 6)或者第六类唯一性测试Uniqueness Test 6)。这一点不受影响,你知道和了解即可。

3-6 隐性唯一矩形(Hidden UR/UR Type 7)

最后来介绍一种利用共轭对的新型技巧,这个技巧还有一个单独的技巧名:隐性唯一矩形Hidden Unique Rectangle)。

首先我们观察到,r1和c3上,都有5的共轭对,而且共轭对涉及的单元格刚好是这个结构涉及的其中三个单元格。那这有什么用处呢?

试想一下,5的共轭对涉及r1c3、r1c7和r3c3这三个单元格,那么就这三格而言,填5只可能有以下两种可能:

  • r3r3 = r1c7 = 5;

  • r1c3 = 5。

如果r3r3和r1c7同为5的话,可以确定的是,r3c7只能填1(因为r3c7只有1和5两个候选数)。那么,r1c3就不能填1了。因为r1c3如果此时还填1的话,r3c7也是1,然后剩余两格又是5,这就构成了1和5的致命形式。之前说过,虽然已经填入了四格,看似已经不能发生变动,但是终归是自己填的,而不是提示数,这样就可以交换四格的填数,并产生客观的另外一种填法,就形成了类似于标准类型致命的形式。所以此时r1c3不应为1。

第二种情况则是r1c3为5。那很明显,r1c3都是5了,那肯定这格就不能填1了。

所以,所有两种情况都能使得r1c3不可以填1,所以r1c3 <> 1,所以可以安全地删除掉这个候选数。

这个结构运用到的是行和列两个“维度”上的同数的共轭对,所以依然是共轭对的类型。而至于分类呢,有些分析软件将其归为类型7UR Type 7)。但是有趣的是,它有个单独的技巧名——隐性唯一矩形,说明这个唯一矩形的位置是隐藏在里面的,不容易看到。

Part 4 其他UR类型

下面给大家陈列一则不属于前面任何一种类型的示例,但和前面的推理思路有很深的关系。

如图所示,这个结构看起来跟UR都没有什么特别大的关系了,不过它依旧能够形成删数,删数就是图中给出的红色的候选数。那么它是如何被删除的呢?我们下面分成两个图为大家呈现出来。

左图给出的是示例里r8c8 = 4时的情况,而右图则给出的是r8c8 = 5的情况。仔细对比两个示例,就可以发现,它实际运用到的是共轭对类型的基本推导思路。

先看左图,当r8c8 = 4的时候,r89c7变为5、8的显性数对结构,而由于r89c5存在c5上关于8的共轭对,所以r89c5里必须要填入一个8,那么由于刚才的填数模式,就可以发现,r89c5里就不能再放入5了,否则r89c57将会构成关于5、8的唯一矩形的致命形式,所以此时应当删除掉的是r89c5(5)。当然,由于r8c8 = 4的关系,此时r8c5根据排除的规则,肯定也可以去掉r8c5(4)。

再看右图。当r8c8 = 5的时候,r89c7变为4、8的显性数对结构,而由于r89c5此时还是存在关于8的共轭对,所以r89c5里必须有一个8的出现,而另外一个则不能是4,否则r89c57将会形成关于4、8的唯一矩形的致命形式,所以此时应当删除r89c5(4);当然了,由于排除的关系,r8c5此时也不能填入5。

所以,可以对比两种情况就可以发现,结论可以删除的数字里,r8c5(45)是同时都可以被去掉的,所以r8c5 <> 45是这个推导过程的结论。

这个示例非常有趣的地方在于,它在推导过程里完美诠释了共轭对类型的唯一矩形结构的推理过程,但它又不同于这个类型,因为结构并不是这样简单清晰的样子。


技巧信息

  • 区块类型类型2):难度4.6。

  • 区块类型类型5):难度4.6。

  • 数组类型类型3):难度4.6+数组规格*0.1+(是显性?0:0.1)。

  • 共轭对类型类型4):难度4.6。

  • 二链列类型类型6):难度4.8。

  • 隐性唯一矩形类型7):难度4.8。

“*”是乘号,“a?b:c”是条件计算,a条件成立的时候取b,否则取c。为了简写才放到一行上的。

名词解释

  • 待定数组Almost Locked Set,简称ALS):数组不是真正成立的,它有点类似于“退化了的”数组,但是,它和普通的数组不同,待定数组的规格总是比它涉及的数字种类数要少一个。比如4个格子里一共有5种不同的数字,那么这个结构就可以叫待定数组。这段内容已经超纲,但不得不在这里说。

  • 共轭对Conjugate Pair,简称CP):当某一个行/列/宫(即区域)里,有且仅有两处可以放数字a的位置,那么我们把这两个a叫做一组共轭对。

第 17 讲:UR 的变体的评论 (共 条)

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