零秩结构

Rank-0 Pattern

我们知道,秩的计算是通过最多可能填充的总数减去实际填的总数,得到的差值。这个数反映了理想和现实的差距。另外,这个结果也可以用于了解结构的填数的分布位置。

根据抽屉原理,我们可以知道,当秩为负数时,结构显而易见不成立;但如果秩为非负数呢?那似乎并不能得到什么有效性的信息。但是只要我们拆成两种情况来看,那么问题就会变得比较方便上手。

今天我们先来最容易上手的类型:零秩结构(Rank-0 Pattern)。

什么是零秩结构

零秩结构,指的是结构的秩为零的那些技巧类型。当一个技巧的秩为零时,说明填充的强区域数量和弱区域数量相等,因为要保证结构需要同时满足弱区域的填充规则,又需要在每一个强区域里安排填数,所以最终每一个弱区域都会安插一个数进去。

这句话稍微解释一下。

弱区域保证的是最多填一个,所以你不能安排两个数填到同一个弱区域里,所以最终的效果就是,每一个弱区域只能填一个。

下面我们来看一个例子。

基础的零秩结构

复杂鱼

复杂四阶鱼

如图所示。我们将 8r1258b7 视为强区域,而 8c1257 视为弱区域。这样分配可以使得每一个数都有一个强区域和弱区域的归属。

这里,“每一个数都有一个强区域和弱区域的归属”这一点很重要。这一点暗含了两层意思。

因为弱区域的讨论需要依赖我们强区域里已用的候选数位置。对于此题而言,比如 r5c7 这种位置你肯定需要优先按列连接到上面 r2c7 去,而不是使用诸如 8b6 这样的弱区域。8b6 的问题是,它无法覆盖到 r2c7 使得 r2c7 又自己需要独立的弱区域覆盖用于最终讨论排列情况;而这样弱区域数直接从 4 个变为 5 个,此时秩就不为 0 了。这是第一层意思,必须有所覆盖。

另外,每一个数都必须有一个强区域和弱区域的归属,还有对“一个”的强调。换言之,你不能让一个候选数同时被两个强区域和一个弱区域覆盖,或者一个强区域和两个弱区域覆盖,甚至更多。因为这样覆盖会造成讨论它的真假性时,它会直接影响结构整体总的实际填的次数,造成结构讨论复杂度增大(增大的甚至不是一星半点)。

回到题目。既然每一个数都有合理的覆盖,那么我们可以鲁莽下结论:因为弱区域数和强区域数都是 4,所以这个结构的秩为 0。换言之,我们实际的填数次数和最多可填次数一样多,那么只能安排每一个弱区域都必须填充一个数到强区域交叉的点位上。比如说 8c2 这个弱区域,它和强区域的交点有 r1258c2 四个单元格。那么秩为 0 意味着我们需要在 c2 里排列有且仅有一个填 8 的位置到其中去。

如果从穷举的角度来看,这个题一共存在 12 种不同的、正确的排列模式:

  • r1c5、r2c7、r5c2、r9c1

  • r1c5、r2c7、r5c2、r8c1

  • r1c5、r2c7、r5c1、r8c2

  • r1c5、r2c2、r5c7、r9c1

  • r1c5、r2c2、r5c7、r8c1

  • r1c5、r2c1、r5c7、r8c2

  • r1c2、r2c7、r5c5、r9c1

  • r1c2、r2c5、r5c7、r9c1

  • r1c2、r2c7、r5c5、r8c1

  • r1c2、r2c5、r5c7、r8c1

  • r1c1、r2c7、r5c5、r8c1

  • r1c1、r2c5、r5c7、r8c2

穷举只会在这里出现一次,以后我就不再穷举了。我的本质还是想告诉大家通过秩的分析来看删数,而不是穷举。这里列穷举是为了衔接以后的内容,方便你知道这个理论是可行的。

按穷举来看的话,每一个弱区域也确实都有一个数字实际占位,所以所有弱区域用于删数的现象是能够得以体现的。

所以,本题的删数有很多:r36c257(8)r4c12(8) 一共 8 个。

这种结构也是基于之前学到的鱼结构进行的推广,只不过它用到了一个宫的强区域 8b7。这种鱼被称为复杂鱼(Complex Fish),是鱼体系里比较复杂的内容部分。这个以后会有单独的部分对其进行详细的内容介绍。

