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

第 67 讲:网的基本概念

2021-10-26 09:04 作者:SunnieShine  | 我要投稿

欢迎进入本文档里的最难的一部分:(Multi-sector Locked Set,简称MSLS)。

Part 1 我们从SDC说起

先来看看SDC基础版是什么样的。

1-1 度SDC

我们可以从之前的SDC的讲解里看到,SDC是一种由两个区域构成的整体跨区的数组结构。那么SDC能否拓展到涉及更多个区域呢?

如图所示,我们观察这个结构,它涉及了三个区域:r5、c8和b6,一共涉及r5c289、r24c8和r4c9这六个单元格和六种不同的候选数4、5、6、7、8、9。

首先我们对这样六个单元格按照所属区域涂上颜色:我们发现六格之中,4和5只出现于同一列上,所以我们暂用绿色标注;6和8只出现于同一行上,所以我们暂用橙色标注;7和9则只出现于宫内,所以图上紫色。

此时我们会发现,六格有六种不同的候选数,并且每一种候选数都不会跨区域出现。所以,我们可以这样思考这个问题:结构在b5内,有多个涂色的单元格一共有三个:r4c8和r5c89。因为上方的r2c8只有候选数4和5,所以还需要一格,候选数也只有4和5,才可以不出现矛盾(如果三格只有4和5则无法填满三格;如果只有一格有4和5,则4和5在c8上总有其中一格数不会出现,于是矛盾)。于是r45c8其中一格只能有候选数4和5;同理,r5c2因为只有候选数6和8,所以需要且仅需要一格只有候选数6和8,才不会出现矛盾。所以r5c89其中一格只能有候选数6和8。再观察b6,结构涉及于b6内还有一格只有候选数7和9,那么还需要且仅需要一格只有7和9才不会出现矛盾。

这样一来,r4c8和r5c89这三格有一格只有7和9、有一格只有6和8、有一格只有4和5。这样刚好用完这三格,所以这样看来,c8总会出现45数对、r5总会出现68数对、b6总会出现79数对,于是删除c8、r5、b6其余位置各自出现的数对而得到的删数,图中红色的均为删数。

这样的结构就是SDC的拓展,把原本涉及的两个区域变为涉及了三个区域,所以称为三区域分布式跨区数组(Three-sector DDS),另也可以直接叫作二度SDC(SDC Degree 2)。注意,结构涉及n个区域,则称为“(n-1)度SDC”。最基本的SDC也可以被称为一度SDC(SDC Degree 1),千万不要搞错了名字。

可以看到,这样的结构最多只能到达二度,因为盘面只可能出现行、列、宫三种区域类型,所以不可能出现第四个维度,使得结构变为三度的。

1-2 段SDC/多米诺链

除了这样从涉及区域来拓展结构的,还可以直接将推导情况接起来形成链条形式。

如图所示,我们从r5c468起推。r5c46其中一格只能有6和8,和r5c8(68)构成68数对(r5c46都没有6和8和都只有6和8都是矛盾的,这一点和上面的思路是一致的,这里就不阐述了)。因为r5c46其中一格只有6和8,所以另一格就不会有6和8、只有4和5。此时r46c5其中一格也只能有4和5,构成45数对;而r46c5其中一格只有4和5,所以另外一格则只有6和7,此时和r7c5形成67数对。所以推导过程可以得到r5形成68数对、b5形成45数对、c5形成67数对,于是其余单元格对应数对的删数就都可以删除了。

这个结构和刚才的结构不太一样的地方是,多度SDC(多区域分布式跨区数组)是“发散形”的,而这个结构则是“链条形”的。所以这个结构也可以看作多段不同的待定数组共同构成的结构,并称为多段SDC多米诺链(Domino Chain),是不是很像多米诺骨牌那样一个一个顺次倒下的感觉呢?另外,上图由三段构成,所以是三段SDC

