次のパズルを考えてみましょう:
セルは、マークされているかマークされていないかのいずれかです。パズルの右側と下側に沿った数字は、特定の行または列の合計を示します。セルは、その行と列の合計に貢献します (マークされている場合): 位置にあるセルは、列の合計と行の合計に(i,j)貢献します。たとえば、上の図の 1 行目では、1 番目、2 番目、5 番目のセルがマークされています。これらは行の合計 (合計 8) に寄与し、列の合計にはそれぞれ 1 つずつ寄与します。ij1 + 2 + 5
ECLiPSe CLP でソルバーを作成しました。それは完全に機能しますが、さまざまな値/変数の選択方法で非常に奇妙な動作を示し、その理由がわかりません。(注: パズルの各フィールドはドメイン [0,1] の決定変数で、マークされている場合は 1、マークされていない場合は 0 です。制約は明らかです。)
input_order ( search/6を参照)、first_fail、occurrences、または max_constrained を使用すると、ほとんどメモリを使用せずにパズルがほぼ瞬時に解決されます。最大または最小の anti_first_fail を使用すると、パズルが完了するまでに数分かかり、最大16GB の RAM を消費する可能性があります。なんで？これらのメソッドに対して、ほとんどの制約が非常に長い間アクティブのままなのはなぜですか?
たとえば、smallest と first_fail に違いがあるのはなぜですか? ドメインが 2 つの要素のみで構成され、すべての変数が同じドメインを持つ場合、first_fail、anti_first_fail、largest、smallest、most_constrained は同等であるはずです。ドメイン内の 1 つの値を削除すると、その変数に 1 つの値がアタッチされるため、それ以上の伝播は必要ありません。したがって、この場合の検索では、ドメインがちょうど 2 つの項目で構成される変数が常に処理されます。いいえ？