当前位置: 首页 > 感悟故事 > 人生感悟 >
最新名人名言 名人名言排行 推荐名人名言

算法实践数独的基本解法

时间:2022-11-08 00:00来源:人生感悟 作者:在线人生 点击:

算法实践数独的基本解法

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

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

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

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

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

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

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

  • 上一篇:深圳地铁能用支付宝吗
  • 下一篇:没有了
  • 相关名言