人生游戏:数独

在人生的不同阶段都玩过数独。数独作为一种轻便的思维游戏,似乎每次重新捡起来玩的时候,还是都有新鲜感。

寻找“落单”数字

最初根据数独的游戏规则,就可以得到一些显而易见的规律,足以应付一些中低级谜题,这些规律甚至并不需要什么推理。在数独中进行推理时,主要用于做判断的单元是:行、列、区。一个标准的数独棋盘行、列、区都各有 9 个。以下为了方便,就都用“有效单元”来称呼单个行、列、区。

  • 首先,在单个有效单元中,单个数字有且只有 1 个。因此对简单情况,扫描单个有效单元,就可以猜出所需数字
  • 变体1 :在单个有效单元中,如果一个格子只有一个候选数字A,那这个格子里肯定填的是数字A
  • 变体2 :在单个有效单元中,如果数字A只有一个格子可以填入,那数字A肯定就是在这个格子里,即使这个格子可能有好几个可能的候选数字。

以上这两个变体其实是一回事,如果玩的时候使用了笔记功能,并且笔记做得完整充分,那很容易就可以找到这些“落单”的数字,把它们填入适当的格子。如果玩的是 App 版的数独,很多都会有自动过滤功能,就是选中一个数字,App 会高亮该数字可以填入的所有格子,置灰不能填入的格子。那只要我们从行、列、区三个维度依次扫描,也很容易找到那些“落单”的数字。

交叉排除修剪

快速处理完“落单”的数字后,就要再深入一步,这一步主要是用交叉过滤的方法。交叉过滤主要是用单个区,去和行(或列)进行交叉。因为行和列交叉没什么意义,它们只有1个格子是共用的。

  • 首先,看该区里,它和经过自己的某一行(或列)非共用格子部分(另外6个格子)有什么数字。如果已经有填入数字,那这些数字必定不会再出现在共用格子里。所以这些数字只能出现在这一行(或列)的剩下 6 个格子。
  • 同理,如果某区里,某个数字A已经推理出来必定在某一行(或列),那想象将这一行(或列)两边延伸出去,它们和延伸出去经过的其他区共用的格子,必定不会再出现该数字A。通过这个方法可以有效地修剪掉其他区的共用格子的候选数字的数量。

寻找裸对

上面两种方法有点类似让眼睛进行逐行逐列扫描,这两招用完可以解决大部分简单情况。剩下可能就要单独去看一些格子了。其中裸对的意思是:

  • 在同一个有效单元里,如果发现 2 个格子的候选数字完全相同且恰好是 2 个数(比如都是 {3,8})。那这 2 个数必定分别属于这 2 格,虽然还不知道哪个在哪格,但已经可以把这个有效单元的其他所有格都排除 3 和 8 了。
  • 同理,在同一个有效单元里,如果发现 3 个格子的候选数字完全相同且恰好是 3 个数(比如都是 {3,5,8})。那这 3 个数也必定分别属于这 3 格,所以也可以把这个有效单元的其他所有格都排除 3、5 和 8 。

删完之后,往往又可以触发前面两种情况,又可以用之前的方法填入一波数字。形成连锁反应。理想的情况,通过循环使用上面几种策略,就可以把一个数独完成了。

并且我在玩的过程中发现,如果上来先做好完整标注,再推理,虽然看似前面浪费了时间,但其实往往总时间会更短。所谓好记性不如烂笔头啊。

X-Wing 排除

X-Wing 方法指的是这种情况:例如下图中,在第 2 列里,数字 4 只可能在 r3c2r5c2;第 5 列里,数字 4 也只可能在:r3c5r5c5。这两个列的 4 被限制在同样的两行 —— 第 3 行和第 5 行。这就是 X-Wing。从这里可以推理出:第 3 列和第 5 列里的其他格子都不能再是数字 4 了。直接可以把数字 4 从这些格子的候选里排除掉。

但是在实际的实践中,我发现如果一开始标注做全了,那使用前面的几种自己的手段,很少会出现 X-Wing 的情况。

Y-Wing 排除

“Y-Wing”与“X-Wing”类似,其本质是:三个双值格联动,用来删除某个候选数。但它是基于三个角,而不是四个。

开始时,需要找到一个刚好有两条笔记的单元格,将这个单元格叫做“折点”。然后,再找两个也有 2 条笔记的单元格。这些单元格(叫做“钳”)应该和“折点”位于同一行、同一列或同一宫中。每个“钳”中的两个数字之一应该与“折点”中的相同。两个“钳”中的另一个数字相同。也就是这种结构:

  • 中心格:{A, B}
  • 翅膀1:{A, C}
  • 翅膀2:{B, C}

关键条件是:中心格能看见两个翅膀,两个翅膀都含有同一个候选数 C。于是可以推出结论:任何同时能看见两个翅膀的格子,都不能是 C。简单说:AB 看到 AC 和 BC ;于是可以从同时看到两个翅膀的格子里删除 AC、BC 的共同候选 C。要注意的是:

  • 第一,Y-Wing 不能直接说某个格子等于几,它通常只是删候选数。
  • 第二,两个翅膀不一定要互相看见。重要的是中心格能看见两个翅膀,被删除的那个格子能同时看见两个翅膀。
  • 第三,三个格子必须都是双值格。如果某个格子是 {3,7,9},通常就不是标准 Y-Wing。

剑鱼模型排除

“剑鱼”解法与“X 翼”类似,但使用的是三组单元格,而非两组。来看一个例子。

6 是我们的“鱼数字”,第 1、6 和 9 行是定义域。数字 6 的候选单元格也在 3 列中完美对齐。因此,数字 6 的位置有两种选择。无论在哪里,那 3 个包含对齐列的域都说明 6 不可能在其中出现两次。因此,我们可以安全排除这些列的所有其他笔记中的 6。


最后…

最后到了一些高难度谜题,会发现即使上面几招用完,也还是很大可能得到一个很难破局的状态。这时就只能考验推理了。

具体做法就是构建推理链,找到矛盾点,确认最终的数字。那具体怎么识别从哪个格子开始推理呢?如果只是随便挑一个格子假设,那确实会变成暴力试错,效率很低。所以不要乱选格子。候选链的技巧是:只从有强制关系的地方开始。按这个顺序看:

  • 找只有两个候选的格子。例如 {1,8}{3,5}{6,9}
  • 找某个数字在一行/列/宫里只出现两次的位置。例如某列的 8 只有两个位置
  • 从这些“二选一关系”开始推
  • 每一步只走“被迫成立”的关系

具体做法就是问自己:如果这里不是 8,哪里会被迫成为 8?然后一直开链推理下去,看能否找到矛盾。最后,也不是每个假设都能找到矛盾。很多假设会推不动,或者推很远也没结果。那就应该停止,不要硬算。实战建议:一条链推 5~8 步还没有明显收益,就先放弃。练习识别这些“二选一关系”,才是从中级进入高级数独的分界线。

最后的最后,还有一种暴力解法,就是取巧一点牺牲准确性,直接找一些二选一甚至三选一的格子来猜,一旦猜对该格子其中的数字,就会触发连锁反应,就可以用之前的办法把剩下的格子都填了。但这个只在 App 形式的游戏里有效,猜对猜错应用会直接提示。如果你是拿一张纸在玩,那就猜都不好猜了。

微信扫码打赏