「Drools Planner」パッケージを使用して、部分的に初期化された数独パズル (新聞に掲載されているようなもの) を解こうとしていました。3 秒でゼロから(ランダムな) パズルを生成できますが、部分的に初期化されたパズルを解くループに陥ります。
質問: タブー検索やシミュレートされたアニーリングなどのヒューリスティックは、数独にとって基本的に悪い選択ですか? 私が話しているのは、完全性 (解決策に到達するかどうか) と効率性 (やり過ぎかどうか) です。
私の疑問は、数独パズルには常に正確で単一の解決策があり、ヒューリスティックアルゴリズムは（AFAIK）「それらに到達する」ように設計されていないという事実から来ています。
はい/いいえの質問に対する私の答えは、タブー検索やシミュレートされたアニーリングなどのヒューリスティックが数独を解決するための悪い選択である場合、はいです。
この問題には、ローカル検索戦略を効率的にするには制約が多すぎます。
数独は制約充足問題 (CSP) の良い例であり、CSP ソルバーはそれを解くのに非常に優れています。これは、ローカル検索が機能しない、またはヒューリスティックが一般的に悪い考えであるという意味ではありませんが、この問題は制約を伝播することで非常に簡単に解決できます。
タブー検索やシミュレートされたアニーリングなどのヒューリスティックは、数独にとって根本的に悪い選択ですか?
はい、優れた制約伝播アルゴリズムが数独を非常に高速に解決できるという理由だけで、ヒューリスティックはまったく必要ありません。その上、あなたは（実際に）数独の部分的な解決を望んでいません。
9x9 数独のような問題の場合、厳密にコード化された力ずくで検索すると、非常に迅速に解決策が見つかります。さらに、すべての解を確実に見つけることができるため、数独が一意の解を持つという点で適切に形成されているかどうかも判断します。