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

第 55 讲:宫内鱼以及鱼的理论

2021-09-07 08:07 作者:SunnieShine  | 我要投稿

在前面的基础部分里我们介绍了鱼的基本使用和定义,不过可以看到的是,这种例子结构非常大,导致可能出现的频率不高,所以不怎么实用;其次是结构不好推理,虽说它和数组是同构的,性质和数组完全一致,除了表达上不一致以外。

这一个部分我们将为你介绍的是鱼的完整体系,这个体系将鱼的内容完整地推广到任意同数情况,所以我们经常可以听到一些小伙伴的评价:“鱼 = 所有同数技巧”。

不过在进入正文之前,我们需要先介绍一下后续经常用到的鱼的基本定义以及鱼的删数原则,在介绍完毕之后,我们才会正式地进入鱼的篇章。

Part 1 鱼的原理

首先,我们再次回顾一下鱼的一些常见术语词汇。

  • 定义域(或基准域,Defining Set或Base Set):定义鱼结构推导的区域集合。

  • 删除域(或删数域覆盖域,Secondary Set或Cover Set):可以提供删除鱼结构的区域的集合。

那么,我们可以这么去思考一个鱼结构的删数逻辑,例如下图。

如图所示,我们回顾一下之前的推导逻辑,我们可以发现,r368这三行的4的填数恰在同样的三列里,这使得我们无论如何放置数字4的位置,但由于r368里每一行都必须放一个4的缘故,使得三行肯定会放下三处4,但它们被框在同样的c567三列里,所以恰好我们安放4的位置就只能是在c567的不同行列的三处,但也都肯定可以保证,c567里,每一列都会出现一个4在r368c567的其中三个单元格里。

所以,c567既然可以保证每一列都会有4在r368c567里,使得其余位置都不能放4,所以可以删除其余位置的4。

可以从刚才的示例的逻辑里精简出来,定义域的每一个区域必须保证填数“必须填入一个”;而删除域则保证的是“最多有一处可填入”

定义域保证,每一个区域都必须有一个单元格可以放这个数字,显然是成立的。因为结构里只有这些位置可以放下它们,所以不填就必然会导致出错;而删除域的保证却不太好说明。你可以当作这是删除域的规定:删除域必须要求每一个区域都最多有一个单元格放这个数字,就可以了。

再来回顾这个例子,定义域r368即保证r3、r6和r8每一个区域都必须放下一个4在r3c567、r6c567和r8c567里;删除域c567则保证c5、c6和c7每一个区域最多都只有一个4要填入到r368c5、r368c6和r368c7里。相信你应该能够明白这一点了。

现在我们来说说鱼的删数原理和机制。

显然,我们找到了三处删除域和三处定义域。鱼要求,如果鱼的定义域和删除域的区域数相等,并且删除域给定的所有区域都能够完整包含到定义域能放下数字的所有位置的话,那么删除域的非涉及单元格都可以删除。这句话有些绕,我们来理解一下这句话的逻辑。

我们先找到定义域区域的所有涉及单元格(r368c567),而删除域c567恰好能够包含r368c567的所有单元格,并且定义域区域数和删除域区域数相同(都是3个区域),此时删除域上非r368c567的其余单元格的4都可以删除。

那么,鱼的整体内容就讲到这里。我们现在来看鱼的正文内容。

Part 2 宫内鱼

2-1 宫内鱼的形成

由于结构的特殊性,我们先从三链列开始谈起现在我们要讲到的内容。

首先,我们先使用三链列来进行结构的变换。先介绍一下,这个图就是我们之前所谓的鱼图结构,斜杠表示当前单元格不能填入某一种候选数,而x表示当前位置可以填入这种候选数。

我们移动其中一列,使得和右侧的一列拼起来,所以结构变为右图这样。当然,逻辑还是原本的三链列的逻辑。

