网站首页 拼图游戏 填字游戏 填色游戏 找茬游戏 七巧板游戏 数独游戏 迷宫游戏 任天堂游戏  
  收藏本站   
  网站帮助   
  报错建议   
  联系我们   
关键数删减法
作者:尤怪之家

概说

遇到了高级、困难级的数独谜题,使得唯一候选数法和隐性唯一候选数法黔驴技穷的时候,就是各种删减法上场的时机了。在各种的删减法中,哪一个要先用是随个人之喜好的,并无限制。本页介绍的例子虽然可能可以使用其他删减法完成解题,但在大部份的情况下是无可取代的,不过本删减法成立的条件和其他方法相比稍嫌繁杂,所以一般在使用时,均将其优先顺序 放在后面,只在不得已时才用之!


<图 1>

请看<图 1>,此时使用以往所提及的:数对删减法、区块删减法、隐性数对删减法、三链数删减法、 隐性三链数删减法、矩形顶点删减法、三链列删减法...等各式删减法都已找不到下一个解了,这才是 关键数删减法(Colors, Colouring)最好的上场时机。

某一个数字在某一行、某一列或者某一个九宫格的各宫格候选数中恰出现两次时,我们说在 这一行、这一列或者这一个九宫格中有了一个关键数。由于使用本删减法的时机是在数独填制的中后期, 所以拥有同一个关键数的行列或九宫格通常不止一处,而且环环相扣,使得候选数中包含该关键数的宫格 形成泾渭分明的两大阵营;<图 2> 和 <图 1>是完全相同的数独残局,但只显示候选数 4 的情形:


<图 2>

在 <图 2> 中,第一列的数字 4 仅出现在 (1, 1) 及 (1, 5),是本列的关键数,此时,若数字 4 应填入 (1, 1),则 (1, 5) 就不能再填入数字 4;反之,若数字 4 应填入 (1, 5),则 (1, 1) 就不能再填入数字 4 了; 虽然我们还不知道哪一个宫格应填入数字 4,但却可以利用关键数的这一个特性,将待填的部分宫格区分成两组, 只要其中的一组宫格应填入数字 4 ,另一组宫格就不可能再填入数字 4 。<图 2> 中底色为粉红及浅蓝的两组宫格, 就具有这样的性质。

接下来,我们就可以根据这两组宫格的分布情形,做一些确切的判定:

  • 当在底色为浅蓝的宫格中填入数字 4 时,并无任何不妥!
  • 若在底色为粉红的宫格中填入数字 4 时,则第 7 列或第 7 行都将出现两个数字 4,这是违反填制规则的。
所以所有底色为粉红的宫格都不可能填入数字 4,这些宫格候选数中的数字 4,全部都可以删减掉!回到 <图 1>,我们可发现,进行删减之后,下一个解的寻找根本就不成任何问题了。

 

大部分情况下,利用行列及九宫格的关键数将相关宫格区分为两组后,并不一定可找出上述的矛盾状况, 而确切的据以判定某一组宫格可进行候选数的删减,例如<图 3>就是一个例子:由第 9 列的关键数 6 所引发区分的两组宫格,不论将数字 6 填到粉红或浅蓝为底色的宫格中,都是不会产生矛盾的。


<图 3>

不过<图 3>却展示了关键数删减法的另一种删减状况;请看第 1 列中的 (1, 5) 及 (1, 8),它们有什么 特殊之处呢?尤怪居然要用浅绿的底色来标示!

哈!哈!相信你已看出来了,在这两个宫格的同一行上,都有两个不同底色的宫格存在,这代表:不论最后 数字 6 应填到哪一组底色的宫格中,因为本行的数字 6 已被填入了,所以这两个宫格都不可能再填入数字 6 了,因此这两个宫格的候选数 6 都可被安全的删减掉!

为了更清楚的说明这类的删减,假设有某个数独残局的数候选数 1 分布如<图 4> :


<图 4>

利用<图 4>第 1 列中的关键数 1,可将部分宫格区分为两组独立的宫格,分别以粉红及浅蓝为底色来标示; 只要其中的一组宫格被填入数字 1,另一组宫格就不可能再填入数字 1。虽然在本图中的任一组宫格中填入 数字 1 都不会产生矛盾,但是仍可以利用这些宫格的分布,对其他宫格进行删减。

  • 先看 (3, 7)、(3, 8)、(3, 9),因为上右九宫格中己拥有粉红及浅蓝为底色的宫格各一个,表示不论 数字 1 应填到哪一组底色的宫格中,因为本九宫格中的数字 1 已被填入了,所以其他宫格都不能再 使用数字 1 了,因此这三个宫格的候选数 1 都可被安全的删减掉!
  • 再看 (4, 9),因为同行的(2, 9)有一个粉红底色的宫格,同列的(4, 4)又有一个浅蓝底色的宫格,所以 不论数字 1 应填到哪一组底色的宫格中,因为同一个行、列中的数字 1 已被填入了,所以本宫格就不能 再使用数字 1 了;这个宫格的候选数 1 可安全的删减掉!
  • 最后来看看 (4, 1)、(5, 1),因为同行中己拥有粉红及浅蓝为底色的宫格各一个,所以这两个宫格的 候选数 1 都可安全的删减掉!

利用“以关键数的关系找出矛盾的组合,或者找出确切可进行删减的宫格,进而将该数字自宫格候选数中删减掉” 的方法就叫做关键数删减法(Colors, Colouring)。由于在说明本法的分组状况时, 以颜色来区分是最清楚明了的,所以外国人就以 “colors 颜色”为名,也是十分传神的。


Copyright ® 2013-2024 puzzle8.com All Rights Reserved.

沪ICP备05056905号

苏公网安备 32108102010371号