融合人工求解策略的数独回溯求解法

• 作者: 叶发茂 唐祎玲 徐少平 江顺亮
• 来源期刊: 计算机应用研究
• 关键词: 数独 回溯法 人工策略 计算时间
• 年，卷（期）: 2020,（2）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 481-485
• 页数: 5页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2018.08.0539

摘要

数独有唯一解,回溯法可以保证获得正确结果.为了提高回溯法求解效率,向前搜索用最基础的人工策略进行求解,这样只需要两三个正确的候选数就可求解成功.基础人工策略求解的结果分为求解成功、求解失败和求解不确定三种情况,只有在求解不确定时才继续向前搜索,从而达到高效剪枝的目的;同时在算法实施方面采用大量位运算,大量9×9数独的实验结果表明对于绝大部分数独,平均计算时间不超过0.15 ms,对于那些极端困难的数独平均求解时间为2 ms;求解一个16×16数独的平均时间为224 ms.通过实验还发现17个提示数的9×9数独数据集在各方面具有较好的分散性,建议作为标准测试用数据集.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	江顺亮	南昌大学计算机系	72	456	11.0	17.0
2	徐少平	南昌大学计算机系	85	417	11.0	17.0
3	唐祎玲	南昌大学计算机系	30	110	6.0	9.0
4	叶发茂	南昌大学计算机系	21	134	7.0	11.0