数独方法及技巧(小图)(共59页).doc

上传人:飞****2 文档编号:13530019 上传时间:2022-04-29 格式:DOC 页数:59 大小:1.24MB
返回 下载 相关 举报
数独方法及技巧(小图)(共59页).doc_第1页
第1页 / 共59页
数独方法及技巧(小图)(共59页).doc_第2页
第2页 / 共59页
点击查看更多>>
资源描述

《数独方法及技巧(小图)(共59页).doc》由会员分享,可在线阅读,更多相关《数独方法及技巧(小图)(共59页).doc(59页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精选优质文档-倾情为你奉上数独技巧(Sudoku Strategies)数独快速入门(上篇)范例一: 在左边第一个九宫格里,哪格可以放数字, 先看到再第一列和第二列里已经有了数字, 所以很明显了,除了棕色格子之外,上面两列格子已经不能放了。 范例二: 换个进阶范例来看看, 已知第一列和第二列不能放,但仅就第三列而言,的旁边似乎都可以放的样子, 但再看看被颜色标示的第三行, 看到第三行有之后,就知道棕色格子应该放。 范例三: 来个更进阶点的,想想左上角第一个九宫格里,哪一格可以放, 再看 先看看前两列,应该不能放, 看被颜色标示的第二行与第三行,又是不能放, 很显然的,就只有棕色格子能放。 范例

2、四: 再看看这个重要范例,想想左上角第一个九宫格里,哪格可以放, 先看看被颜色标示的第二列, 再看看被颜色标示的第二行, 经过分析后可知要放在这棕色格子。 范例五: 换个轻松点的范例, 看看第一列,数字有哪些, 显而易见的就是缺。 数独快速入门(中篇)范例一: 看看这个比上篇难的,想想能放在哪里呢, 被颜色标示起来的第一列和第一行已经不能放了, 就左上角的九宫格而言,在红色标示区域似乎是可以摆的, 但在这里而言,似乎无法决定放在两格红色区域的哪一格, 所以,可以先看看邻近的九宫格,发现到棕色格子能放喔,这时候就不用怀疑马上写下。 范例二: 看看这个有技术性的,想想能放在哪里, 看到黄色的第一列

3、已经有,所以不能再放了, 就中央的九宫格而言,合理的推论,一定是在第二列中央红色三格的其中之一了, 既然知道第二列的情况,再考虑黄色区域后, 那么可以先确定右方九宫格的必然放在这棕色格子。 范例三: 由上篇的概念再进阶,考虑这上面三个九宫格,看看能否决定的位置, 黄色标示的第三行已先被排除, 就第一个九宫格而言,一定在红色区域, 就黄色标示区域来看,已不能再放了, 这时可以马上先决定右上九宫格里的棕色格子是能放的啦。 范例四: 看到这左上方九宫格的第一列,就可以马上知道缺了哪两个数字, 是不是已经看出红色格子不是就是了, 但是又看到第二行有,所以很轻松知道左上棕色格子一定是, 接下来就确定在红

4、色格子了。 范例五: 先看看这第一列, 左上方的九宫格里,第一列绝对有、, 再考虑到第一行黄色区域,看到有和, 这下就可确定绝对放在左上角的棕色格子。 数独快速入门(下篇)范例一: 来看看这个高级进阶例子,可以先把眼光放在第一列和第一行, 看到在黄色区域里都有和,所以此黄色区域已经不能再放和了, 这时可以考虑到左上九宫格里的红色格子能放和, 再看到第一列和第三列的黄色区域,这黄色区域里已经不能放, 在左上九宫格里,能放的只有红色与棕色格子,但红色格子将会被和所占据,所以能确定棕色格子必然为。 范例二: 看看左上方九宫格里,能否由些微线索决定的位置, 首先,看到第一列后先排除、,又因左上方九宫格

5、里有、,再排除这三个数字,这下,在左上方九宫格的第一列,只剩下、可以填,然后,又看到第一行有和,所以,棕色格子必然不会是和,那么,就只剩下可以填入啦! 直观法(Direct Elimination Techniques)经常在报章杂志上看到的数独谜题,一般就算再难都可以用直观法来解决。它不需要象那样在每个空白的单元格中用铅笔填上一大堆候选数。你只要有相对锐利的眼光和一定的逻辑分析能力,就可以准确地把空余的数字逐个填出来。实际上,直观法就是对数独游戏规则的充分利用。虽然它并不如那样强大,但通常要想体会解决数独谜题的乐趣,使用直观法却是不二之选。直观法(Direct Elimination Tec

6、hniques)具有以下的特点:轻松上手。 即便是数独新手,在拿到谜题的一刹那,就可以用直观法来解题了。 无需辅助。 在纸上解题时一般只需要一支钢笔就可以。因为是通过推理和逻辑分析来确定哪个格填哪个数,或是哪个数填在哪个格里,所以基本不需要猜测。容易掌握。 对于直观法(Direct Elimination Techniques)中应用的各种算法,可以很快掌握并应用于实际中。 相对简单。比起,它的算法相对比较简单,当然能解决的谜题的复杂度也相对要低。在直观法(Direct Elimination Techniques)中,常用的算法包括:1. 2. 3. 4. 5. 6. 1. 这应该算是中最简

7、单的方法了。基本上只需要看谜题,推理分析一概都用不上,这是因为要使用它所需满足的条件十分明显。同样,也正是因为它简单,所以只能处理很简单的谜题,或是在处理较复杂谜题的后期才用得上。 我们先来看一个例子:在上图中,观察行B,可以看到除了B3外,其他所有的单元格中都已有了数字,根据数独游戏的规则,即每行,列或区块中不能有重复的数字,则B3中能填入的数字只能是行B中所未出现过的,也就是数字3。所以可以毫不犹豫地在B3中填入3。这就是单元唯一法在行中的应用。这里的单元(Unit, or group),指的是行,列或区块。所以有三种情况:当某行有8个单元格中已有数字,或 当某列有8个单元格中已有数字,或

8、 当某区块有8个单元格中已有数字。 无论是哪种情况,我们都可以很快地在该行,列或区块剩余的空格中填入该单元还未出现过的数字。下面是单元唯一法在列中的应用: 在第7列中,只有F7未填入数字,且这一列中数字8还未出现过。所以F7 = 8。在区块中也是一样:在起始于D7的区块中,只有E7还未填入数字,且这个区块中数字5还未出现过,所以可以马上在E7中填入5。单元唯一法在解题初期应用的几率并不高,而在解题后期,随着越来越多的单元格填上了数字,使得应用这一方法的条件也逐渐得以满足。 2. 单元排除法是中最常用的方法,也是在平常解决数独谜题时使用最频繁的方法。使用得当的话,甚至可以单独处理中等难度的谜题。

9、使用单元排除法的目的就是要在某一单元(即行,列或区块)中找到能填入某一数字的唯一位置,换句话说,就是把单元中其他的空白位置都排除掉。它对应于中的。那么要如何排除其余的空格呢?当然还是不能忘了游戏规则,即行,列或区块中不能有重复的数字。从另一个角度来理解,就是如果某行中已经有了某一数字,则该行中的其他位置不可能再出现这一数字。如果某列中已经有了某一数字,则该列中的其他位置不可能再出现这一数字。如果某区块中已经有了某一数字,则该区块中的其他位置不可能再出现这一数字。单纯理解上面的规则还是不足以解题,但是在实践中这些规则却可以交叉使用。在实际解题过程中,应用最多也最方便的是对区块的单元排除法,我们可

10、以先看下面这个例子:对于起始于D1的区块,其未填数字的空格有6个之多,如果不使用单元排除法,是很难为这一区块填入任何数字的。这时我们就可以利用行,列及区块的相互关系,即一个单元格既在某一行上,也同时在某一列上以及某一区块中的这种关系来解题。观察数字9在谜题中的位置,可以看到它出现在B2,A4,C7,D8,I1和H9。而这些位置中,只有B2,D8和I1与起始于D1的区块有关联。因为I1=9,它所在的第1列上的其他单元格中不可能再出现9, 而区块中的D1和F1正好也在第1列上,所以这两个单元格填入9的可能性被排除。同理,因为B2=9,它所在的第2列中的其他单元格不可能再填入9,而区块中的D2和E2

11、也正好在第2列上,因此,这两个单元格填入9的可能性也被排除掉了。再看行D,因为D8=9,所以该行上的D1,D2和D3也不可能再填入9,而这些单元格正好也在起始于D1的区块中。所以,这个区块中能填入数字9的位置就只剩下了E3,这样就通过排除法找到了答案,即E3=9。下面再看一个在行中使用单元排除法的例子:在谜题中观察数字4和行H,在行H有5个空单元格无法确定数字,但是C3位置上的4使得其所在的第3列中的其他单元格上不能再出现4,所以H3不能填入4。I4上的4使得其所在的区块中也不能再填入4,它帮助行H排除了两个单元格H4和H6,而第8列上的E8中的数字4使得同样位于这一列上的H8也排除了填入4的

12、可能。这样,行H中能填入4的位置就只剩下H9了。在列中也可以使用单元排除法:在第7列中,我们试图确定能填入数字1的位置。在行B中,数字1已经出现在B2上,所以B7不可能再填入数字1了。而位于D8的数字1也使得F7排除了填入数字1的可能,因为它们位于同一区块中。这样,第7列上就只有A7能填入数字1了。 通过上面的示例,可以看到,要对区块使用单元排除法,需要观察与该区块相交的行和列。要对行使用单元排除法,需要观察与该行相交的区块和列。要对列使用单元排除法,需要观察与该列相交的区块和行。 在实际解题过程中,行,列和区块之间的关系并不象上面这些图中所示的那么明显,所以需要一定的眼力和细心观察。一般来说

13、,先看哪个数字在谜题中出现得最多,就从哪个数字开始下手,找到还未填入这个数字的单元(行,列或区块),利用已填入该数字的单元格与单元之间的关系,看能不能排除一些不可能填入该数字的位置,直到剩下唯一的位置。如果害怕搞不清已经处理过哪些数字的话,可以从数字1开始,从左上角的区块开始一直检查到右下角的区块,看能不能在这些区块中应用单元排除法。然后测试数字2,以此类推。 单元排除法是应用得最多的,虽然在实践中经常会因为粗心而漏掉很多使用这一方法的机会,但只要勤加练习,就可以运用自如。 3. 区块排除法是中进阶的技法。虽然它的应用范围不如那样广泛,但用它可能找到用无法找到的解。有时在遇到困难无法继续时,只

14、要用一次区块排除法,接下去解题就会势如破竹了。区块排除法实际上是利用区块与行或列之间的关系来实现的,这一点与颇为相似。然而,它实际上是一种模糊排除法,也就是说,它并不象那样利用谜题中现有的确定数字对行,列或区块进行排除,而是在不确定数字的具体位置的情况下进行排除的。这句话听起来似乎不好理解,让我们先从一个例子入手,看看区块排除法是怎么应用的。对于上面这个谜题,用基本的或是都无法再找到解。这时可以尝试使用区块排除法。 我们先从填入数字最多的区块着手,也就是起始于G4的区块,该区块中只有H6和I5为空,且剩余数字1和2还未填入。这样,我们可以想办法确定这两个数字的位置。观察全局,可以看到D2=2,

15、根据单元排除法,它所在的第2列上不能再出现数字2,所以H2和I2将不能填入2,这使得起始于G1的区块中数字2可能出现的位置仅剩下I1和I3,见下图:虽然我们无法确定2在起始于G1的区块中的确定位置,但幸运的是,能填入2的位置正好都在行I上,也就是说,无论2在I1还是在I3,行I的其他单元格中将不可能再出现数字2,所以可以毫不犹豫地排除在I5填入2的可能性,这样,对于起始于G4的区块而言,能填入数字2的位置就只剩下H6了。所以H6=2。接下来,当然毫无疑问,利用,在I5填入数字1。先小结一下上面的求解方法:解题时,实际上是在对目标区块(主区块)有影响的区块(辅助区块)中应用单元,使辅助区块满足某

16、些条件并能参与对主区块的数字排除。实际应用中,可能出现下面四种情况:当某数字在某个区块中可填入的位置正好都在同一行上,因为该区块中必须要有该数字,所以这一行中不在该区块内的单元格上将不能再出现该数字。当某数字在某个区块中可填入的位置正好都在同一列上,因为该区块中必须要有该数字,所以这一列中不在该区块内的单元格上将不能再出现该数字。当某数字在某行中可填入的位置正好都在同一区块上,因为该行中必须要有该数字,所以该区块中不在该行内的单元格上将不能再出现该数字。当某数字在某列中可填入的位置正好都在同一区块上,因为该列中必须要有该数字,所以该区块中不在该列内的单元格上将不能再出现该数字。其中,两种情况相

17、对常见,也比较容易判断。上面的示例就是情况。下面我们会看到情况的例子:虽然在起始于A7的区块中,未填入数字的空单元格多达4个,但我们还是可以轻松地确定数字5的位置。这是因为在起始于G7的区块中,我们欣喜地发现数字5可能出现的位置正好都在第8列上,这时5的确切位置已经不重要了,因为它已经满足了上面介绍的第2种情况的条件,因此可以参与对起始于A7的区块进行数字排除了。在它的影响下,A8和B8中填入数字5的可能性已经不存在,因为它们都在第8列上。这样,在起始于A7的区块中,数字5能填入的位置只剩下A9和C9了。这时,我们再利用单元排除法,通过A4位置上的数字5再消除其所在行A上的A9,最终得到能填入

18、5的唯一位置C9。下面看几个比较少见的例子在行C上,数字3的位置可以通过下面的方法来确定:先看行B,利用单元排除法,通过H2和F3位置上的3进行列排除,得到行B中能填入3的位置为B4和B5。碰巧的是,这两个单元格都在起始于A4的区块中,这时已经满足了上述情况的条件。利用单元排除法的区块排除,则行C上的C4和C5都不能再填入3;再加上F3的列排除的共同努力,最终确定数字3在行C上的唯一位置就是C1。第种情况的例子如下:在这个示例中,只是使用单元排除法和单元唯一法到这一步就继续不下去了。要想求得数字8在第6列的位置,就必须要借助区块排除法。先看第4列,通过位于C3和I8的数字8的行排除,使8在第4

19、列可能填入的位置只剩下D4和F4,而这两个单元格正好都在起始于D4的区块中。因为第4列不能没有数字8,而数字8如果填在区块中的其他位置(如D6,E6或F6)时将迫使D4和F4上不能再填入8,这样会导致第4列没有数字8。因此,第6列中的D6,E6和F6能填入数字8的可能性被排除。这样第6列中就只剩下B6能填入8了。实际解题过程中,还会碰到比较复杂的情况,看下面的谜题:你能确定数字3在起始于A1的区块中的位置吗?先看位于C5的数字3,它不仅排除了同一行中C1和C3中填入3的可能性,也同时排除了同一行中C8和C9填入3的可能性,这使得在起始于A7的区块中,能填入3的位置只剩下B8和B9,见下图:利用

20、区块排除法,在起始于A7的区块中,无论3在B8还是B9,行B中的其他位置都不能再填入3,所以B1,B2和B3都被排除。于是,在起始于A1的区块中,能填入3的位置仅剩下A1和A2了。但至此我们还无法确定3的准确位置,这时我们还要借助于其他的辅助区块来进一步排除。观察起始于D1的区块,利用D7位置上的3排除同一行的D1,以及用G3位置上的3排除同一列的E3和F3,使区块中可能填入3的位置只余E2和F2,刚好这两个位置都在第2列中,符合上面介绍的第2种情况,于是可以把A2也排除掉。最后,我们就可以很肯定地在A1中填入数字3了。这个例子同时使用了多个辅助区块同时参与排除。在实际使用中虽然这种情况并不常

21、见,但却也不少见。关键在于如何能正确识别并恰当应用区块排除法。相信通过大量的练习并勤于分析思考,这种方法就可以运用自如,得心应手。下面是其他的一些例子,可以帮助更好地理解并掌握这种技法:4. 唯一余数法是中较不常用的方法。虽然它很容易被理解,所以说明这个方法不需要很大篇辐,然而在实践中,却不易看出能够使用这个方法的条件是否得以满足,从而使这个方法的应用受到限制。与相比,唯一余数法是确定某个单元格能填什么数的方法,而是确定某个数能填在哪个单元格的方法。另外,应用的条件十分简单,几乎一目了然。与相比,唯一余数法相当于。虽然是中最简单且应用最容易的方法,但在 中却正好相反。先看一个例子:对于单元格G

22、9应该填入什么数字,就算你把前面介绍的所有直观技法都用上,也不得而知。然而,我们通过观察它所在的行,列和区块,可以发现除了数字2以外,1到9中其他的数字都出现了,其中行G中包含了7,6,9,5,3和8,第9列中包含了数字5,8,7和1,起始于G7的单元格中包含了3,8,4,7,5和1。这样,如果G9不填入数字2,就一定会违反游戏“行,列或区块不能出现重复数字”的规则。所以G9中的数字一定是2总结一下,就是如果某一单元格所在的行,列及区块中共出现了8个不同的数字,那么该单元格可以确定地填入还未出现过的数字。怎么样,很简单吧,但在实践中却不那么容易识别。看下面的谜题: 你能看出来对哪个单元格应用唯

23、一余数法吗? 还有这个谜题:答案分别是E6=9和I7=9。 一般来说,只有在使用基本的排除方法都失效的情况下,才试着使用这个方法来解题。5. 组合排除法和一样,都是中进阶的技法,但它的应用范围要更小一点。一般情况下,基本没有机会用到这种方法解题,所以要找到相应的例子也都很困难。当然,如果你希望优先以这个技法来解题的话,还是能碰到很多能符合使用组合排除法条件的情况。组合排除法,顾名思义,要考虑到某种组合。这里的组合既包括区块与区块的组合,也包括单元格与单元格的组合,利用组合的关联与排斥的关系而进行某种排除。它也是一种模糊排除法,同样是在不确定数字的具体位置的情况下进行排除的。下面先看一个例子:对

24、于上面这个谜题,你能确定数字6在起始于G4的区块中的位置吗?要想获得正确的答案初看起来有些困难。因为虽然在G9和H3已经存在了两个6,但是利用它们只能行排除区块中的G4和H6两个单元格,还是无法确定6到底是在I4还是在I5中。这时候,组合排除法就派上用场了。现在撇开起始于G4的区块,先看它上面的两个区块,即起始于A4和D4的区块。这几个区块的共同特点是占有同样的几列,也就是第4列至第6列,因此它们之间的数字会相互直接影响。对于起始于A4的区块,利用A1处已有的数字6进行行排除,可以得到这个区块中可能填入6的位置只剩下两个:B5和C6。 对于起始于D4的区块,利用E7处已有的数字6进行行排除,可

25、以得到这个区块中可能填入6的位置也剩下两个:F5和F6。 这时,我们仍无法确定6在这两个区块中的确切位置。但不妨对可能出现的情况作一下分析:假设在起始于A4的区块中,B5=6,则同一区块中的C6必不为6,而且B5还将列排除F5,这样在起始于D4的区块中,只有F6=6。假设在起始于A4的区块中,C6=6,则同一区块中的B5必不为6,而且C6还将列排除F6,这样在起始于D4的区块中,只有F5=6。简单地说,只有两种可能:B5=6且F6=6,或者C6=6且F5=6。决不会再出现其他的情况。但无论是其中哪一种情况,第5列和第6列都会有确定的6出现在这两个区块中,也就是说,第5列和第6列的其他位置不可能

26、再出现数字6。这样,原本无法肯定的6在起始于G4区块中的位置,一下子就变得明确了。利用起始于A4和D4的区块对起始于G4的区块进行列排除,可以把I5排除掉,这样,就只剩下I4可以填入6了。小结一下,组合排除法的要满足的条件如下:如果在横向并行的两个区块中,某个数字可能填入的位置正好都分别占据相同的两行,则这两行可以被用来对横向并行的另一区块做行排除。如果在纵向并行的两个区块中,某个数字可能填入的位置正好都分别占据相同的两列,则这两列可以被用来对纵向并行的另一区块做列排除。 让我们再看一个例子:要想确定数字1在起始于D4的单元格中的位置,我们将设法借助于其横向上相邻两个区块的帮助。利用I2的列排

27、除,我们可以把起始于D1的区块中的E2和F2排除掉,这样,这个区块中能填入1的位置剩下D1,D3和E1。 利用H7的列排除,可以把起始于D7的区块中的E7和F7排除掉,再利用A9的列排除,可以把这个区块中E9和F9排除掉,这样,这个区块中能填入1的位置只剩下D8和E8。虽然在起始于D1的区块中,能填入1的位置多达3个,但是它们正好只分布在行D和行E上,而且在起始于D7的区块中能填入1的位置所占据的也是这两行。最终1的位置只可能有三种情况:D1=1且E8=1;或者D3=1且E8=1;或者E1=1且D8=1。无论是哪种情况,行D和行E都会有确定的1出现在这两个区块中,也就是说,这两行的其他位置不会

28、再出现1。于是,借助于这两个区块的行排除,我们可以把起始于D4的区块中的D4和D6排除掉,再利用G4位置的列排除,最终确定1的位置在F6。下面是其他一些使用组合排除法的例子:在实践中,组合排除法的实际应用机会不如多。但是,掌握这一技法无疑可以大大提高求解谜题的灵活性,从而增加解题的乐趣。6. 矩形排除法虽然浅显易懂,但一般在实际解题的时候应用得却比较少。这是因为即使谜题中存在满足使用这一方法的情况,也很难直接看出来。然而,相对而言,在解题过程中倒是能有更多的机会用上矩形排除法。下面先看一个例子:对于这个谜题,如果不用矩形排除法是无法继续下去的。我们将通过讲解这种技法,从而找到数字8在起始于G1

29、的区块中的位置。乍看之下,好象一筹莫展。因为B2和E3上的8只能列排除左下角这个区块中的G2, H2,G3和I3这4个单元格,这时仍剩下两个单元格G1和H1无法确定。让我们先来留意一下第6列,这一列中暂时没有8,那么8可能会填入哪几个单元格中呢?首先,B2中的8行排除了B6,而E3和F4中的8又分别行排除了E6和F6。这样,能填入8的位置就只剩下C6和I6了。见下图:同样,对于第9列,由于F4的行排除,F9不可能填8,所以这一列能填入8的位置也就只剩下C9和I9了。凑巧的是,这两列中能填入8的位置都在同样的两行上,即行C和行I。这时就为我们应用矩形排除法创造了前提条件。如果第6列中C6=8,那

30、么I6和C9一定不能是8。而第9列这时就只剩下I9能填入8了;又或者如果第6列中I6=8,那么C6和I9一定不能是8,而第9列就只剩下C9能填入8了。不可能再有第3种情况。所以,要么C6=8且I9=8,要么I6=8且C9=8。但无论是哪种情况,不难发现,行C和行I都已填入了8,所以这两行的其他位置不可能再填入8。我们正好可以利用这一点来进行排除。 观察起始于G1的区块,我们已经知道现在只剩下G1和I1两个单元格无法确定了,通过上面的分析,利用矩形排除法排除位于行I上的I1,就可以确定数字8一定在G1上。总结一下,使用矩形排除法的条件如下: 如果一个数字在某两行中能填入的位置正好在同样的两列中,

31、则这两列的其他的单元格中将不可能再出现这个数字;如果一个数字在某两列中能填入的位置正好在同样的两行中,则这两行的其他的单元格中将不可能再出现这个数字。让我们再来看一个例子:做到这一步时,不用矩形排除法的话恐怕是走投无路了。这次还是要在起始于G1的区块中找到数字4的位置。但我们无法确定4究竟在G2还是G3呢? 先要找找看有没有满足矩形排除法条件的情况存在。观察行B,在这一行中,由于C5的区块排除,B4和B5都不能为4,再加上H8列排除了B8,这样行B中能填入4的位置包括B1和B3。 再看行F,由于D6的列排除,使得F6不能填4,所以行F中能填入4的位置只有F1和F3。 幸运的是,行B和行F中能填

32、入4的位置正好都位于同样的两列上,即第1列和第3列。根据上面矩形排除法的规则,第1列和第3列中不在行B和行F上的单元格中不能填入4,所以G3不能为4。这样,起始于G1的区块中就只有G2能填入4了。 下面是应用矩形排除法的其他一些例子,希望可以帮助大家快速掌握这种方法: 矩形排除法可以说是中最困难的技法,因为当前的谜题即使满足应用这一方法的条件,也实在太难发现了。一般情况下,尽量先使用其他相对简单的。如果最后连矩形排除法都用上还是无法解题,你可能就需要尝试候了。候选数法(Candidates Elimination Techniques)对于解决数独谜题,最常使用的方法就是和候选数法。在谜题相对

33、简单时,可以取得相当好的效果。但是如果谜题比较复杂,的效果就十分有限,即使通过试探性填数也不一定能够解题,而这时候选数法却可以很好地发挥作用。在对数独谜题求解的电脑程序的设计上,候选数法也因为高效易实现而被广泛应用。如果用候选数法来解题,必须首先准备一张如下图所示的候选数栅格表: 初始化时,每个单元格中都包含了1至9所有的数字,它表示该单元格中在解题时还可以选择填入的数字。很明显,不在候选数中的数字是不能够填入该单元格中的。如果某一单元格中已填入一个确定的数字,则根据数独游戏的规则,即该单元格所在行,列及区块中都不能再出现这个数字,则该数字应从这些单元格中的候选数字中去除。对于下面的这个谜题:

34、 每填入一个数字时,都要将该单元格中的候选数全部删除,同时扫描其所在行,列和区块,看它们所覆盖的单元格上的候选数中有无该数字: 如果有,就把该数字从候选数中删除:同理,填入谜题中其他的初始数字,并删除这些数字各自所在行,列和区块候选数中的该数字,可以得到下面的候选数栅格表: 注意,填入数字的顺序与最终的候选数栅格表无关。这时,我们发现每个单元格中的候选数已经比最初少了许多,真是一个令人兴奋的开始。随后,我们将辅以各种候选数删减技巧,进一步减少候选数的个数,当某单元格中只剩下唯一的候选数时,该单元格就得到了它的唯一解。细心的朋友已经发现,在上面的候选数栅格表中,单元格I1中已经剩下唯一候选数1,

35、这时我们就可以通过来解题了。 在候选数删减法中,常用的算法包括:1.2.3.4.5.6.7.8.9.10.11.12.13.14.1.这是中最简单的一种方法,就是扫描候选数栅格表,如果哪个单元格中只剩下一个候选数,就可应用显式唯一法,在该单元格中填入这个数字,并在相应行,列和区块的候选数中删除该数字。 在下面的图中:单元格I1有唯一的候选数1,则毫无疑问地把数字1填入该单元格中,并扫描其所在行,列和区块的候选数中有无数字1:如果有,则把1从这些单元格的候选数中删除:显式唯一法虽然简单,但却是最有效的之一;尤其在谜题相对简单时,有时单单使用显式唯一法就可以解题。2.见文知义,隐式唯一法也是唯一候

36、选数法的一种,但它肯定不如那样显而易见。我们知道,如果某一个单元格中只有一个候选数字,这时可以毫不犹豫地填入它;但是有没有这种情况,即使某个单元格中有不止一个候选数字,我们也可以轻易地推断出这个单元格的正确解答呢? 考虑下面的情况:在第7列中,单元格B7中虽然有多个候选数,但观察整列后我们发现,只有这个单元格中有数字6。根据数独游戏的规则,每一列中都必须要有从1到9的所有数字,而同时6却只能出现在这个单元格中,所以很显然B7=6。当然,别忘了把6从B7所在的行,列和区块中删除。同样,在下图中:观察行B后我们发现,只有单元格B8中含有数字7。同理,B8是该行中唯一可以填入数字7的单元格,所以B8

37、=7。另外,我们还要扫描相应行,列和区块,删除其中的候选数7。当然,这种隐藏的唯一候选数也可能躲在区块中,看下图:对于起始于A1的区块而言,数字8只出现在单元格A2的候选数中,所以A2=8。从相应行,列和区块,删除其中的候选数8。 隐式唯一法是的有力补充,很多稍复杂的题都可以在这两种方法的交替使用下得以解决。 3.应用和只能解决简单的谜题,遇到稍复杂的谜题,还是要靠其他的方法。区块删减法也是比较常用的方法,它的目的是尽量删减候选数,而不一定要生成某一单元格的唯一解(当然,产生唯一解更好)。区块删减法是利用区块中的候选数和行或列上的候选数之间的交互影响而实现的一种删减方法,它分为两种情况:区块对

38、行或列的影响 观察下图:可以看到在起始于A7的区块中,数字9只出现在A9和C9的候选数中,更巧的是,A9和C9正好都在同一列上,即第9列。这时就可以应用区块删减法了。具体地说,在起始于A7的区块中,数字9只能填在A9或是C9中,又因为这两个单元格都在第9列上,所以无论数字9填在哪个单元格中,第9列的其他单元格中都不能再填数字9,所以要把9从它们的候选数中删除。在上图中,位于第9列的单元格E9中的候选数9将被删除。下图说明的是区块对行的影响:在起始于G1的区块中,只有H2和H3可以填入数字3,而这两个单元格正好都在行H中。同样的道理,在这个区块中无论数字3填入H2还是H3,行H中的其他单元格中都

39、不可能再填入3,所以在单元格H4,H6和H7的候选数中的3将被删除。行或列对区块的影响 与“”相近但却不同,“行或列对区块的影响”着重于先对行或列进行分析。观察下图:在第5列中,8只出现在D5和F5的候选数中;也就是说,第5列中的数字8只能填入这两个单元格其中的一个。碰巧的是,这两个单元格正好都位于起始于D4的区块中,结果使得这一区块中的数字8也不能填入区块的其他单元格中,所以D4,E4,E6和F6的候选数中的8将被删除。 同样,下图说明了行对区块的影响: 在行E中,只有E5和E6能填入数字6,而这两个单元格又刚好都在起始于D4的区块中,所以该区块中的其他单元格内不能再填入数字6,即6将从单元

40、格D5和F5的候选数中删除。总结一下区块删减法的条件,就是在某一区块中,当所有可能出现某个数字的单元格都位于同一行时,就可以把这个数字从该行的其他单元格的候选数中删除。在某一区块中,当所有可能出现某个数字的单元格都位于同一列时,就可以把这个数字从该列的其他单元格的候选数中删除。 在某一行(列)中,当所有可能出现某个数字的单元格都位于同一区块中时,就可以把这个数字从该区块的其他单元格的候选数中删除。虽然区块删减法应用比较广泛,但是还是要先给大家泼盆冷水。因为在很多时候,即使满足了区块删减的条件,也可能会发生没有候选数可以删减的情况,让人空欢喜一场。其实,这个问题对其他稍复杂的方法都是普遍存在的。

41、4.显式数对法在很多谜题中都可以得到应用,它的条件比较容易满足,而且显而易见。先看下图:在行E中,E2和E8中候选数只有两个,且都是2和3,即构成一个2, 3的数对。这使得该行中其他单元格中不能再出现2或3。为什么呢,因为假设E2=2,则E8一定要填3;反之,假设E2=3,则E8则一定填2,不会再出现其他的情况。所以2和3必然不能成为该行中其他单元格的候选数。这样,E3,E4和E5的候选数中都不能再有2和3。对于列也是这样:在第3列中,数对6, 8只出现且都出现在A3和H3中,所以其他单元格里都不能再有这两个数字。这样,C3的候选数中将删除6和8,而F3的候选数中将删除8。同样,别忘了还有区块

42、: 观察起始于G4的区块,可以发现G5和I4中含有数对2, 4,这样,该区块中其他的单元格里都不能再有数字2和4,这次受影响的有4个单元格,分别是G4,H4,I5和I6。总结一下显式数对的条件,也就是,在一个行,列或区块中,如果有两个单元格都包含且只包含相同的两个候选数,则这两个候选数字不能再出现在该行,列或区块的其他单元格的候选数中。5.显式三数集法并不如那样常见,但它们的原理却很相似。要求同样的2个数字都出现在某行,列或区块的2个单元格中,且这2个单元格的候选数不能包含其他的数字。同样,显式三数集法要求的是3个数字要出现在3个位于同一行,列或区块的单元格中,且这3个单元格的候选数中不能包含

43、其他数字。但不同的是,显式三数集法不要求每个单元格中都要包含这3个数字。例如,对于数字集2,4,5,如果在某行,列或区块中有3个单元格的候选数分别为下面几种情况时,都可应用显式三数集法,即3个单元格的候选数集可以分别为:2, 4, 5 2, 4, 5 2, 4, 5,或 2, 4 4, 5 2, 5,或 2, 4, 5 2, 5 4, 5,或 2, 4, 5 4, 5 2, 4, 5,或 . 也就是说,要形成显式三数集,则必须要有3个在同一行,列或区块中的单元格,每个单元格中至少要有2个候选数,且它们的所有候选数字也正好都是一个三数集的子集。由于这个三数集中的3个数字正好可以分别填入这3个单元

44、格中,所以该行,列或区块中其他的单元格中不可能再填入这3个数字。但要注意的是,下面的这种情况不是显式三数集:2, 4, 5 2, 4 2, 4其中2, 4和2, 4可应用,所以第一个候选数集2, 4, 5将只能剩下候选数,这时就可应用了。看下图:在行D中,D1,D7和D8中分别包含候选数集3, 5, 9,3, 5, 9和5, 9,根据上面的知识,可以判断出这是一个显式三数集,因此数字3,5和9不可能再出现在行内其他的单元格中,所以D4和D6的候选数中的3,5和9将被删除。下面是列中的显式三数集的例子: 在第2列中,G2,H2和I2中分别包含候选数集2, 6,2, 5和2, 5, 6,所以数字2,5和6只能在这三个单元格中分别填入,而不可能填入到该列的其他单元格中,因此A2,B2和E2的候选数中的2,5和6将被删除。 细心的朋友可能还发现,G2,H2和I2不仅都在第2列中,而且又恰好都在起始于G1的区块中,对于数字5,已经符合的条件,可惜的是,第2列中其他单元格的候选数中都没有5可以删减。 同样,显式三数集还有在区块中的可能: 在起始于D7的区块中,D8,D9和E9中分别包含了候选数集

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 教案示例

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