数独难题组合构建法.docVIP

从Skyhuner的难题说组合构建 Skyhuner发贴子，介绍了四道数独题，其中有一道难度为11.9： 000 000 039/ 000 001 005/ 003 050 800 008 090 006/ 070 002 000/ 100 400 000 009 080 050/ 020 000 600/ 400 700 000 我尝试用”组合构建法”来解，花了点时间，感觉还可以，不算太吃力。现将解题过程贴出来供大家评鉴。 组合构建法源于欧美，应用于解题，仍处于发展阶段，国内还没有引进，所以想借此机会，介绍给喜欢 解难题的朋友。 组合构建法主要是通过对备选码（又称候选数）进行计量分析，主动地在同一宫链的某些位格中进行挑选， 使适合条件的备选码能够构建成一个组合，并通过构建而成的组合，经组合排除使备选码得以减少，达到 最终将命题破解的目的。为帮助读者理解和掌握这种方法，有几个重要的基本概念，必须先加以说明： 1, 满额组合：（横行直列统称为链，每一个小方格称为位格或点） 宫链中除已知码外，剩余的位格里所有的备选码全部参与而构成的组合称为满额组合。其中如果有某个 备选码只出现过两次，那么，这个备选码就称为”双子码”。 2, 差额组合：宫链中除已知码外，剩余的备选码所在的位格，有一部分不参与组合的构建，这种不是满额的 组合称为”差额组合”。 在差额组合中，或者在特别选定的同一宫链的某几个位格中，如果有某一个备选码只出现过一次，那么这个备 选码称为”突点”。 3, 满额组合中，双子码之”二选一”： 一个备选码在同一宫链的某两个位格中，各出现过一次，成为双子码，因唯一性原则，两个位格非此即彼，不 能遗缺。那么按什么准则来作”二选一”呢？目前使用的是优势准则。即出线率较高的被选中（概率的大数论） 例如，以下列的A链为例： 2567/1456/124567/ 268/2467/4678/ 1247/3/9/ ，其中，有两个已知码：A8=3 A9=9 剩余的七个位格中，备选码出现的次数各不相同且皆不少于两次，只有 备选码8是两次。那么，双子码8之”二选一”怎么选呢？比较8在A4=268和A6=4678中所占的优势，其中， A4=1/3 A6=1/4 很明显，A4优于A6，因此，被选中的是A4=8。 （A4=8还因周围环境而影响其出线优势，恕不详述）。 4, 差额组合中，含突点的组合如何构建？请看下面B链的实例： 26789/4689/246/ 23689/23467/1 247/2467/5/。链中B6=1 B9=5 是仅有的两个已知码，为保证有一个突点， 我们把备选码9所在的三个位格，撇在一旁，不参与组合的构建，那么，剩余的位格及其备选码就构成如下的 组合：B3/B5/B7/B8=246/23*467/247/2467 其中，备选码3只出现一次（它就是突点，用 * 标注）如果我们 把3*抽离出来，就得到 B3/B5/B7/B8=246/2467/247/2467。即 B3/B5/B7/B8=2467 这是一个标准的四元四位格组合，依例是具有排他功能的。於是，备选码9所在的三个位格中，凡含有2467的 皆被排除，结果是： B1=89 B2=89 B4=389 又因B1/B2=89 故B4=389变成B4=3 。 现在，返回来检视B5=23*467中被抽离的3* ，因B4=3而遭排除，到这时B5中的突点3才真正的被抽离了。 （这里借用了时空倒置原理）。以上的叙述，可以用下列程式简明表达之： B链（9） 3*/2467 得B1/B2=89 B4=3 突点组合的构建，关键在于如何选择不参与组合的位格。它必须保证能获得一个突点，而且也只能有一个突点。能满足这个条件，突点组合就构建成功，如果没有突点或有多个突点，构建就算失败。 有了以上的基本概念，解题过程就可以概念化地叙述，并用简单的程式来表达，无需再作详尽的说明了。 下一个贴子，将详细说明难度为11.9的数独题是怎样解出来第3/7页 的。 组合构建法，解11.9难题 Skyhuner推介的难度为11.9的数独题，怎样解？请看下列说明： 本例的阅读方法：预备纸笔，画好九宫图，填好已知码及各剩余空格内的备选码。 在求得每一个实码或二元（三元）组合时，均应在相属的宫链内，把同名的实码 或组合码加以排除，并用符号”划在该数码上。这一操作将贯穿解题的全过程。 任何疏忽将导致解题过程的复杂化，也可能招致失败。 1. 在B链构建不包含备选码（9）的、以3*为突点的四元组合： B3/B5/B7/B8=2469 （前贴已有详细说明） 经组合排除，得B1/B2=89 B4=3 以上叙述可用下列程式简明表达之 B链-（9）-3*/2467 得B1/B2=89. B4=3 2. 在A链，有以8为双子码的满额组合：8/124567 其中 A4= 8， （A链中的四个8，有两个已被B1/B2=89所排除，因而成为双子码） 3. 在第4链构建不包含备选码（9）的、以2为突点的三元第4/7页 组合： （9）-2*/156 得H4=9 C4=2 至此，有三个跟随的宫链三星点可以确定：K5=2 F6=8 C6=9 （同一个元码，在相关的宫例如第二五八宫，各据一宫，各占一链， 这种”一元三点”结构，称为”宫链三星”） 4. 在G链构建不包含备选码（4）的、以7*为突点的三元组合： （4）-7*/136 得G6=4， G7/G9=27 5. 在第2链构建不包含备选码（8）的、以9*为突点的五元组合： （8）-9*/13456 得K2=8. B2=9 跟随有B2=9 B1=8 及 E1=9（三星点） 6. 在第5链构建不包含备选码（4）的、以7*为突点的三元组合： （4）-7*/136 得A5/B5=47 於是有A6=6 以上六个步骤，共求得七个椿点及六个跟随点，至此，解题方法 已进入直观法范畴了。 标准数独的另类解法：组合构建法 以下面的实例，说明组合构建的操作方法 你还记得那道来自芬兰的数独题吗？现在又被基哥提了出第5/7页 来。问题虽难，但使用组合构建法来解它，仍是游刃有余。请看下列详细过程： 1, 第四宫有D3/F1=67 (二元组合之自我排除） 2, 第四宫有两个289配以E1=25*9，就可构建一个三元组合： D2/E3/E1=289/289/25*9 应用时空倒置原理，把5*抽离出来， （被抽离的点称为突点，下同）就是D2/E3/E1=289/289/29=289， 於是F2=59中的9被排除了，得F2=5，返回来，E1=25*9中的5也被排 除了，得E1=29 。跟随有E8=5（由宫链三星而来） （由D6=5 F2=5及E8=5构成的一元三位格结构，称为宫链三星） 以上叙述，可用下列程式简单表达之： 第四宫 5*/289 得F2=5 3, 在第2链，把包含4的两个位格撇在一旁，剩余的三个位格刚好可以构建一个三元组合：D2/H2/K2=289/289/23*8 ，其中3*为突点，被抽离后就是D2/H2/K2=289，於是A2=249和B2=349中的289皆被排除，得 A2=4 B2=3，以上叙述可用下列程式简单表达之： 第2链（4）-3*/289A2=4 ,B2=3 跟随有C9=3， （由宫链三星而来） 第6/7页 4, 同样地，在H链有（5）-9*/12678得 H9=5 H1=9，并由此在左直三宫（一、四、七）中扩散， 除H2/K2=28外，共有17个位格被填充。 5,跟随着，由D2=9 D3=6，D链可全部填满。 6,由中直三