第 44 讲:动态环
Part 1 一个基本的示例

如图所示,链写法如下:
它的逻辑大致是这样的:设r7c2(1)为假,则得到r7c6(8)为假时分两种情况讨论,一个是r7c6 = 2,另外一个则是r7c6 = 5。但不管r7c6是数字2还是5,都能得到r5c8(1)为假,于是又可以得到r5c2(1)为真、r7c2(1)为假。这样就首尾拼接成环了。
可是稍微奇怪的是,r7c6分了两种情况讨论,也就是这里产生了分支,那么,这个环的删数仍然还是所有弱关系对应位置吗?
想一下逻辑,如果把逻辑抽象出来,就是下面这个样子:
首先,大体下,F-A部分是可以删除的,不过B-C和D-E两处是两种不同的情况,它们是“或”的关系(注意“或”的关系是指两个部分至少有一个为真,而不是有且仅有一个为真),所以我们无法判断到底B-C还是D-E是一直都可以的,也就不能找到分支条件下的删数。所以总体来看,删数只有F-A。
对于图上来说,只有r5c2(1)-r7c2(1)和r7c2(8)-r7c6(8)两处弱关系可以删数。
这个结构称为动态标准环(简称动态环,Dynamic Continuous (Nice) Loop)。有时候也将这种带有两部分子环形式的结构称为双环(Double Loop)。
我们再给出一个示例,请自行推理其推进过程。

这个链的删数特别奇怪,所以请注意实际的推导过程。这个环的理解比较难,希望你能慢慢地、细致地注意到每一个细节。
Part 2 原理进一步剖析
2-1 #1:动态环的删数是否有定式?
动态环的删数实际上在前面已经说了,所以我们可以在这里直接总结出来了。所以答案肯定是有删数的定式的。而且还比较明显。如果是读者你的话,不用看这一节的问题,自己思考一段时间,我想你也可以想到它——所有主干上的弱关系的区域都可以删数,而分支上的弱关系不可以。
可以从例子里看到,分支之间是或的关系,所以显然不可以删数,我们无法断言出删数一定能产生在分支上。所以不可以。主干上的弱关系有时候会很多,但有时候会少得可怜,看看上面的例子你就明白我在说什么了。
2-2 #2:英文名里的Nice有没有很重要吗?
是的。在Nice的原文描述里提到,“当且仅当环内的每一个弱关系都可以删数时,称为Nice Loop;否则称为Loop”。换句话说,如果我们现在有一个环,不论动态环还是标准环,如果环的每一个弱关系都可以实现删数(即使它在这个题目里找不到删数,但理论上可以删的话),就称为这个环是Nice的;否则就不能使用Nice。
可以看到,任意一个标准环都一定是Nice的,因为标准环的特征就是每一个弱关系都可以视为强关系,所以它们所在的区域上一定会出现一个节点包含需要填的数字,所以每个弱关系的对应区域都一定是可以删的;而动态环不同,由于动态环具有分支,所以分支上的弱关系我们并不能保证是否可以删除,所以动态环里不一定所有的环都能加上Nice一词。实际上,大多数动态环都无法实现全部弱关系都可以删除,只有很少一部分可以实现,所以大部分的动态环都不带Nice一词,即Dynamic Continuous Loop;而少部分动态环才称为Dynamic Continuous Nice Loop。所以前面给出的示例是不能加Nice的,因为它还有分支上的弱关系不能删数。
Part 3 嵌套结构的动态环
说完了基本的动态环的删数原则,我们来看一些嵌套结构的动态环结构。
3-1 动态环
如图所示,这个链内嵌入了毛刺隐性数对结构。链的写法如下:
这个题的推导和刚才的动态环差不多。删数也是找总体下的弱关系。总体下的弱关系有r9c1(1-7)、{r4c7, r5c8}(27)-r4c7(1)、r4c5(1)-r9c5(1)这三个。那么删数也就在这里面去找。需要提到的地方就是这里的r4c7和r5c8的2、7隐性数对的删数了。我们之前说到的是,删数是看两端都能删的地方,虽然这个2、7隐性数对确实可以删r5c8(8),但是r4c7(1)为什么也能保证r5c8(8)可以删呢?因为此时r4c7(1)和r5c8(8)都是弱关系。如果r4c7(1)和r5c8(8)同真时,b6内数字2没有位置可填。所以r4c7(1)和r5c8(8)确实是弱关系,也就确实是可以删的。
这个题目带有一个ALS,所以称为嵌套ALS的动态环(Dynamic Grouped Continuous (Nice) Loop With ALS)。同样,此题不加Nice。
我们再来看一个动态环。
3-2 Nice的动态环
获取你注意到了,前后两个示例的标题大致一样,就是英文名里,一个有nice,一个没有。下面我们来尝试理解一下它。