如图所示,c7之中有两格只有候选数4、8、9,则还需要一个单元格只有候选数4、8、9才不会出现矛盾;发现r45c7其一是4、8、9就可以,于是r45c7另外一格只有候选数2和5,于是还需要恰好一格只有候选数2和5才不会出现矛盾,此时发现r6c89其中一格只有2和5就可以,于是另外一格则只有候选数6和8,此时需要r6c23其中一格只有候选数6和8才不会矛盾;r6c23其中一格只有候选数6和8,所以另外一格则只有候选数2、4、5,于是和b4内只有候选数2、4、5、7的r4c1、r5c13三格共同构成2457四数组。

所以总的来说,c7总会出现489三数组、b6总会出现25数对、r6总会出现68数对、b4总会出现2457四数组。所以各自对应的区域下的数组的删数就都可以删除掉了。

这个结构在推导时被分为四个部分,所以称为四段SDC。

那么,这里再来一个练习,请自行观察。这个结构有些复杂——六段SDC。

大致的推导过程是从r3、b2、c5、b8、r7、b7的顺序推导的哦!就提示到这里了!当然了,从推导过程之中,你也可以发现,多段SDC的推导是不论方向的,所以倒着推导也是可以的。

它非常像是链,但和链不同的是,链如果不首尾拼接形成环的话,是无法删除那么多数字的,而多段SDC虽然很像是链的形式顺次推导,但是它在不封闭的情况下也是可以删除很多数字的哦。那么,多段SDC封闭起来构成环路会怎么样呢?

1-3 科尔扎斯环/多米诺环

如图所示,我们只看绿色的单元格。我们这么去想,任找一点,比如r2c13,不妨假设其中一格只有候选数68,则r2c79其中一格只有候选数6和8,构成68数对,而另一格则只有1和5,与r13c8构成15数对,另外一格则是68,和r79c8其中一格形成68数对,另外一格则只有29,和r8c79其中一格构成29数对,而r8c79另外一格则只有候选数4和6,则会和r8c13其中一格构成46数对,则另外一格是15,会和r79c2其中一格构成15数对,另外一格则只有候选数6和8,会和r13c2其中一格构成68数对,而另外一格则只有候选数2和9,会和r2c13其中一格构成29数对。而最开始r2c13假设的其中一格是候选数6和8,那另外一格必然肯定只有候选数2和9了。

这样一来就会构成涉及r28c28b1379八个区域的环形八段SDC,且各自区域上恰会构成一个简单的数对。这样的结构是多米诺链的环形版本,所以直接可以成为多米诺环(Domino Loop,简称DL),或称为柯尔扎斯环(SK Loop,简称SK环)。

结构是由一位叫Stephen Kurzhals的人发现的技巧,所以为了纪念他,采用了他的名字直接称呼这样的环,即S.K. Loop。

另外,我们可以对这样的多段SDC的推导过程利用数学符号的方式简写,而不是用上面复杂的文本描述。

另外,多米诺环还有一个示例。

它的表述如下。

Part 2 MSLS的定义和使用

我们正式进入网的学习。不过首先,我要拿出一个大家基本上都熟悉的例子:被网上“戏称为”世界最难题的数独题目。

2-1 MSLS的定义

这个题把它的全部候选数都标注上去的话,就是这样的,不过这个题目,在前面学习到的技巧之中,是无法解决掉的,也包括飞鱼导弹(或者我自己没找到)。

不卖关子了,接下来我们直接来看这个例子用什么网怎么操作。

首先我们标记出来一系列单元格,如下图所示。

这样我们就标注了20个单元格。我们之前学到的SDC的拓展,不论是多段SDC还是多度SDC,最终在结构内的所有候选数,没有任意一个候选数同时属于两个或更多区域。换句话说,之前的所有候选数,都有自己对应的明确的涂色的,而不会同时因为属于两个或更多区域时,同时图上不同的颜色。

这里我们来看这20个单元格的所有候选数,这些候选数能不能像之前那些SDC那样,每一个候选数都可以明确地找到自己所属的区域呢?

好消息是,全部都可以。比如这样:

如图所示,标注在盘面外的数字,表示所在行(列)上,一定存在于此区域的候选数。比如说r1外围的1、3、6,表示这一行内,结构涉及的单元格内,候选数1、3、6恰只属于此行内。

