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

来源：计算机应用研究杂志2020年第2期北京时间：

作者：江顺亮,唐祎玲,徐少平,叶发茂,

单位：南昌大学计算机系,南昌330031；

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

关键词：数独,回溯法,人工策略,计算时间,

基金资助：国家自然科学基金资助项目(61662044)；；