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

第 61 讲:不饱和鱼

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

接下来将为你介绍的是最后一种鱼结构,之所以放在最后讲,是因为这种结构难度非常大,而且有一些基本定式无法满足,所以删数的方式和原理有一些别扭。

试想一下,我们之前学到的鱼结构,定义域区域数和删除域区域数是相同的,即一样多的,这种结构我们完全可以拿着它就可以用来删数,因为毕竟这种结构删数的原理已经通过理论严格证明了,只要满足全覆盖和区域数一致的要求,就可以删数。那么,有没有可能让定义域区域数比删除域区域数多,或者删除域区域数比定义域区域数多,但依旧全覆盖的情况呢?那么如果有,又应该如何删数呢?本节就会讨论全覆盖要求下,定义域区域数和删除域区域数不一样多的时候的删数情况。这种鱼结构称为不饱和鱼(Unsaturated Fish)。

Part 1 不饱和鱼的形成和原理

在进入正文技巧内容的学习之前,我们先要掌握一个理论概念——(Rank)。这个词汇实际上来自于线性代数里的矩阵的秩。这个词被套用到鱼结构里,又有什么特殊的用法和用途呢?

1-1 秩的概念

我们在之前的内容里,提到过一个情况:自噬。在自噬的内容里,我们说到过,当鱼的定义域和删除域区域总数相同,而且还全覆盖的时候,鱼是可以删数的;而如果鱼的某一部分位于两个删除域区域的交集上,而位于一个定义域区域的交集的话,假设它填入后,它会同时使得两个删除域区域消失,一个定义域区域消失,致使定义域区域数少于删除域区域数,这样的话,填数就不再平衡了,因为定义域必须保证放入(n - 1)个数,而删除域却必须保证最多放(n - 2)个数。这个最多放入的总个数竟然比必须放入的总个数还要少,所以出现了矛盾。

那么我们尝试把这种说法包装一下。我们使用删除域区域总数减去定义域区域总数,减下来的这个差值称为鱼结构的秩。那么上述内容就变为这样:当某个结构满足全覆盖要求,而且秩为0的时候,鱼就可以删数了;而如果某一处位置填入后导致秩为-1((n - 2) - (n - 1) = -1)的时候,出现矛盾。

这便就是秩的一个基本的叙述模式。可以看到,有了这个说法之后,前面的说辞就会简化一些了。

1-2 所以,前文都是在讲秩为0的鱼?

是的,前文介绍的内容都是秩为0的鱼结构,因为删除域区域数和定义域区域数是相同的,所以减下来的差值必然为0。

但请注意,前文所说的是“区域数相同,则秩为0”,而秩为0的结构不代表一定能在所有删除域进行删数。我们之前发现的所有秩为0的鱼结构是可以删数的,这是因为结构涉及了全覆盖,且每一个候选数都只被使用过一次,但有些时候,某个(或某些)候选数将会被重复使用,此时的分析将会更复杂一些,而这一点在后续的一些例题里会出现。

1-3 那么,秩可以为负数吗?

可以从刚才的说法里看到,一个结构是不允许秩为负数的,哪怕刚才说到的-1,也是不允许的;比如秩为-2则表示的是定义域区域数只有(n - 1)个,但是删除域区域数却只有(n - 3)个。定义域保证结构还必须填入(n - 1)个x,但删除域保证最多还只能放(n - 3)个x。显然,只要后面这个数值(即最多能放置的个数)如果比前面这个数(即必须放置的)要小,不管小多少,就一定会矛盾。因为我们无法达成这里给出的要求。

那么用秩的说法就是,一个鱼结构的秩必须大于或等于0才有效,即使无法删数,或者其它原因没有删数,但起码不会像是秩为负数那样立刻矛盾。

1-4 好了,秩可以怎么用呢?

所以,我们可以基于这一点,产生一些有关秩这个理论的一些基础用法。我们把鱼作一个推广。之前我们要求的鱼的定义域区域数要必须等于删除域区域数,是为了保证鱼内部的所有删除域都是有效的。但如果我们没有必要删除那么多,或者目的并非是找这种删数多的鱼的时候,或者甚至是根本找不到删数多的鱼结构的时候,我们可以试试找找,删除域区域数比定义域区域数多的鱼结构。

