数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。此处出现的候选数我们稍后再提。
※不要求斜线也满足条件
最常规的回溯法对于常规,也可以说是最常使用的一种算法,回溯法。它可以用来解决很多问题,比如这里的数独问题。 先说说它的优点,对于程序员来说,代码量很少,往往几层嵌套循环就可以解决问题,逻辑也很简单, 编写也很快捷。但这里我们为什么不推荐使用呢,因为它对于这个问题,时间复杂度有些高。 首先这个算法类似与我们平时说的试。先对于一个空格,依次读取该格所在行,所在列,所在宫,保证所填数与三者中任一数都不重复。比如上面的图,第一行第二列那个格,检查该行列宫后,出现数为123567,所以它可以填489,根据回溯法,就填4,然后看第二空格,以此类推,直到有一空格没有数字可填,则将上一空格所填数更改,如果该格也没有可以更改的数,那么再退上一格。。。。。所以到后来,如果运气不好,这个方法可能会试非常非常多次,所以我认为对于单纯的计算机效率来说,这个方法不算优。
再看这此时,再将我要写的算法之前,先讲一下人工数独解法。此处要引入一个概念,叫做候选数。 候选数顾名思义,就是候选的数字。对于每一个要填的空格,都有一个候选数组。比如第一行第二列的那个空格,489就是它的候选数,如果还是不懂,百度一下你就知道!
第一种,唯一候选数法其实这些解法只是数独解法的冰山一角,往往一个复杂的数独题目要使用很多很多的方法。具体可参考这里 但是对于实现起来的逻辑,我挑选了一共两种解法交替使用。第一种,也是最好用的,唯一候选数法。即按照上面提到的,将每一个空白格按照行列宫依次查找,最后得出其候选数组,然后找到那个候选数组中候选数个数为1的,说明这个格只能填这个数字,然后填入。之后更新所填格所在的行列宫的其他空白格的候选数组,也就是减去新填入的这个数字。
当某行已填数字的宫格达到8个,那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为行唯一解。 唯一候选数法的思路是:选定一个空白格,从其初始候选数中删除与它在同一行、同一列以及同一宫中已经确定的数字,当这一格的候选数为1时,这一格正确的数字就是剩下的唯一一个候选数。如此重复,直至找到全部解或者无法再用此方法进行下去。 比如这个题,我们可以发现中间那个格子,填5,然后将该行列宫中所有的候选数都删去5,发现该行第二列那个各自只能填2,依次类推,到后来会出现越来越多的唯一候选数格子。
第二种,隐式唯一候选数法与第一种方法类似,只是有时我们发现所有空白格中,没有一个候选数个数为1的,此时第一种方法已经行不通了,我们就要用到隐式法了。虽然表面上没有候选数 当某个数字在某一行(列、宫)各单元格的候选数中只出现一次时,那么这个数字就是这一列的唯一候选数了.这个单元格的值就可以确定为该数字. 这时因为,按照数独游戏的规则要求每一行(列、宫)都应该包含数字1~9,而其它单元格的候选数都不含有该数,则该数不可能出现在其它的宫格,那么就只能出现在这个宫格了。 比如这个题,会发现没有唯一候选数格子,此时第一种方法失败,然后用第二种方法,可以发现第三行第七列中候选为5的那个格子,该行的候选数中再没有出现5,所以这里必填5,然后更新该行列宫的候选数,以此方法,一旦出现候选数为1的格子,立刻停止此方法,调用第一个方法,直到第一个方法再次失败,再调用此方法。
plan B如果两种方法都失败了呢?那就无可奈何了,我的算法逻辑仅写到这里。有兴趣的朋友可以写