那怎么去选择每一个候选数的所在区域呢?比如r1c5(7),因为行上只有唯一一个单元格可能有7的填数位置,按照SDC拓展版本那样,如果一个区域下只有唯一一处有这个数,就完全无法构成合适的结构。所以这样看是不行的,换而言之,只能将候选数安排到列上。

然后,数一下外围的数字的个数。结构涉及五行,一共是3 + 2 + 2 + 1 + 2 = 10个数;又涉及四列,一共是2 + 3 + 3 + 2 = 10个数,所以结构整体一共涉及的是20个数。而恰好又是20个单元格。我们就可以下结论:这些外围的数字表示所在行(列)上,一定会出现这些数字。所以所在行(列)上,可以对应删除掉其他位置的候选数。如图所示,红色的均为删数。

结论是成立的,而且红色的删数是可以保证正确性的,我们可以安全删除掉它们。比如刚才我们确定了r8上有3和6,所以r8结构涉及的区域单元格的候选数3和6均可以被删除。

那,又是为什么可以这么确定删数呢?外围的数字又是个什么意思呢?

2-2 MSLS的原理

下面我们用简单的几句话阐述一下它到底为什么成立。

我们利用鱼的删数原理思路可以进一步地推广,换句话说,鱼只会涉及行、列、宫,因为鱼只能是同数的;而网涉及不同数字,所以还会比鱼多出一种衡量区域:单元格。

我们这么去想这个问题。我们尝试把外围的数字看作“广义的删除域”,而把单元格看作“广义的定义域”。定义域意味着,每一个定义域下只可能有且仅有唯一一个正确的数;删除域意味着,每一个删除域下最多都只能有一个正确的数。那么20个单元格都被看作定义域的话,就有20个定义域,即恰有20个数字正确;而我们把外围的数字,挨个在所在区域上算作对应的删除域区域的话,也会有20个删除域。删除域下数字最多只有一个正确的,比如说,我们把r1上涉及的三个删除域区域r1(1)、r1(3)和r1(6)都写出来,这就表示r1上最多只有一个位置是1、最多一个位置是3、最多一个位置是6。

而20个删除域区域就意味着,最多有20个数填入结构之中,而定义域保证,结构恰有20个数。所以这么一来,就没有多出来的数了。换句话说,这些数最终都是全部会填入到结构之中的。所以,删除域下的数字(所在区域的其余候选数)均可删除。

这下知道为什么网的英文名的直译是“多区域(跨区)数组”了吧。因为它的结构不同于SDC的拓展,

另外再提及一些术语。

  • 定义单元格(简称定义格,Defining Cells):即结构涉及的单元格,每一个单元格都称为一个定义格。即定义网结构的单元格。也称为网定义域(Defining Sets For MSLS)。

  • 链接点(Link):比如上述示例之中,标注在盘面外的数字。位于行上的,称为行链接点(Row Link),位于列上的,称为列链接点(Column Link),当然也存在宫链接点(Block Link)。

  • 网定义域(Defining Sets For MSLS):同定义格。

  • 网删除域(Secondary Sets For MSLS):链接点所在的所有区域,称为网删除域。

2-3 小练习

下面我将会给出一个题目,这个题目里存在一共3个不完全相同的网结构(当然网结构的位置不同,删数就不一定完全一致了)。我会给出其中的一个网,并且给出对应的删数在那里,以及所有提供提示的涂色信息,而剩下的两个网里,一个我只给出删数和定义单元格的位置,但不给出链接点的分配情况的涂色信息;而还有一个仅仅给出定义单元格的位置,不给出涂色信息和删数,希望你能够独立通过前文的描述完成推理。

这是第一个网结构,看起来好像要补充r1c1才能算是完整的4 * 5的结构,但这个例子里由于r1c1被提示数9占据了,所以不能算上它,而剩下的部分恰好满足19个单元格和19个链接点的分配,而且同样满足了全覆盖的要求,所以网是成立的。

这个网的示例里只有16个单元格,但依旧构成了网,希望你能找到链接点的情况。

最后是同样这个题目的第三个网结构。

那么,下一节我们将继续讲解,网结构的复杂变体类型。


第 67 讲:网的基本概念的评论 (共 条)

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