赚钱创业网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

赚钱创业网 创业资讯 查看内容

算法实践数独的基本解法- 创业赚钱网tiyp.com

2020-5-22 17:14| 发布者: admin| 查看: 26| 评论: 0

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

  

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

  

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

  

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

  

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

  

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

  

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

  

  


鲜花

握手

雷人

路过

鸡蛋

相关分类

QQ|Archiver|手机版|小黑屋| 赚钱创业网 ( 粤ICP备18134897号 )

GMT+8, 2020-10-22 23:17 , Processed in 0.027093 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

返回顶部