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

第 26 讲:跨区数组基本原理

2021-05-13 10:10 作者:SunnieShine  | 我要投稿

Part 1 假数组/伪数组(Subset Counting)

如图所示。我们观察r5c2359和r6c2这五个单元格。它们有一个神奇的地方是,恰好五格里面刚好只有五种不同的候选数1、4、5、7、8。这恰好满足数组的定义啊,但是这一定就是一种数组吗?当然不能直接确定了。数组的定义是必须规定于同一区域下的,而这里的五格包含跨区域的单元格,比如这里r6c2和r5c9两格,就根本没啥联系了。

那我们这么去想这个问题:既然长得很像数组,那就分“内部填数不重复”和“内部填数有重复”来讨论情况吧。

我们发现,数字1、4、5、7、8这五种数字里面,只可能有数字7可能会重复。因为7的位置可以同时填入到r6c2和r5c9之中,这样它们两格没有直接关系,就可能产生重复。但是,其余的数字都不可能重复,比如1的位置就只出现在r5c39中,恰好r5c39同行(r5),所以这两格一定只可能有其中一格是1的;同理,4的位置也只出现在r5c23之中,恰好r5c23同行(r5)和同宫(b4),所以4在这五格里面就更不可能重复了;那么5和8的分析方式也是一样的(5的所有填数可能均同行,8的填数可能均同宫)。所以唯独数字7可能有重复。

那么,如果要把1、4、5、7、8这五种数字填入到这五格之中去的话,当内部有重复(就假设此时r5c9和r6c2同时是7)时,剩余的r5c235三格,就有四种填入的数字(1、4、5、8)可选。这样一来,究竟是其中的哪三种数字被选进去填入了,我们无从得知。所以这方面的情况我们确定不了。但是我们能确定的是,不管重不重复,数字7在结构之中都是不可缺少的。换句话说,这四格的数字7,是不可能全部从盘面之中消失的。同时全被去掉时,这五格里面就只剩下四种数字(1、4、5、8)了,又因为它们一定是不可填数重复的,所以这显然是不够的,所以便产生了矛盾。

于是乎,我们得到了结论:不管内部怎么填数,数字7都是不可缺少的,所以删除掉的是四格候选数7共同对应到的位置。所以,r5c1 <> 7。

这个结构称为伪数组(或假数组,Extended Subset Principle/SubSet Counting)。伪数组分析起来相当痛苦,也很费劲,而结论却如此“草率”。那么有没有什么办法更为简单呢?或者说,怎么样观察和使用更快一些呢?

Part 2 跨区数组删数理论和原理

伪数组的分析方向大体是按照是否是一个“跨区域的数组”来看的。如果是,则内部不重复;而如果不是,则内部一定有重复的数字。然后就去找重复的数字到底是多少。而伪数组有一个特征,这在刚才我们推导原理时,就得到了一点:伪数组假设内部有重复的话,唯一有重复可能的数字一定不可全部从盘面之中消失。所以,在观察和找结论的时候,只要判断出唯一可重复的数字是多少,找到交集,就可以直接删数了。

那么,有没有一眼看出来,是一个跨区域的结构,但是内部一定不重复的呢?有的,比如这个例子。

如图所示。观察r34c34四格,内部只有1、4、6、8四种数字,而恰好填入于四格之中。但巧妙的是,1、4、6、8都不可重复,因为数字1的所有填数位置同列,数字4的所有填数位置通同列,数字6的所有填数位置同行,8的所有填数位置同行。所以这根本不可能有重复的填数情况的。

我们称,如果在分析一个伪数组时,发现它的内部一定不重复的话,这个结构就叫分布式跨区数组(Distributed Disjointed Subset,简称DDS),简称跨区数组。那么一个DDS的删数应该如何呢?

由于内部不重复的关系,一个跨区数组内一定恰好只填入这些数字,换句话说,这些数字都是必不可少的。因此,比如图上示例,由于1的填数一定出现在r34c4上,所以c4内其余单元格都不可以是1;6的填数一定出现在r4c34上,所以r4内其余单元格都不可以是6,而4和8也是一样。所以,删数已经全部标注在图上了。当然了,该示例还有一个DDS,请你寻找一下。

Part 3 SDC和跨区数组

SDC特别麻烦,分了好多种不同的情况来讨论和分析。不过,最终我们发现,很多“恰好”满足的情况,就比如三个单元格融合示例(即带区块示例)里的1、4数对、2、6、7三数组和这个单独的9,都是“恰好”形成的。那这么多“恰好”,真的是偶然导致的吗?现在我们就来看一下这个问题。

如图所示,这是一个SDC,不过我没有分成橙色和绿色来涂色。因为这样更接近于伪数组的分析方式。

我们使用伪数组的分析方式来看,它是一个跨区七数组,但是巧妙的是,内部并不可能有可以重复的数字,因为1、2、3、4同列(c8),而7、8、9同宫(b6),所以它是DDS。按照DDS的删数原则,c8内其余单元格都不可以是1、2、3、4;而b6内的其余单元格都不可以是7、8、9了。于是删掉它们。

SDC的观察或许比较麻烦,因为需要分两个区域来假设其待定数组的情况。但是使用伪数组角度,是不是会稍微轻松一些呢?

融合待定数组(SDC)还有一个名字叫双区域分布式跨区数组(Two-sector Disjoint Subset),就是因为这个原因。


第 26 讲:跨区数组基本原理的评论 (共 条)

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