factory-predictor その18 ダム問題の完全ではない解

ダムがいくつかあり、グループAとグループBに分かれている。
水道局がいくつかあり、各水道局はグループA, グループBそれぞれ1つずつのダムとつながっている。
グループA, Bそれぞれから3つずつダムを選んで、そこからすべての水道局を直接たどれるようにしたい。それは可能か判定せよ。

この問題は完全に解く必要はないことに気づきました。つまり、「おそらく可能である」「確実に不可能である」で出力されても十分なのです。
それなら、グループA, グループBを区別せずにカバーできる水道局の個数に関する貪欲法でダムを選べばいいです。

ということでおおざっぱな結果を出力する部分(RoughPredictorクラスと呼んでいます)をこれに基づいて実装してみたところ、だいぶ無駄な結果を含んでしまうようで、入力値しだいではとても遅くなることがあります(1分以上かかったり)

ただこれは探索時に順次予定表が作成可能かを判定することによって枝刈りをすればマシになるんじゃないかと思うので次へ進むことにしましょう。

また、このグループA, Bを区別しないという考え方を使うと以下のことが実際のファクトリーのデータベースにおいて成立することも確認できそうです。

2nより小さい整数kについて、k個の互いに衝突しないエントリーを勝手に選んだとき、それらのどれとも衝突しないエントリーが存在する。