当删除域区域数比定义域区域数多,那么这个差值,即鱼的秩一定就会大于0,虽然我们不能得到结论,但是起码它不是负数,就意味着结构是可能成立的,只是删数不知道在哪里罢了。

那么总的来说,不饱和鱼结构的使用方式是这样的。我们如果找到一个结构,经过全覆盖要求后发现删除域区域比定义域区域多,就算找到了不饱和鱼结构。此时只要我们找到某一处位置,假设它填入后,能使得鱼的剩余结构的秩变为负数时,我们就可以认为结构产生矛盾了,故原假设错误,删掉它。

实际上,在有时候不一定能立刻找到秩为负数的矛盾,因为有些时候结构秩看起来为0,实际上并不是真正的0。这些结构都非常麻烦,而且大多数例子直接使用秩来理解都不是很方便,反而还不如通过代入试填来推导矛盾来得快。所以在有些时候,试填和利用同数技巧来获得结构内部的矛盾的过程,称为饱和性测试(Saturation Test)。虽说试填有一些暴力,但依旧通过逻辑层面推导,所以在逻辑层面,我们是可以接受的。下面我们将拿出众多的示例给大家分析。

那么我们尝试使用这个方式来理解一些常见的不饱和鱼结构吧。

Part 2 不饱和鱼的示例

2-1 不饱和四链列

如图所示,我们尝试找到c1389的所有数字6,并寻找新的区域来执行全覆盖要求。可以发现,此时我们找到了r13589b4一共6个区域,才覆盖完所有的数字。一般来说,我们都会去删除域上找删数,所以此时我们对于每一个删除域上的含有候选数6的单元格执行假设操作。

此时发现,假设r5c2 = 6的时候,我们将有下图这样的构型。

如图所示,这样的构型好像看似没有什么问题,因为定义域区域依旧是4个,而删除域区域则变为了4个。虽然变少了,但是删除域区域数依旧和定义域区域数一样多,起码它并非变为秩小于0的情况,即定义域区域比删除域区域数量还多的情况。不过请你注意一个地方。由于我们假设到r5c2 = 6的时候,结构剩下的部分变为了一个看起来很像是四链列的构型。看起来虽然没有什么异样,但请你仔细思考一下,这个结构真的存在吗?我们可以发现到的是,不论你怎么放置这些填数,任取其中三处填入,最终都必然会有一个定义域区域无法填数,这便产生了矛盾。可你会问,这是为什么呢?

我们尝试尽量使用简单的思路来解释。我们可以通过结构找到两条摩天楼结构,且它们共用一个定义域区域作为强关系产生的区域。之所以这么做,是为了后面证明出现矛盾作出铺垫。

我们可以观察图上的两种填数模式,就可以发现,此时已经产生了不对劲。左图的删数和右图的删数能够对应到c9的唯一的两处填数位置,而这两处位置都被删除了。这便使得c9就不能填数了。因为链是同时可以成立的,所以删数也都是同时成立的。而删数导致了c9无法填入6,所以出错。

那么既然错误了,这便就说明了这样的结构不存在,就得到了原本的假设(r5c2 = 6的说法)自然就是错误的了,所以r5c2 <> 6。

可是你会思考,这也只能说明这一个例子才能满足这个要求,而其它的例子不一定。实际上,其它的例子也都符合这种要求,只要我们能形成上述形状的构型的话。由于结构的特殊性,结构只会涉及8个单元格,而且8个单元格分属于四行四列,且两个一组,出现在同一个并排三宫里。这句话有点绕,具体的意思指的是,比如c13这两处定义域区域,它们都处于b147这样并排的三个宫里;同理,c89也是一样。这样一来,我们还有c1389都是共轭对这一个条件,这就使得结构产生了非常多的摩天楼,并且能互相删除自己的某一个端点。当我们给出的链合适时,删除的位置就应当会排除掉同一个定义域区域下的所有情况,使得结构出错。

