如何在1秒内找到数独游戏的所有解(计数)？

Question

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

Answer 1

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

Peter Norvig的一篇优秀文章：Solving Every Sudoku Puzzle。

Answer 2

数独(所有解决方案)的标准求解算法使用backtracking。数独的经典变体只有一个解决方案(或者至少应该有)，因此您可以使用类似于人类的技术，但在这种情况下这是不可能的。因此，回溯可能是唯一的方法。

但您可能希望使用以下几个技巧

• Prunning of the tree (用更复杂的conditions)
• Massive并行性扩展回溯算法的基本剪枝策略)
• 使用对称性和你设置的一些特殊属性，这可能是最好的策略，如果你有一些隐含的知识
• 你可以尝试一些黑盒方法-例如constraint (logic)编程，它们在海量搜索空间中进行了高度优化--