现在,我们开始变换结构的形状。我们现在尝试把其中的r2变换到b3里,这一点很奇怪,但也很特殊。变换后,结果变为下图这样。

如图所示。如果结构变为这样,还能推理和执行删数逻辑吗?我们尝试使用之前我们得到的逻辑进行解释。首先,定义域区域数量为3:r58b3,这保证了这三个区域必须填入三个x到里面去;而删除域是我们规定的,也恰好是三个区域,而这三个区域都完全恰好包括了所有我们原本定义域里圈出来的所有x。我们知道,从理论上可以明白一点,既然删除域能完整容纳下定义域原本所有的候选数x,而且定义域区域数和删除域区域数一样,那不论怎么放置这些x的位置,由于不能违背数独规则,即行列宫内不含重复数字,那么x的位置还要在每一个定义域里恰好放一个,那显然每一个删除域里,就也必须每一个区域都含有一个x。否则,候选数x必定会在某一个定义域区域里出现两次。毕竟我们只能填入这么多x,如果少一个删除域区域不出现x,那就必然会让定义域区域多一个位置填x,而定义域区域数只有那么多,所以多余的填数位置必然就会挤到同一个区域里,导致违背数独规则。所以这个结构的删数,删除域的每一个区域的其余位置(涂色单元格并不含任何符号的位置)就是删数的区域了。

从理论上听起来很空泛,所以我们针对于实际情况来对这个结构作出分析。首先,我们先来按照特殊的定义域区域b3来讨论填数,我们把它划分为r123c7(x)和r123c8(x)两部分。首先,如果r123c7里有一个单元格填x,则由于r123c7(x)区块的影响,此时在r58里必然会产生一个二链列结构在r58c28。r58c28显然是可以被删除c28的,因为此时它是一个完美的二链列结构。而由于假设r123c7(x)区块的成立,此时c7是可以由于这个区块得到x的删数的,所以我们还可以把c7算上,所以删除域是c278;接着,如果假设r123c8(x)区块成立,则下面的r58依然会产生一个完美的二链列结构,删除域此时是c27,但由于r123c8(x)区块的成立,所以c8其余位置也是不能放下x的,所以我们把c8也算上,整体的结构删除的地方还是c278。

所以,两种情况肯定会至少有一种是对的,但它们都可以删除c278的其余位置的x,所以我们完全可以认为,这个结构整体是可以删除c278其余位置的x的,或者换句话说,把它看作一种新的鱼结构,而定义域是r58b3,删除域则是c278。

我们把这种定义域区域里同时包含行宫或列宫组合的,或者是删除域区域里同时包含行宫或列宫组合的鱼结构称为宫内鱼(或宫内链列,Franken Fish)。比如这个例子里,定义域含有r58b3,是同时含有行和宫两种区域类型的,所以称为宫内鱼。

2-2 原理进一步剖析

因为宫内鱼的结构有一些奇怪,而且会有区域被压缩到宫内,所以讨论起来就会有一些地方比较麻烦。所以我们进一步来分析这种结构到底可以如何变换。

2-2-1 宫内鱼的残缺情况

如图所示,这个结构是否是一个正确的宫内鱼结构呢?答案是肯定的。从理论的角度来说,删除掉原本宫内鱼完整版的一部分候选数是不影响鱼的使用的,即使它们会变得各种奇形怪状,这是因为,删除的部分并不会影响到定义域区域数和删除域区域数相同的这一个特征。而我们之前从理论上和实际上都详细阐述到了“只要它们的数量相同,并且删除域区域包含所有定义域区域里圈出来的所有候选数x,就一定是可以删数的”这一个看起来似乎很棒也很神奇的结论。

而从实际上来说,想要说明这一点也很简单,我们依然通过b3来分情况讨论。只是这一次,b3结构变得更简单了,这使得b3本身该有的两个区块都直接变为了两个单独的候选数。但实际上,它们的排除效果是不受影响的,所以实际上删数依然可以得到保证。