可能你还是有问题的地方在于,定义域区域数和删除域区域数此时是一致的,那么秩为0,根据理论,秩为0的结构是可以直接把删除域区域的所有位置都看作删数的地方来删数的,可这个例子怎么就不行了呢。实际上,我们在论证摩天楼存在和删数的时候,用到了过多的定义域区域来论证:首先,我们用到了四个定义域区域,是结构本身存在的;而b13是隐藏的,因为b13在6排除了r1389c2(6)的删数。所以,定义域区域比删除域区域数还多2个,所以秩为-2,导致矛盾的出现,而b13实际上我们在结构论证矛盾(就是刚才摩天楼技巧的互相删数那里)是用到了它的,要不你自己独立想一想?

接下来我们再来看一则不饱和四链列的示例。

如图所示,这个结构看起来比较简单,但删数很“离奇”:不饱和鱼按道理是通过假设得到的删数结论,而这个例子却巧合地删除了四个数字之多。下面我们就来挨个进行分析和讨论。

假如r6c2 = 7,则c2和b4两个删除域区域就会由于填数假设而直接被去掉,但这个假设并不会影响到任何定义域区域(当然,b7此时可以出数,但是我们考虑通过秩的逻辑来说明,所以这里我们不继续往下假设)。

显然,定义域区域数依旧是4个,但删除域区域数变为了3个(原本有5个,但c2和b4消失,所以只剩下3个)。但是,此时删除域区域数比定义域区域数还少,秩为-1。我们说过,秩为负的时候,结构出错,所以这个结构便产生了矛盾。故r6c2 <> 7。

而其余三个删数,是通过普通鱼的视角得到的,这一点其实在之前的例子里已经说明了它们的删数缘由。

如图所示。如果我们把定义域区域b6的视角改变到r4的话,定义域就和不饱和鱼所给的定义域完全一样了。

当然了,至于为什么可以这么切换视角,你可以尝试自己论证这一点,你可以通过秩在切换视角后依旧不产生变化这一点来论证它。

我们再来看一则示例,这一则示例则更像是第一例里那样的删数逻辑样式。

如图所示,细数定义域区域和删除域区域,定义域区域一共4个,分别是b2356;而删除域区域则是r23456,一共5个区域。如果r5c23(3)其中有一个为真,都会使得结构只剩下{r2c57, r3c69, r4c59, r6c67}(3),不论如何填入3,都会出现错误。因为原本r789c5679都是不含有候选数3的,这使得3只能放在上面的单元格里;而由于r5c23(3)其一成立的关系,使得3的位置变为类似于之前第一则示例的样子,导致无法填数。当然,通过秩来解释就是,结构涉及的定义域和删除域个数发生了变化,导致差值为负数,出现了矛盾。

当然,这个题更为简单的理解方式就是转化为之前看到过的一定矛盾的构型:我们尝试把b2356的定义域改变为c5679,就会发现,实际上结构就变为了之前那样的矛盾的构型,你可以自己试试看。

2-2 不饱和五链列

如左图所示,我们需要找到r345689b1一共7个删除域区域才能实现全覆盖。所以此时的鱼的秩为7 - 5 = 2。假设r3c1 = 8,则结构将会消失两个删除域区域b1和r3,而定义域区域不会消失。

似乎看起来秩变为0了。实则不然。它同时还影响着b47两个宫,使得在b47里填入8的位置分别只能在{r4c3, r56c2}和{r8c3, r9c2}里。那么,这样一来,仔细观察c45填入8的地方,就可以发现,不论b6里填入8的位置在哪里,左侧c23和c45填8的位置都能形成和之前示例完全一样的构型,而这种构型在之前都已经讲得比较清楚了,所以这种结构不用再去推导,就知道它一定是错误的。所以,原假设错误。

我们再来看一些这样的示例。

如图所示,这个结构看起来好像秩为0,对吧。实际上你可以看到,如果照着结构给出的样子的话,r1c4(6)和r9c6(6)是无法覆盖到的。所以,这个结构的删除域实际上是r34678b28,一共7个删除域区域。

我们尝试对两个删数逐个进行讨论。假设r7c8(6)为真,则会如何呢?

我们画出这样的一个推导过程。注意着不是链,所以没有用实线虚线表达强弱关系。显然,这样画出来后,打勾的就是我们假设填入的地方,打叉的则是不能填入的地方。那么我们再次针对剩余的部分执行推导。

