algorithm - 如何在 1 秒内找到数独游戏的所有解决方案（计数）？

Question

我已经尝试过跳舞链接和其他一些搜索算法，但它不会在 1 秒的给定时间限制内工作。对于具有大约 100 万个解决方案的数独游戏，计算所有解决方案大约需要 10 秒。

Answer 1

1M 的结果听起来有点吓人，但为了快速求解，基本上你必须使用消除/约束传播过程和对可能值最少的字段进行详尽搜索。

Peter Norvig 的一篇优秀文章：解决每个数独难题。

Answer 2

Standard solving algorithms for Sudoku (all solutions) use backtracking. Classic variant of Sudoku has only one solution (or at least should have), so there you might use human-like techniques, but this is in the case not possible. So backtracking will be probably the only way.

But you might want to use several tricks

• Prunning of the tree (extend basic prunnign strategy of backtracking algorithm with more sophisticated conditions)
• Massive parallelism (I think that that you might benefit of superlinear accelaration of the solution, because some sub-problems might be the same, hence solvable only once, or might prune some branches of other threads)
• Use symmetry and some special properties of your setting, this is probably the best strategy, if you have some implicit knowledge
• You might try some blackbox approaches - for example constraint (logic) programming, which are highly optimized in searching in massive search space...