我试图用“Drools Planner”包解决部分初始化的数独谜题（报纸上出现的那种）。虽然它可以在 3 秒内从头开始生成（随机）拼图，但它会陷入解决部分初始化拼图的循环中。
问题： 诸如禁忌搜索和模拟退火之类的启发式算法从根本上说是数独的错误选择吗？我说的是完整性（是否会达成解决方案）和效率（是否矫枉过正）。
我的怀疑来自这样一个事实，即数独谜题总是有一个精确和单一的解决方案，而启发式算法（AFAIK）并不是为了“达到它们”而设计的。
问问题
3057 次
3 回答
4
如果禁忌搜索和模拟退火等启发式方法是解决数独的错误选择，我对您的是/否问题的回答是肯定的。
这个问题对局部搜索策略有太多的限制，无法有效。
数独是约束满足问题 (CSP) 的一个很好的例子，CSP 求解器非常擅长解决它。这并不意味着本地搜索不起作用或启发式通常是一个坏主意，但这个问题可以通过传播约束很容易地解决。
于 2012-02-01T12:47:43.727 回答
1
诸如禁忌搜索和模拟退火之类的启发式算法从根本上说不是数独的错误选择吗？
是的，如果仅仅因为一个好的约束传播算法可以非常快地解决数独问题，那么根本不需要启发式算法。此外，您（确实）不想要数独的部分解决方案。
于 2012-02-01T12:43:55.780 回答
0
对于像 9x9 数独这样的问题，经过严格编码的蛮力搜索可以很快找到解决方案。此外，由于可以确定找到所有解决方案，它还将确定数独是否正确形成，因为它具有唯一的解决方案。
于 2012-07-31T20:25:54.843 回答