数独プロジェクト追加

 数独の問題がただ一つの解を持つことの証明 (nurse-scheduling-software.com)

シフト勤務表では、求解回数が効きます。前回とは異なる解を求めようとするので、2つめの解がないということは、1解しか存在しない、ということの証明になります。

その昔、池上先生のベンチマークについて、池上先生のベンチマーク上の解はどの程度存在するかについて、お聞きしたことがあります。少なくとも100万以上は実際に存在するのだそうです。

しかし、例えば、SchedulingBenchmarksのInstance15を見ると、そんなにもあるはずがないと思います。恐らく一桁台だろうと思います。

問題の難しさは、解空間/探索空間　に反比例するであろうと思うので、その意味では、池上先生のベンチマークは、易しい部類に入り、解きようによっては時間がかからないのだと思います。しかしながら、Instance15は、探索空間も広いし、解も少ないということで、難しい問題、時間のかかる問題ということなのだろう、と解釈しています。