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

第 41 讲:基本的强制链类型

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

强制链(Forcing Chain)是链的一个重要的思想,为了让链的使用范围更加广泛,便产生了这个思想。

Part 1 基本的强制链类型

下面陈列一些基本的、常见的强制链模型。

1-1 区域和单元格强制链

区域强制链(Region Forcing Chain)和单元格强制链(Cell Forcing Chain)属于一类强制链,这个类型的强制链使用链的思维,将某一个区域所有每个候选数,或某一个单元格的所有候选数情况进行分情况讨论,并以弱关系延伸(即假设每一个分支的头节点为真的形式进行向下推理),直至所有分支的尾节点均能得到一致的结论。如果全部情况都能得到一致的结论,则结论一定成立。不过,区域强制链是按行列宫的某一种候选数进行分情况讨论的,而单元格强制链则是按单元格的所有候选数进行讨论的。

1-1-1 区域强制链

如图所示,可以发现c6一共有三个2,我们将每一个2都进行讨论。

  • 第一种情况:r1c6(2)为真。显然,r1c6 = 2时,一定有r1c1 <> 2;

  • 第二种情况:r3c6(2)为真,此时有一条强制链:r3c6(2)-r3c28(26)=r3c8-r3c1=r1c1(5),得到r1c1(5)为真,所以一定也有r1c1 <> 2;

  • 第三种情况:r8c6(2)为真,此时有一条强制链:r8c6-r9c4(2)=r9c1(2),得到r9c1(2)为真,所以r1c1 <> 2。

所有的情况均能使得r1c1 <> 2,所以r1c1 <> 2结论是成立的,可以删除掉它。

1-1-2 单元格强制链

如图所示,按r4c7的所有候选数进行分情况讨论。

  • 当r4c7(3)为真时,则有强制链:r4c7-r6c8=r6c3(3),即得到r6c3 = 3;

  • 当r4c7(5)为真时,则有强制链:r4c7-r4c6=r6c6-r6c3(5=3),即得到r6c3 = 3;

  • 当r4c7(6)为真时,则有强制链:r4c7-r7c7=r7c4(6)-r14c4(46)=r1c4-r1c3=r6c3(3),即得到r6c3 = 3。

所有的单元格的情况都能得到r6c3 = 3,所以r6c3 = 3结论成立。

可以看到,上述的两种推导方式都不是很特别好,因为它多少都有一点试数的风格。不过,有些题目不得不使用这类技巧才能完成。所以请读者你在使用之前斟酌,不要随时随地都使用它,这样是不合适的。

1-2 矛盾强制链

前面叙述了一种分情况讨论的强制链,接下来要讲到的矛盾强制链(Contradiction Forcing Chain)则是另外一种类型的强制链。这种强制链依赖于一个节点的两种情况。当两种不同的情况均能得到一致的结论的时候,则结论成立。

如图所示,按r9c8(8)执行两种情况的假设。

  • 假设r9c8(8)为真,则有强制链:r9c8-r9c1=r8c1(8),则r8c1 <> 6;

  • 假设r9c8(8)为假,则有链:r9c8=r5c8-r5c4=r2c4(8)-r1c5(6)=r8c5(6),依然可以得到r8c1 <> 6。

不论真假,都可以得到r8c1 <> 6,所以r8c1 <> 6。

另外,这个类型的强制链一般可以改写为普通链的形式,仅需要将其中一种情况反向即可,所以矛盾强制链一般不实用,仅在一些特殊情况(例如嵌套结构里)使用较多。

Part 2 链能看逆向,那么强制链呢?

可以看到,强制链和链不一样的是,强制链有至少两个分支,而带有不同的推理情况。那么链可以逆向理解,强制链是否也可以呢?实际上是可以的。我们先来看区域和单元格强制链的大致逻辑:将所有情况进行分情况讨论,如果全部情况都能得到一致的结论,则结论一定成立。那么倒过来,则是这样的一种情况:假设某条件成立,则能推出某一个区域下的所有某一候选数全为假,或者某一个单元格的所有候选数全为假时,产生矛盾,所以原假设错误。

同理,矛盾强制链的逆向视角则是:假设某条件成立,则能推出某一个节点存在真假两种情况都成立的矛盾情况,进而得到原假设错误。

第 41 讲:基本的强制链类型的评论 (共 条)

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