数独(Sudoku)是一种运用纸、笔进行演算的逻辑游戏 。玩家需要根据9乘以9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1到9,不重复 。每一道合格的数独谜题都有且仅有唯一答案,推理方法也以此为基础,任何无解或多解的题目都是不合格的 。
数独的基本解法就是利用规则的摒弃法 。每一行称为数独的行,每一列称为数独的列,每一个小九宫格称为数独的宫 。数独的基本规则就是每一行、每一列、每一宫中,1到9这9个数字都只出现一次 。那些只能填一个数字的空白单元格,我们称之为唯一数单元格 。
解题的顺序,就是从唯一数单元格开始,由于唯一数单元格只能填一个数,故先在这个单元格里填数 。在这个单元格里填数,由于规则的定义,那么这个单元格所在的行、所在的列、所在的宫的其他单元格就不能再填这个数了 。这些单元格能填的数的可能性就少了 。有可能会产生新的唯一数单元格 。
在相当的一些的数独题目中,从唯一数单元格开始填数,不停的在唯一数单元格填数就可以把数独解出来 。如果在解题的过程中,发现某些空白单元格没有数字能填这样的单元格称之为无解单元格,那就说明:要么这个数独没有解;要么之前的解题过程有问题,需要返回检查之前的解题过程查看 。
但是还有不少的数独的题目,在解题的过程中,在还有空白单元格的情况下,却找不到唯一数单元格,也就是意味着每个空白单元格中能填的数字至少有2个 。而出现无唯一数单元格的这种状况,我们可以找到其中一个可能数最少的空白单元格(这个没有定论,可以是可能数最少的空白单元格;
也可以是第一个空白单元格;也可以是可能数最多的空白单元格,选哪个空白单元格对后面的解题是否有影响,没有证明过,不好妄下定论 。凭感觉选可能数最少的空白单元格是最好的选择),由于能填的数字不止一个,先把当前的状态保存起来,再在能选的数字中选择一个数字填写(从小到大选择),然后继续求解下去 。如果能解出最后的结果,说明当前的选择是正确的;如果后面的求解过程有问题,说明当前的数字的选择有问题,那么再挑选另一个数填写,继续求解 。
【算法实践数独的基本解法】如果,所有的选择都求不出最后的结果,还是说明:要么这个数独没有解;要么之前的解题过程有问题,需要返回检查之前的解题过程查看 。如此反复,直到求出最终的答案 。会有种极端的情况(可能性不大) 。那就是在当前的空白单元格的所有可能的数字都选择了一遍,都没有解 。而之前又没有出现无唯一数单元格的状况 。那就说明这个数独根本就无解 。
推荐阅读
- 随机分配算法
- 算法正确的程序可以有零个输出
- 电信运营企业专利申请有何策略以及如何实践
- 125×32x25简算 125×32x25简算算法
- 数独解题技巧有哪些
- 数独入门技巧有哪些?
- 科学实践观的四个意义 科学实践观的四个意义是什么
- 56×47用简便算法怎么算 56×47用简便算法如何算
- 谈谈630大图片作为桌面的算法改进
- 纸杯火箭手工制作实践目的是什么