结构因为填入了r6c9(6),所以少了一个定义域区域,而删除域区域少了几个呢?r6是肯定会消失的,而原假设r7c8(6)使得r7删除域区域消失,所以少了两个。现在依然没有矛盾,我们还得继续去发现。

接着我们观察左图,图中有一个在c34上的摩天楼,于是得到r3c56 <> 6的结果,此时观察c5,发现6有出数,于是变为右图的状况。此时就可以发现,c6无法填入数字6,出现错误。所以,原本的假设r7c8(6)是错误的,应当删除掉。

别急,这个示例还有一个r8c1(6)的删数我们还没有说明。

如图所示,似乎设定r8c1(6)为真,更难分析得到结论。是的,确实它比较复杂,因为我们假设到的第一步就遇到了瓶颈:我们好像无法继续推导了,因为没有一处可以出数。不过我们不能灰心,实际上是有办法解决掉这个瓶颈的。

先看左图,可以看到,结构里有一个同数环结构。而删数是通过环结构的定义得到的,即弱关系对应的区域,所以结构里可以删除的地方是r3c6(6)和r7c4(6)。在删除了它们后,我们再来看右图。右图里由于删除了刚才给出的两处地方,所以剩余的部分里可以找到两个摩天楼,得到删数r3c5(6)和r7c5(6)。

此时就可以发现问题了:定义域区域c5里无法找到合适的地方填6了,所以出现了矛盾,所以原假设r8c1(6)错误,应当删除掉。

看了这么多例子了,我相信你应该有所感受。我们寻找删数矛盾,总是通过试填的方式来证明矛盾的出现,矛盾的出现也都只是利用结构内部(即定义域里)的所有候选数而已,并未涉及外部的任何其它的候选数。这也算作一种约定俗成的方式。

实际上,我们完全可以利用外部的数字来推导矛盾,但涉及的东西就比较多了,而且显得比较暴力。就好比UR里,我们通过强制UR的思路可以得到,实际上它也仅仅是利用了UR结构内部的候选数和共轭对来推导矛盾的,并没有涉及外部的其它任何数字。

我们再来看一则相对熟悉的例子。

如图所示。我们假设r3c2(5)或r6c3(5)其一成立的话,它们的位置看起来似乎是影响差不多的。比如r3c2(5)如果为真,则显然会使得r12c3(5)和r45c2(5)同假,而r6c3(5)也会导致一样的情况出现。所以我们可以断言,如果r3c2(5)可以删除,那么r6c3(5)也可以删除,我们就不必两个候选数都推理一遍了。

我们假设r3c2(5)为真,则可以得到下面图中给出的样子。

看起来定义域区域是5个,删除域区域也是5个,但结构出错了吗?确实是出错了。我们尝试观察b9,任意一处填数都会使得上方给出的r1245四行定义域区域出现类似于之前遇到过很多次的出错构型。所以,整体这个结构必然是错误的。这便得到了最开始假设的矛盾,故r3c2(5)是可以删除的;当然,r6c3(5)也是一样的。

和上面差不多的出错方式的示例还有下面这一个。

如左图所示,如果我们尝试假设r3c3(4)为真,则由于r4共轭对的关系,直接可以得到r5c4(4)为真,于是依然出现了如右图所示的出错构型。

所以,这些例子都还是比较清晰和神奇的。我们再来看一则利用鱼鳍推导的。

如图所示,这个结构饱和五个定义域区域和五个删除域区域,不过含有四个鱼鳍,而且四个鱼鳍不都能直接得到删数的成立。不过我们依然可以尝试利用试填的方式来得到矛盾。首先,两个外鱼鳍是可以直接对应删数的,所以我们就不再讨论它们了。接着我们来讨论两个内鱼鳍的情况。

如左图所示,假设r5c5(7)成立,则我们可以依次得到r4c7(7)和r8c1(7)为真的结果,由于r8c1(7)的成立,所以此时是可以删除r6c1(7)的。

如右图所示,假设r8c5(7)成立,则排除掉一些情况,我们发现剩余部分里,r59形成了一个二链列结构,而这个二链列依旧可以删除r6c1(7)。