之前,我们学到过了退化鱼结构,这种鱼结构甚至只能依赖于鳍才能存在。我们先不考虑鱼鳍的事情,我们尝试在这个残缺得看似无法再残缺的结构再删除一些x。如果r5c7(x)和r8c8(x)此时也一并消失的话,如果看这个结构,实际上是可以存在的,只是巧妙的是,此时的每一个区域都仅剩下了两处可以填入x的位置,所以这样它们是可以构成一个环结构的,删数也就恰好是删除域所在的这三个区域。

2-2-2 宫内二链列?

如左图所示,结构是这样的,我们尝试把结构的x移动到r28c78里,然后把r2转换到b3内,就可以变为右图这样。

但实际上,在中途的转换时就可以发现,它已经变为了一个级联区块结构,所以宫内二链列实际上已经脱离了实际的应用,所以它只存在于理论之中。

当然,我们继续观察右图,即使变为了真正的宫内二链列,也会发现,实际上它等效于c9和r8的两个关于x的区块结构,删数是都可以删掉的,因此依然不存在于实际的运用里。当然,实际上它也可以像是一般的宫内鱼那样,变为残缺的情况,比如下面这样。

那么它是环,是宫内二链列,还是级联区块呢?这就你自己来分析它了。

2-2-3 宫内四链列的结构

实际上,四链列因为比三链列更大,所以肯定会存在宫内的版本。但是宫内四链列比较特殊的地方在于,它具有四个定义域区域,这样就可以有更多的区域转变到宫内,例如我们可以把一个行改为宫,或者同时把两个行改为宫,例如下面的这两种不同的情况。

至于如何推理变为这样,我就不再过多阐述了。

2-2-4 定义域能重叠吗?

我们还有一种构型依然可能出现在盘面里。由于宫内鱼的结构有宫的区域,这就导致了可能出现行或宫重叠的现象。

如图所示,这个结构就是我刚才说的重叠的情况。显然,这种结构里把原本b3的宫移动到了b6,但是其它的并未发生变化。

可是,仔细观察就可以发现,r5已经产生了出数的结论,所以这样的结构在三阶的情况下只有理论上是存在的。另外,这里也会产生一个问题。如果区域重叠了,那么r5c78如果也含有x,那应该怎么考虑逻辑呢?毕竟当r5c78其一填入x后,这将同时使得两个定义域区域同时拥有填数,而我们却只填入了一个数就满足了两个定义域区域的要求。这种现象,我们将在后面的内容讨论到,我们大可直接将这个重叠的部分(即这里的r5c78)视为“不能放候选数x”,即图上画的“/”符号。

从理论上说明,我们可以发现,此处的结构依然存在三个定义域区域和删除域区域,也确实满足删除域区域全部覆盖了所有定义域里的x。那么这就保证了,x在定义域里只能放3个,而且还要想行列宫不产生违背数独规则的情况,那么只能在每一个删除域区域上也都保证一个x的出现,而这一点内容已经在前文叙述过,这里就不作出说明了。

可以类比一下这个情况,我们将结构提升到四阶,看看宫内四链列是否存在重叠区域的现象。实际上,宫内四链列确实存在重叠的现象。例如下面的这种情况。

如图所示,这种结构就是典型成立的,首先定义域区域r6和b6有重叠部分,而重叠部分我们目前要求的是不能有x。而这样一来,就不存在之前重叠区域里产生的“填入一个x同时满足两个区域”的特殊情况,就不必过多去探讨。并且这样放置的话,定义域区域保证要放下4个x,删除域区域也是4个,这样就满足了删数的原理,所以删除域依然是可以成立的。

不过,这个示例如果从假设层面,就显得很麻烦了,而理论是可以保证正确性的,所以我们就不再探讨它的实际推导为何正确了。

2-2-5 什么?鱼也可以转置?

别着急,在进入示例讲解之前还要看一种情况。

