前言:
眼前你们对“c语言数独”大体比较关心,各位老铁们都想要了解一些“c语言数独”的相关内容。那么小编在网摘上搜集了一些有关“c语言数独””的相关文章,希望我们能喜欢,你们快快来学习一下吧!第五节 候选数法中区块的应用
一、候选数的相关知识
〔一〕什么是候选数?
1、所谓的候选数(Candidate),也叫可能数,就是指每个空白单元格中可以填入的数字。
2、候选数是指空白单元格中可能填入的数字,也就是说,虽然不知道哪个数字是正确的,但是,正确的填数一定在其中。
〔二〕如何发现候选数?
1、发现候选数的理论根据:
〔1〕数独的规则:将数字1-9填入剩余的空格内,使得每行,每列,每个粗线围成的3x3小九宫内,均出现数字1-9各一次。
〔2〕由于每行、每列和每个九宫格内填入的数字不能重复,根据这个要求,我们只要从{1,2,3,4,5,6,7,8,9}中去掉某个单元格所在行、所在列和所在九宫格中出现过的数字,就得到了这个单元格对应的候选数列表。
2、通过行来发现候选数
〔1〕在盘面中选择一个空白单元格
这里选择单元格R4C1,就是第四行与第一列相交的空白格。
〔2〕观察行中出现的已知数
单元格R4C1所在的行R4中的已知数:2、3、5、6、8、9
〔3〕寻找没有出现的数字
从1数到9,与已知数字作对比,找到没有出现的数字。
R4行中的没有出现的数:1、4、7
〔4〕填入候选数
3、通过列来发现候选数
〔1〕在盘面中选择一个空白单元格
这里选择单元格R4C1,就是第四行与第一列相交的空白格。
〔2〕观察列中出现的已知数
单元格R4C1所在的列C1中的已知数:1、4、5、8
〔3〕寻找没有出现的数字
从1数到9,与已知数字作对比,找到没有出现的数字。
R4列中的没有出现的数:2、3、6、7、9
〔4〕填入候选数
4、通过宫来发现候选数
〔1〕在盘面中选择一个空白单元格
这里选择单元格R4C1,就是第四行与第一列相交的空白格。
〔2〕观察宫中出现的已知数
单元格R4C1所在的第四宫B4中的已知数:2、3、5
〔3〕寻找没有出现的数字
从1数到9,与已知数字作对比,找到没有出现的数字。
B4宫中的没有出现的数:1、4、6、7、8、9
〔4〕填入候选数
4、通过行列宫来发现候选数
〔1〕在盘面中选择一个空白单元格
这里选择单元格R4C1,就是第四行与第一列相交的空白格。
〔2〕观察行列宫中出现的已知数
A、行中已知数:235689
B、列中已知数:1458
C、宫中已知数:235
〔3〕寻找没有出现的数字
从1数到9,与已知数字作对比,找到没有出现的数字。
R4行列宫中的没有出现的数:7
〔4〕填入候选数
5、特别说明
〔1〕通过不同的方法得到如下的结论
A、行的候选数:1、4、7
B、列的候选数:2、3、6、7、9
C、宫的候选数数:1、4、6、7、8、9
D、行列宫的候选数:7
上面四种候选数的集合都是对的。
〔2〕观察的方法不同,获得的候选数集合也不同。
〔3〕在实际的解题中,常常用行列宫观察法,三种观察方法放在一起,可以得到更少数量的候选数集合。
〔三〕候选数法的应用逻辑
1、使用候选数法解题的主要目的是删数,就是删除一个或多个候选数。
2、候选数法解题的过程就是逐渐排除不合适的候选数的过程
3、通过直观法可以得到某个空白格的候选数集,然后通过相应的技巧,删除不合适的候选数,这种推理过程是删数的过程,而不是“排数”的过程。
二、宫内区块排除法
〔一〕宫内区块对行列排除法(Pointing) ,简称宫内区块排除法。
〔二〕解法说明:在同一个小九宫格中,如果只有2个或者3个单元格包含同一个候选数,并且这2个或者3个单元格在同一行(同一列),则该候选数不能再出现在该行(该列)的其他单元格。
1、宫内行区块对行的排除:在某一九宫格中,当所有可能出现某个数字的单元格都位于同一行时,就可以把这个数字从该行的其他单元格的候选数中删除。
2、宫内列区块对列的排除:在某一九宫格中,当所有可能出现某个数字的单元格都位于同一列时,就可以把这个数字从该列的其他单元格的候选数中删除。
〔三〕宫内区块对行排除的应用实例
实例盘面
1、标记候选数
〔1〕有三种做题模式
A、直观法:直接通过空白的盘面上手就开始做题的方法。
B、候选数局部标记:在一部分单元格里标注出候选数来达到辅助做题的目的。
C、候选数全标:将全盘的所有空格的所有候选数都标注出来。
〔2〕建议采用全标的形式来解题
A、对于新手,采用全标的形式,观察更容易。
B、对于难题,用到的技巧一般都较难,直观层面一般都做不了,将候选数全部标注出来是非常有效的。
〔3〕在运用候选数法时,首先将全盘的所有空格的所有候选数都标注出来。
2、寻找宫内行区块
〔1〕选择数字
这里选择数字六
〔2〕寻找只有二个或者三个候选数的宫。
A、存在两个候选数的只有一个宫:B2。
B、存在三个候选数的有两个宫:B5和B7
〔3〕选择候选数在同一行的区块。
宫内区块只有是行区块或者是列区块,才是有效区块。
本例中,只有第二宫B2存在行区块,区块R2C56(6)是有效区块。
3、删除宫内行区块所在行的其他位置的候选数。
〔1〕删数的逻辑原理
A、根据数独规则,每个粗线围成的3x3小九宫内,均出现数字1-9各一次,所以B2宫中必然包含数字6。
B、在B2宫中,虽然不知道数字6最终填入哪一个空格,但是,一定在第二行R2中。
C、通过推理,B2宫中的数字6在区块R2C56中,根据数独规则,每一行没有重复的数字出现,所以,区块R2C56所在行的其他位置中,就不能再出现数字6了。
〔2〕删数。因此,在第二行R2中,数字6只能出现在区块R2C56中,其他位置的候选数6就可以删除了。
4、特别说明:
〔1〕宫内区块排除法的结果是删除候选数,而不是得到填入数。
〔2〕宫内区块排除法往往需要结合其他方法,才能逐步删除多余的候选数,最终只剩下唯一的候选数。这唯一的候选数就是最终的填入数。
〔四〕宫内区块对列排除的应用实例
初盘
1、寻找宫内列区块
〔1〕选择数字
这里选择数字七
〔2〕寻找只有二个或者三个候选数的宫。
存在两个候选数的有两个宫:B2和B4。
〔3〕选择候选数在同一列的区块
这里只有第二宫B2存在列区块。
2、删除宫内列区块所在列的其他位置的候选数。
由于数字7在区块R23C5中,所以,可以删除第五列中其他位置的候选数7。
这是删除候选数后的盘面。
3、利用宫内区块对行排除法继续删除候选数
〔1〕选择存在行区块的宫。
第四宫存在行区块R6C12
〔2〕删除宫内列行区块所在列的其他位置的候选数。
可以删除3个候选数7
这是删除候选数后的盘面
4、寻找存在唯一候选数的宫
第五宫存在唯一候选数7。
当一个宫中存在唯一的候选数时,这唯一的候选数就是应当填入空格中的数。
5、填入正确的数字
将数字7填入到单元格中。
6、特别说明
〔1〕候选数区块删减法也是比较常用的方法,它的目的是尽量删减候选数,而不一定要生成某一单元格的唯一解(当然,产生唯一解更好)。
〔2〕在某一行(列)中,当所有可能出现某个数字的单元格都位于同一九宫格中时,就可以把这个数字从该九宫格的其他单元格的候选数中删除。
〔3〕当只有唯一一个候选数时,这个候选数就是正确的解,是应当填入空白格的数字。
三、行列区块排除法
〔一〕行列区块对宫排除法(Claiming) ,简称行列区块排除法。
〔二〕解法说明:如果在一行(或列)中,某个数字的所有可能的格被限制在一个宫中,该候选数字将从该宫中的所有其他格中排除。
1、行区块对宫排除法:在一行上只有一个区块,除了这个区块,本行中再无其他格有与这个区块相同的候选数,那么这个区块中,必有一个候选数最终成为正确解,所以能删除行区块所在宫中的,其他单元格中相同的候选数。
2、列区块对宫排除法:在一列上只有一个区块,除了这个区块,本列中,再无其他格有与这个区块相同的候选数,那么这个区块中,必有一个候选数最终成为正确解,所以能删除列区块所在宫中的,其他单元格中相同的候选数。
〔三〕行区块对宫排除的应用实例
实例初盘
1、寻找行区块
〔1〕这里选择数字1。在实际的解题中,往往从数字1开始观察。数字1观察完之后,观察数字2;这样依次从1观察到9。
〔2〕画出只有两个或三个候选数的行。
2、寻找位于宫中的区块
第二行和第八行的区块符合要求,都位于某个宫中。
这里选择第二行来举例。
3、删除宫中其他位置的候选数
〔1〕删数的逻辑原理
A、根据数独规则,每行中均出现数字1-9各一次,所以R2行中必然包含数字1。
B、在第二行R2中,虽然不知道数字1最终填入哪一个空格,但是,一定在区块R2C789中。
C、根据数独规则,每一宫不允许有重复的数字出现,所以,区块R2C56所在宫的其他位置中,就不能再出现数字1了。
〔2〕删除行区块所在宫的其他位置的候选数。
可以删除两个候选数。
这是删除完成后的盘面。
〔四〕列区块对宫排除的应用实例
实例盘面
1、寻找列区块
〔1〕选择一个数字
这里选择数字7
〔2〕寻找只有两个或者三个候选数的列
一共有三列。
2、寻找位于一个宫中的区块
只有第四列C4符合要求,列区块R4C46位于第五宫B5中。
3、删除宫中其他位置的候选数
可以删除三个候选数
这是删数后的盘面
4、寻找存在唯一候选数的行列宫
经过观察,第八宫B8存在唯一的候选数
5、填入正确的数字
R8C6=7
标签: #c语言数独