所以实际上,两个内鱼鳍依旧可以对应到删数,所以删数r6c1(7)不论哪个鱼鳍成立都可以删除掉;而且鱼结构的删除域也包含r6c1(7),所以它可以安全地被删除。

这一则示例之所以放在不饱和鱼里讲解,是因为这一则示例也是通过不饱和鱼的结构包装得到的构型。如果你在做题过程之中能发现这样的形式的结构,我们就可以通过利用鱼鳍的方式来讨论,把结构变为秩为0的饱和鱼结构,这样看起来逻辑比起之前的示例要清晰一些。

如图所示,这是一个交叉五链列,看起来还不错,不过多了两个内鱼鳍。我们尝试逐个进行讨论。

如图所示,这是两个讨论情况。可以看到的是,不论哪种情况成立,删数都是可以删掉的,因为最终我们都会在b46里发现一组级联区块结构。级联区块可以当作X-Wing使用,而它们都会删除r4这一个区域的6。

如左图所示,我们找到一个交叉五链列结构,不过删除域区域比较多,要想覆盖完整就需要r1678b2368一共8个区域才行。不过不要紧,删除域区域再多也不害怕,因为删数一定是在删除域区域上的。那么假设我们让r6c9(5)为真,会如何呢?

如右图所示,我们按照顺序推导,就会发现,b3里同时出现两处填入5的地方,这便是产生了矛盾。所以原来的假设是错误的。

那么,我们给出了这么多例子,下面再给出两则示例,希望你能够自己理解它们。

这一则示例看起来比较麻烦,但实际上并不难。

这一则也是一样。

2-3 不饱和六链列

接下来我们来看一些不饱和六链列的示例。

如左图所示,这个示例看起来很漂亮,因为结构高度对称。假设r6c5(9)为真,则变为右图这样。

右图看起来似乎很麻烦,但实际上,它可以转化为之前我们就讲到过很多次的矛盾的构型。我们随意拿出一处定义域区域的两个情况来进行讨论,就可以发现讨论后一定会出现矛盾,这里我们就不重复给出示例的推导过程了,你可以自己试试看。

如图所示,假设r5c2(2)为真,则会产生矛盾。这一则示例就自己理解了,我们不再重复叙述它的具体逻辑。

Part 3 最后的介绍

鱼的内容就全部说完了,最后我们需要介绍一些理论的内容,以便编写电脑程序,或者书写参考文档时使用。

3-1 为什么同数技巧全都可以叫做鱼?

这一点我们其实看过众多例子了,所以我们不必过多叙述就能明白这一点。二阶的鱼结构我们可以转化变为链结构,例如双强链,或者带有区块的双强链结构;而三阶的甚至更高阶的,我们都可以通过鱼鳍的包装来得到推导;而包装比较麻烦的,可以通过远程试填来得到矛盾,或者甚至不用包装鱼鳍,直接上手就开始找内部的矛盾。所以,所有同数技巧其实都可以包装形成鱼结构。

3-2 自噬为什么是鱼的内容,而不是其它技巧的内容?

这一点我们也不必去过多叙述了。自噬就是通过删除域区域的交集而产生的一种特殊删数。如果它还在定义域区域上,那么删除它的原因就是因为原本结构的秩为0,而因为填入后,定义域区域少一个,而删除域区域少两个,秩变为-1,出现了矛盾。

不过可以通过鱼结构的理论知道,当鱼结构本身的秩就已经不是0的时候,我们并不难妄自下结论,说某个处于删除域交集上的候选数依旧是自噬删数。这样是不对的,因为它即使填入,鱼结构的秩也不能保证变为多少;更何况有一大部分鱼结构的秩并不是结构得到0就必然能够得到删除域区域全删的结论的。

3-3 鱼的系统命名规则

我们先来说说饱和鱼结构(即定义域区域和删除域区域数相同,且全覆盖的情况)的命名规则。

我们有如下的顺序来修饰一个鱼:

