イラストロジックを解く 第4回 全探索

さて, 4回目の今回は全探索。
考えられる盤面を片っ端から全探索します。

アルゴリズム

1. 一番上の行の最も左のキーをk_1, 2番目に左のキーをk_2, ..., 一番上の行の最も右のキーをk_i, 二番目に上の行の最も左のキーをk_{i+1},..., 一番下の行の最も右のキーをk_n というようにキーにインデックスをつける
2. 行に関する制約を満たすようにキーを配置する。そのとき, それぞれのキーはできるだけ左詰めにする(初期状態)
   
3. 全ての列について、キーを満たすマスの塗り方がなされているかを検査する
   
   • もし全ての列について、条件を満たしていればその盤面を出力する
     
   • もし条件を満たしていない列が一つでもあれば、次の操作を行う
     
     • l = n
       
     • キーk_lが右にスライドできるまで l = l - 1と更新する
       
     • キーk_lが右にスライドできるならば, 右にひとマススライドし, k_{l+1} ~ k_nキーを, 可能な限り左詰めで再配置する

実行例

かもめ
問題

答え

探索中...


途中で切りました。見るからに, 遅いアルゴリズムですが, 正解を見逃すことはありません。
次回はこの全探索(左詰め)をより効率よく行う方法としてDFS(深さ優先探索)を紹介します。
(要するに, 今回は咬ませ犬)

ソースコード

gist.github.com