Chinaunix

标题: 数独的算法这么简单？ [打印本页]

作者: mirnshi 时间: 2012-06-01 16:03
标题: 数独的算法这么简单？
算法的基本思想：

　　步骤1、将所有未确定的格子的可能性定义为0xFFFF（即所有数字都可能），可能数目为9。

　　步骤2、寻找所有确定的格子A（可能数目为0），在所有与A同行、同列和同区域的未确定的格子的可能性中减去与A相同的可能性。例如：A确定为9，则与A同行、同列和同区域（区域标志相同）的未确定的格子的可能性与0xFEFF按位与（除去可能性9），并将其可能性数目减少。

　　在除去可能性的过程中如果发现某个格子B的可能性数目由1减小为0，说明B和A只能取相同的数字，这可能是题目本身无解引起，也肯能是由于步骤3中搜索方向不对引起的，可认为此方向的搜索无解，退出这一方向的搜索。定义这个检查为唯一性检查。

　　步骤3、寻找所有未确定格子中可能性数目最少的格子M，如果M的可能性数目为1，则确定M：将M的可能性数目定义为0，并把确定数量加1，如果此时确定数量达到81，则报告找到解，否则，在所有与M同行、同列和同区域的未确定的格子的可能性中减去与M相同的可能性，并进行唯一性检查。然后重复步骤3。

　　如果M的可能性大于1，则把M假设为所有M的可能性，分多个方向进行搜索，在每一个搜索方向重复步骤3（这个可以用递归来实现）。

作者还给出了C代码。
http://simplesource.blog.163.com ... 140620077104021963/
---------------
直接玩，可是想破了脑袋呀。

作者: aychxm 时间: 2012-06-01 16:43
本帖最后由 aychxm 于 2012-06-01 16:44 编辑

解数独的算法，无非两个方法重复多次地解决每一个空格子：排除，否则就假设

对一个格子，横的、竖的、还有3x3的，用1~9去查，看哪些数可以填，如果确定了，就填进去，
再看哪些数不能填，如果1、2、3、5、6、7、8、9都不能填，那就只能填4了。
如果不能确定，就在可能的数中做假设，再往后推，最后冲突了，再假设另一个。

生成数独的算法才有商业价值。

作者: _Rayx 时间: 2012-06-01 18:28
回复 1# mirnshi

如果是想解数独的算法的话，建议可以尝试一个dancing links。非常优美并且速度非常快的一个算法。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)