区块连续环

区块连续环

如图所示。这个题就是很普通的区块连续环,不过我们带着各位用秩来看一下删数。

这个题的强区域是 1r692r92c4 四个,弱区域是 1c36n49n92b8 也是四个,因为也是每一个数都有合理的一个强区域和弱区域的分配,所以可以直接得到秩为 0 的结果。

所以,在排列数字的时候,每一个弱区域上都会有一个数字在和强区域的交点上,故本题的删数可以包含 r45c3(1)r6c4(12)r7c56(2)r8c6(2)r9c9(3) 一共 8 个。

绽放环

这已经是我们第三次和绽放环打交道了。之前两次都是采用的朴素的解释,下面我们来看绽放环的秩的解释方式。

绽放环

如图所示。我们把强区域和弱区域找出。强区域是 8 个:16r31236r51r94c6,弱区域也是 8 个:1c356c13n75n6899n6

因为它符合前面描述的每一个数都有一个强区域和弱区域覆盖,所以秩显然是为 0 的。所以,每一个弱区域都可以用来删数,比如这个题的这一些。

所以就解释完了。是不是秩理论解释起这个非常方便呢?不过,这里似乎有一个问题。看起来这个题如果要用原来绽放环的视角去看,不论是最普通的强制链分支连接,还是用毛刺,似乎这个画法都不太好去包装。这真的是绽放环么?而且,就算这是个绽放环,但这个秩为 0 怎么看起来都像是恰好的,它没有一个非常明显的暗示告诉我们绽放环的秩一定都是 0,万一只是这个题恰好等于 0 呢?

没问题。下面我们对绽放环的秩的分析进行一个抽象层面的介绍。

绽放环为什么是零秩的

我们思考一下,绽放环的秩理论是怎么看、怎么计算的。

绽放环的本质是使用毛刺带分支,绕回预备删数的情况。上面这个题里,结构是将 r3c7(1) 视为毛刺,然后接到 r3c7(6)r3c1(6)r5c1(6) 最后回到 r5c6(6) 的这一截作为毛刺的分支;把这一部分的强弱关系干掉之后,剩余的部分就是毛刺连续环了。

到秩理论里,其实就是把名字改成了强弱区域而已——强区域暗示必须填一个,这不就是不同假么;弱区域暗示最多填一个,这不就是不同真么。虽说不同假时可以同为真,就不是填一个了;但是我们将结构平铺为普通的强弱链过程,避免类似待定数组里那种跨数字又不同一个单元格的强链关系,最终我们还是会回到图中这种强弱区域的表示上去。

这些都不重要。重要的是,我们可以用强弱区域的概念直接“兼容”强弱链关系的概念这个特性,对绽放环直接进行秩理论方向的转化,所以看起来就不太像绽放环了。但是实际上还是算绽放环的。

那么,为什么绽放环是零秩的呢?

毛刺为真时回到预备删数为真的过程才叫绽放,所以我们将其按这个思路将毛刺的两边拆开来看。

对于毛刺连续环里,如果不算毛刺,则强弱区域数应该是相等的,因为这是连续环,强弱链关系的数量肯定是一样多的;而算上毛刺后,毛刺引出的强制链分支会先从弱关系打头(因为假设其为真才能出去),所以上来是一个弱区域,然后强弱区域这么交替。最后,因为我们要回到预备删数,而预备删数和结构是弱链关系(不同真),所以预备删数到结构内是弱区域相连的。

因为这个到预备删数的部分已经被连续环那一部分里算过一次了(因为毛刺连续环要经过这个预备删数的这个单元格作为弱链关系连接,即图中的 r5c6,或者说 5n6),所以在统计强制链分支时将不考虑它。所以剩下的就是一组强弱交替,且开头为弱区域,结尾为强区域的待计算的部分。

因为强弱此时是交替的,所以这一截强制链分支需要统计的强弱区域数量也应该是一样多的,毕竟都交替出现了。

所以,毛刺连续环用的强弱区域数量一样多,而毛刺引出的强制链部分的强弱区域数量一样多,所以拼一起得到的结果自然就还是一样多的。

既然一样多,自然秩就等于 0,所以绽放环是零秩的。

最后更新于