解释如下:

  • 鳍化修饰符:表示鳍影响到结构的类型。有三种鳍化类型:标准(Basic)、退化(Sashimi)和孪生(Siamese)。当为“标准”时,应当省略不写。且“退化”一词的位置应调整至鳍名修饰符之后。

  • 鳍数量修饰符:表示有多少个鳍。如果有多种鳍,则按照外鳍、内鳍、自噬鳍的顺序排列。如果同一种鳍只有一个或两个的,则使用单(Single)和双(Double)修饰,超过两个的,则使用汉字数字三(Triple)、四(Quadruple)、五(Quintuple)等表示。

  • 鳍名修饰符:表示鳍的名字。有两种鳍:外鳍(Exo-fin)、内鳍(Endo-fin)。拼写时应按照此顺序排列,并配合鳍数量修饰符描述。

  • 形状修饰符:表示形状。一共有三种形状:标准(Basic)、宫内(Franken)、交叉(Mutant);标准链列(标准鱼)的“标准”一词一般可以省略。

  • 规格修饰符:表示规格。规格取自于结构的定义域区域数。一般一共有六种规格(范围在 2 到 7 之间),使用汉字数字后添加“链列”二字即可。超过其规格的,仍使用数字,但结构本身一般不符合其标准;英文里一般有六种规格(范围在2到7之间):X-Wing、Swordfish、Jellyfish、Squirmbag(或Starfish)、Whale、Leviathan。超过其规格的,使用“数字 + 连字符 + Fish”的写法,如8-Fish,但结构本身一般不符合其标准。

合格的命名可以是如下的示例:

  • 双外鳍单内鳍退化宫内五链列

  • 四外鳍三链列

当然,你也可以使用D\S描述(D\S Description)来描述鱼结构。如:

  • rrb\ccc鱼(三阶、宫内)

  • ccbb\rrrc鱼(四阶、交叉)

其中用r表示一个行区域,c表示一个列区域,b表示一个宫区域。反斜杠左侧的部分是鱼的定义域涉及的区域的类型集合,右边则是删除域区域涉及的区域集合。

当然,也可以直接将定义域区域和删除域区域、结构涉及的数字、甚至是鱼鳍体现在其中。涉及的数字应写在D\S描述的前面,而鱼鳍应写在D\S描述之后,用空格隔开,且使用字母f、ef前缀表示属于外鳍还是内鳍,并且以“外鳍、内鳍”的顺序排放。如:

  • 2 r19b26\c578b1 fr3c6 fr9c3

  • 1 r9c4b6\r47c8 fr9c3

  • 9 c29b6\r468 efr4c9

这样可以直接看出规格、形状。其中的fr3c6就是指明有一个外鳍位于r3c6。第一个示例涉及的候选数是2,而第二个示例涉及的则是1。当详细描述时,末尾的“鱼”字可以被省略。

当鱼的定义域区域数少于删除域区域数时,称为不饱和鱼。这个术语词已经在之前提到过了。

当不饱和时,删除域区域数大于定义域区域数,此时应为鱼名称最前面添加“不饱和”一词,规格按照定义域区域数计算。比如定义域区域有4个,而删除域区域有5个,则我们认为结构是一个四链列,而不是五链列。

3-4 鱼图的符号规则

鱼图里一般想要表达出意思,需要不同的符号标识来表达。下面罗列出所有需要用到的符号。

  • 永假符号/:放到单元格里,表示该单元格不能放入鱼涉及的这个数;

  • 鱼结构符号x:表示当前单元格可能填入这个数字;

  • 删数符号*:表示当前单元格可以通过结构删除该单元格的这个数字;

  • 外鱼鳍符号F或&:表示当前单元格的这个数字是作为外鱼鳍出现的;

  • 内鱼鳍符号E或@:表示当前单元格的这个数字是作为内鱼鳍出现的;

  • 自噬符号C或*x:表示当前单元格的这个数字是作为自噬删数出现的;

  • 重删数符号**:表示当前单元格在一个饱和鱼结构不论鱼鳍是否成立,都能删除的地方;

  • 残缺符号I或!:表示当前单元格是结构不一定必需涉及的地方,它可以不存在,结构照样成立,且删数成立;

  • 未知符号?:表示当前单元格的删数是否成立,并不清楚。


第 61 讲:不饱和鱼的评论 (共 条)

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