仔细观察两个鱼图,可以发现它们涉及的单元格都是一样的,但第一个的定义域变为了第二个的删除域,而第一个的删除域就变为了第二个的定义域。那么,变换到后面的这个情况,那么它是否成立,并且删数可以正常删除呢?

实际上,这种结构依然是可以的。从理论上说明,这样的行为并没有引起定义域区域数和删除域区域数的改变,也没有引起“全覆盖”要求的改变,所以删数依旧是成立的;而从实际逻辑推理上来理解,你可以考虑随意放置x,最后必然在c278里每一列都能找到一处x的放置,分属于r58b3的每一个区域。

将定义域和删除域交换的行为,在鱼结构里称为转置(Transpose)。当然,这只在理论上才会出现,在实际解题的结构之中,结构是无法转置的,它只有互补,这一点我们在后面的内容会作出详细的说明。

实际上,这种结构依然叫做宫内鱼,因为在宫内鱼的定义里保证了,定义域或者删除域的其中一个定义里出现行宫和列宫组合就满足了要求。这就是为什么,宫内鱼的定义必须说明必须定义域或删除域的其一,而并不是单纯只有定义域的原因。

那么,讲到了这么多的构型,现在我们来看一些示例。

2-3 一些宫内鱼的示例

现在我们来看一些有关宫内鱼技巧的例子,来熟悉一下宫内鱼的使用。

2-3-1 宫内三链列

下面来看若干宫内三链列(Franken Swordfish)技巧的例子。

如图所示,可以看到这个结构的定义域是r34b9,删除域是c489。显然,定义域区域数和删除域区域数一样多,而且删除域全部包含了定义域里的所有1。这样一来,放下1的位置不论怎么安排,每一个删除域区域都能保证有一个1的出现。所以所有删除域的其余位置的1都可以被删除。

接下来是第二则示例。这个结构的定义域为r19b5,删除域则是c469。和刚才一样,定义域区域和删除域区域数一样多,都是3,而且删除域区域完全覆盖了所有定义域涉及的6,所以删除域的每一个其余位置的6都可以删除。

如图所示,我想让你来理解这两个示例。这两则示例的逻辑和上两个示例的逻辑是完全一样的,所以我并不需要阐述什么东西,靠你自己了!

2-3-2 转置的宫内三链列

接着来看一则利用基本构型转置了的结构。

如图所示,这个鱼结构的定义域是r689,而删除域是c15b9。

2-3-3 宫内四链列

宫内三链列已经够难找了,宫内四链列(Franken Jellyfish)的例子就更难找到了,不过实际上它还是广泛存在于题目里的,所以这里给出了一些情况。

如图所示,这就是一个宫内四链列的示例。可以看到,这个结构的构型非常类似于之前说到的四阶情况的重叠构型。显然,这个结构此时是成立的,定义域区域和删除域区域一样多,都是4个,而且也满足了“全覆盖”的要求;并且,r6和b6重叠的单元格上也都没有影响填数的额外的候选数6,所以结构是成立的。

如图所示,这是另外一则示例,它和上一个示例不同,它没有重叠,所以直接不用考虑重叠的那个额外条件。删数是完全成立的,这里就不再过多说明了。

那么,我们再给出四则示例,不过得你自己来思考了。不过它们的构型都差不多。

如图所示,这些示例都是之前我们提到过的构型。所以逻辑我们就完全不用再去说明它了。第一个和第二个都是重叠的情况,第三个是原结构的转置的情况,第四个则是带有两个宫的定义域的宫内四链列结构。

那么,有没有更高阶的宫内鱼结构呢?由于结构的特殊性,它的互补并不像之前数组和标准鱼构型那样,规格会发生变化,所以,它是可能出现五链列以及更高的情况的,不过例子就不好找了,所以这里就不再列举了,后面将会广泛出现这种情况的示例。


第 55 讲:宫内鱼以及鱼的理论的评论 (共 条)

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