算法实践数独的基本解法


算法实践数独的基本解法


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

    推荐阅读