EH的数独杂谈#6 待定数组（ALS）

目录：

一、ALS的基本概念

二、严格共享候选数(RCC)

三、ALS与连续环

--------

还记得以前的区块链吗？它用来描述链的节点为区块的情况。如果用朴素的试数过程来理解，那么区块链的过程就涉及一个区块为假或为真的情况。

当然，你有时在试数过程中发现的不是区块，而是显性数组。让我们看一看如下的实例：

如果r3c8≠8，那么r3c8=6，从而r13c9≠6。那么现在r13c9就构成了14的显性数组。当然对于这题来说，直接就得到r1c9=4。继续向下推导，得到r7c1=8。

整个链表示成如下形式：

r3c8(8=6)-r13c9(6)=r1c9(4)-r7c9(4=5)-r7c1(5=8)

产生删数r3c1≠8。

这条链里值得注意的一个环节是r13c9(6)=r1c9(4)。以前的篇章中涉及的链通常是同区的同一种候选数，或者同一单元格的不同候选数。但现在，区域与候选数种类都发生了变化。它们是如何联系起来的呢？

实际上，它与数组有关，但它“差一点”才成为真正的数组，我们称之为“待定数组”（Almost Locked Set，简称ALS）。

我们回顾一下数组的概念：

在同一行/列/宫内，如果恰好找到了n个单元格，里面恰好只出现了n种候选数，那么它们就形成了显性数组。比如刚才的图，一宫内就存在一个关于23的显性数组。我们因而可以确定，这两格一个填2一个填3。

有时候情况不会这样理想，比如你在同一行/列/宫内，找到n个单元格，但却有(n+1)种候选数。请仔细观察下面的绿框，这就是2个单元格里含有3种候选数的情况：

这种情况下，暂时并不能确知什么数字要填写在这里，也没有什么删数的效力。

但让我们仔细思考一下：如果这三种候选数有两种同时消失了会如何呢？比如1和4都消失了，那么就只剩一个6，却要填入两个单元格里，这违背了数独规则。所以在这两格内，1和4这两种候选数就构成了强链：

显然，无论哪两种候选数同时消失，都会产生这样的错误。所以候选数1和4，1和6，以及4和6，任意两种候选数都构成强链。

请注意上面的表述：构成强链的是两『种』候选数，即区域内全部的同种候选数共同构成链的节点。仍以上图为例，我们得到的强链是r13c9(1)=r1c9(4)，这两个1是放在一起的；但r1c9(1)=r1c9(4)和r3c9(1)=r1c9(4)都是不正确的，也就是这两个1不能拆开。

读到这里，你应该知道开头提到的那条强链是如何产生的了吧！

你会经常在实战中看到这样的ALS结构。有时候，多个ALS会以某种形式相互连接：

这是一个很简洁的实例。单独拿出橙色格和蓝色格，都分别构成一个合格的ALS。所以

橙色区域 r2c56(1)=r1c5(4)

蓝色区域 r1c2(4)=r5c2(1)

这道题里最巧的一点就是，橙色区域的r1c5(4)和蓝色区域的r1c2(4)恰好可由弱链连接，形成一条完整的链：

r2c56(1)=r1c5(4)-r1c2(4)=r5c2(1)

产生删数r2c2≠1。

像这样，不同ALS区域的同种候选数可能可以通过弱链相互连接。我们将两个ALS结构中用于连接成弱链的同种候选数，称为这两个ALS的严格共享候选数(Restricted Common Candidate，简称RCC)。

我们再观察一个实例，这个实例更加灵活：

这个例子和上面那个例子是同样的原理，请自行理解。在这个实例里，作为RCC存在的候选数是6。可以删除r9c9的4。

这样就结束了吗？之所以说它更加灵活，是因为你只要改变一下链头和链尾，就得到不同的结论了：

这就是这个例子的奇妙之处了，从同一个技巧里产生了多种删数。

观察这两个实例，我们发现了它们的共性：涉及两个ALS；存在RCC；两个ALS同时存在另一种不同于RCC的共同的候选数，它们构成强链并产生了删数。我们将这种结构称为ALS-XZ Rule，其中的X代表那个RCC，Z用于产生删数。特别地，如果这个Z不止一种且都能产生删数，则称这个结构是孪生的(Siamese ALS-XZ Rule)。

ALS-XZ Rule大概是两个ALS结构所能产生的最简洁的技巧了。稍复杂的还有一种被称作ALS-XY-Wing的技巧：

这个链同样非常明确，相信你可以通过图示直接看懂其逻辑。值得注意的是，如果把候选数单独拿出来，会发现它形如(8=5)-(5=6)-(6=8)的形式。特别像XY-Wing。这就是这个结构得名ALS-XY-Wing的道理了。

既然ALS可以为我们提供更多的强链作为选择，那么如果这条链处于连续环内，会不会因为ALS的关系产生更多的删数呢？

1. ALS作为连续环的一条强链出现

我们直接观察下面的例子：

在这里，通过蓝色的ALS区域得到强链，这条强链正好作为连续环的一部分。能否找到其所有的删数呢？

如果你对连续环的性质有印象，你就会知道，所有弱链可以变为强链，从而形成下面这些删数：

但对于这道题来说，还有一些关于8的删数：

或许你还记得，对于连续环来说，除了弱链可以当做强链以外，强链也可以视为弱链。这条性质曾被认为用不到，但有了ALS之后，“强变弱”的性质就有了用武之地。

我们来分析一下：这个ALS区域存在358三种候选数。已知35形成强链，作为连续环的一部分，它也可以当成弱链。既然是弱链，就意味着3和5至少有一种不存在；但作为ALS，它们又不能同时消失。所以，这两种候选数有且仅有一种存在。那不就意味着这两格一定要有一个8吗？所以产生了那些删数。

由此总结出连续环强链变弱链性质的使用方法：

2. 双RCC构成连续环

我们已经讨论过RCC的概念。在之前的例子中，RCC有且仅有一个。实际上RCC不止一个的情况也是存在的，这种情况相对于ALS单纯构成连续环要更加特殊，因为它往往可以产生一地的删数：

这两个ALS结构就存在两个RCC：2和8。我们称这种情况为Doubly Linked ALS-XZ Rule，在这种情形下连续环必然存在。请仿照上一个例子的推理过程，想想这里的这些删数是如何产生的。

--------