用启发式方法解决数独：好主意吗？
我试图用“Drools Planner”包解决部分初始化的数独难题（报纸上出现的那种）。虽然它可以在 3 秒内从头开始生成（随机）谜题，但它会陷入解决部分初始化谜题的循环中。
问题：禁忌搜索和模拟退火等启发式方法从根本上来说对于数独来说是一个糟糕的选择吗？我说的是完整性（是否能够达成解决方案）和效率（是否杀伤力过大）。
我的怀疑来自这样一个事实：数独谜题总是有一个精确且单一的解决方案，而启发式算法（据我所知）并不是为了“达到它们”而设计的。
I was trying to solve a partially initialized sudoku puzzle (the kind that appears in newspapers) with the 'Drools Planner' package. While it can generate a (random) puzzle from scratch in 3 seconds, it gets stuck in a loop solving a partially initialized puzzle .
Question: Are heuristics such as tabu search and simulated annealing fundamentally a bad choice for sudoku? I am talking of completeness (will the solution be reached) and efficiency (is it overkill).
My doubt comes from the fact that a sudoku puzzle always has an exact and single solution and heuristic algorithms are (AFAIK) not designed to "reach them".
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果禁忌搜索和模拟退火等启发式方法对于解决数独来说是一个糟糕的选择，我对您的是/否问题的回答是肯定的。
该问题对局部搜索策略的效率有太多限制。
数独是约束满足问题 (CSP) 的一个很好的例子，CSP 求解器非常擅长解决它。这并不意味着本地搜索不起作用或者启发式通常是一个坏主意，但是这个问题可以通过传播约束很容易地解决。
My answer to your yes/no question, if heuristics such as tabu search and simulated annealing are a bad choice for solving Sudoku, is yes.
The problem has far too many constraints for local search strategies to be efficient.
Sudoku is a good example for a constraint satisfaction problem (CSP), and CSP solvers are very good at solving it. That doesn't mean that local search won't work or that heuristics are a bad idea in general, but this problem can be solved pretty easily by propagating constraints.
是的，如果只是因为良好的约束传播算法可以非常快地解决数独问题，那么根本不需要启发式方法。此外，您（确实）不想要数独的部分解决方案。
Yes, if only because a good constraint propagation algorithm can solve sudokus very fast, so there's no need for heuristics at all. Besides, you (indeed) don't want a partial solution to a sudoku.
对于诸如 9x9 数独之类的问题，严格编码的强力搜索可以很快找到解决方案。此外，由于它可以确定找到所有解决方案，因此它还将确定数独是否正确形成，因为它具有唯一的解决方案。
For a problem such as the 9x9 Sudoku, a tightly coded brute force search finds a solution very quickly. Further, since it can be certain of finding ALL solutions, it will also determine if the Sudoku is properly formed in that it has a unique solution.