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

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

Sudoku backtracking algorithm with rule-base strategies

Sudoku has unique solution, and backtracking can guarantee the correct result. In order to improve the efficiency of backtracking method, this paper solved Sudoku by the most basic rule-base strategies during searching, only two or three correct candidates were needed to solve successfully. When the Sudoku was solved by the basic rule-base strategies, the returning result was one of 3 cases, i. e. the success, the failure, and the uncertainty. Only when the result was uncertain, the search was continued, as a result, the efficient pruning was achieved. Meanwhile, this paper used a number of bit operations in the algorithm implementation. A large number of 9×9 Sudoku experiments show that the average calculation time is less than 0.15 ms for most Sudoku and 2 ms for those extremely difficult Sudoku. In addition, the average time to solve a 16×16 Sudoku is 224 ms. The 9×9 Sudoku dataset with 17 cues is recommended as a standard test dataset due to its diversity.