如图所示。这个动态环比较复杂。我们先从r2c2(2)开始设为假进行推理。
如果r2c2(2)为假,而此时r2c28是一个ALS区域,所以r2c8(3)必须此时为真才行。那么此时,由于r2c8 = 3的缘故,r2c5和r2c9都不能是3,所以此时r2c5(3)和r2c9(3)是同时为假的。我们先尝试走左边。
假设r2c5(3)为假,则r23c6(3)区块为真(当然,这里一般是当得到r2c8(3)为真后,r2c56(3)同为假,于是r3c6(3)为真,也可以这么理解),r5c6(3)为假,r5c1(3)为真,r6c2(3)为假;而假设r2c9(3)为假,则r2c9(7)为真,r4c9(7)为假,r6c7(7)为真,r6c2(7)为假。
此时可以发现,由于刚才假设的情况的成立,我们先得到了r2c8(3)为真的结果,并同时得到了两个分支的走向。可是神奇的地方在于,两个分支竟然最终汇聚到了同一个单元格:r6c2。
由于是两个分支的推导同时通过一个结论得到,所以两个不同分支得到的结论就应当是同时成立的,即这里的r6c2(3)为假和r6c2(7)为假此时必须是同时成立的,所以,r6c2此时只能放入2,故r6c2(2)此时为真,于是r2c2(2)为假,环便出现了。
那么,可以发现到的是,主线肯定是r6c2-r2c2(2)=r2c8(3)这一部分,但剩下的部分,都在分支上。按照原本的推导思路,主线上的所有弱关系是可以删除的,并且由于ALS区域处于主线上,所以ALS的额外删数:r2的其余位置的5也可以删除掉。不过,这个例子里我们可以删除太多其它的删数了,这些又是为什么呢?试想一下,这个结构带有两个不同的分支,但这两个不同的分支的特殊之处在于,它们以同一个节点延伸出去,这意味着两个分支应该是同时成立的,这一点我已经在前文里说过了。而在环结构的结论里,我们知道,环结构的内部填数只可以有两种情况;而在动态链里,分支里可能有不同的情况,所以不一定只有两种。但仔细观察这个示例就可以发现,这个分支是同时成立的,所以要么分支1成立,要么分支2成立。我们不必注意分支内部的填数模式,这两种情况我们便可直接作为整体动态环的两种不同的填数模式。
而环只有两种填数模式,且弱关系都可以删除,所以我们可以认为,这两个分支上面的所有弱关系都可以作为删除项,故两个分支的弱关系完全都可以作为这里所说的删除项而删掉。
可以看到,这个示例里,所有的弱关系全部都可以被删除,所以我们应为这个结构的技巧名加上nice一词,即动态的(dynamic)、嵌套结构的(grouped)、连续的(continuous)、删数完整的(nice)环结构(loop)。
Part 4 最后来个小练习?
之前我们已经给出了三道鱼图题目了,这里再来一道题。请找出所有不能填入的位置(可以删除的位置)。

答案
