DLX 求解数独

原创
10/29 00:27
阅读数 29

https://www.cnblogs.com/grenet/p/3145800.html

https://blog.csdn.net/xiahn1a/article/details/50858957

https://www.jianshu.com/p/93b52c37cc65

https://blog.csdn.net/zhangjianjunab/article/details/83688681

http://blog.gssxgss.me/use-dlx-to-solve-sudoku-1/

https://blog.csdn.net/moguxiaozhe/article/details/47998443

https://blog.csdn.net/WhereIsHeroFrom/article/details/79220897

 

基本上还是有很大提升的, 相比于使用位的搜索算法, 空间和时间上有很大的优势, 不管是有解还是无解都很快

 

两个优化点

1, 每次选择含1数目最少的列

2, 尽量将1最多的行放在前面

3, 构造行的时候尽量用条件约束构造尽可能少的行, 用行, 列和九宫去约束可能性

另外列的顺序不会影响解的结果, 但是行的顺序会影响解的映射

行列的变化和选取影响搜索的路径, 即尽量在一开始选取可能比较少的, 因为这样在删除行的时候可以删除大量无效状态

 

 

 

 

 

添加一些剪枝, DLX算法的优势更大了

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部