网站首页
手机版

算法实践数独的基本解法 数独的解答

更新时间:2024-06-22 09:02:00作者:佚名

算法实践数独的基本解法 数独的解答

数独(Sudoku)是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9乘以9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1到9,不重复。 每一道合格的数独谜题都有且仅有唯一答案,推理方法也以此为基础,任何无解或多解的题目都是不合格的。

  

  数独的基本解法就是利用规则的摒弃法。每一行称为数独的行,每一列称为数独的列,每一个小九宫格称为数独的宫。数独的基本规则就是每一行、每一列、每一宫中,1到9这9个数字都只出现一次。那些只能填一个数字的空白单元格,我们称之为唯一数单元格。

  

  解题的顺序,就是从唯一数单元格开始,由于唯一数单元格只能填一个数,故先在这个单元格里填数。在这个单元格里填数,由于规则的定义,那么这个单元格所在的行、所在的列、所在的宫的其他单元格就不能再填这个数了。这些单元格能填的数的可能性就少了。有可能会产生新的唯一数单元格。

  

  在相当的一些的数独题目中,从唯一数单元格开始填数,不停的在唯一数单元格填数就可以把数独解出来。如果在解题的过程中,发现某些空白单元格没有数字能填这样的单元格称之为无解单元格,那就说明:要么这个数独没有解;要么之前的解题过程有问题,需要返回检查之前的解题过程查看。

  

  但是还有不少的数独的题目,在解题的过程中,在还有空白单元格的情况下,却找不到唯一数单元格,也就是意味着每个空白单元格中能填的数字至少有2个。而出现无唯一数单元格的这种状况,我们可以找到其中一个可能数最少的空白单元格(这个没有定论,可以是可能数最少的空白单元格;

  

  也可以是第一个空白单元格;也可以是可能数最多的空白单元格,选哪个空白单元格对后面的解题是否有影响,没有证明过,不好妄下定论。凭感觉选可能数最少的空白单元格是最好的选择),由于能填的数字不止一个,先把当前的状态保存起来,再在能选的数字中选择一个数字填写(从小到大选择),然后继续求解下去。如果能解出最后的结果,说明当前的选择是正确的;如果后面的求解过程有问题,说明当前的数字的选择有问题,那么再挑选另一个数填写,继续求解。

  

  如果,所有的选择都求不出最后的结果,还是说明:要么这个数独没有解;要么之前的解题过程有问题,需要返回检查之前的解题过程查看。如此反复,直到求出最终的答案。会有种极端的情况(可能性不大)。那就是在当前的空白单元格的所有可能的数字都选择了一遍,都没有解。而之前又没有出现无唯一数单元格的状况。那就说明这个数独根本就无解。

  

  

本文标签: 算法  标签  简介  

为您推荐

算法实践数独的基本解法 数独的解答

算法实践数独的基本解法,数独(Sudoku)是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9乘以9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1到9,不重复。

2024-06-22 09:02

速度最快的dns 速度最快的DNS

速度最快的dns,DNS服务是网络参数必不少的一项,它是把域名解析出IP地址的一项服务,每个网站都有一个域名对应到一个IP地址,众多的网站我们记域名很容易记,而记IP地址就非常费力了,有的DNS服务快,解析也就快,上网就快;

2024-06-22 09:02

算法工程师是程序员吗(算法工程师是程序员吗工资多少)

算法工程师是程序员吗,程序员(英文Programmer)是从事程序开发、程序维护的专业人员。算法工程师的职责主要是设计算法逻辑,而程序员则是通过代码的撰写来实现算法想要得到的结果,二者分工和侧重点有所不同。

2024-06-22 09:02

随机分配算法(随机分配算法流程图)

随机分配算法,随机算法是一个概念图灵机,也就是在算法中引入随机因素,即通过随机数选择算法的下一步操作。

2024-06-22 00:11

随机函数公式 excel区间随机函数公式

随机函数公式,随机函数就是产生数的函数,是EXCEL中很重要的函数。在Excel中有2个随机数生成的函数,具体如下:第一个,RAND函数,说明:RAND函数可以生成0到1之间的随机函数(包含小数位数)。

2024-06-22 00:11

算法正确的程序可以有零个输出(算法正确的程序可以有零个输出吗)

算法正确的程序可以有零个输出,C语言中的算法是指为解决某个特定问题而采取的确定且有限的步,主要的五个特性是:有穷性、确定性、可行性、有0个或多个输入、有一个或多个输出。

2024-06-22 00:11