サブロウ丸

主にプログラミングと数学

イラストロジックを解く 第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キーを, 可能な限り左詰めで再配置する

f:id:inarizuuuushi:20180125012723p:plain



実行例

かもめ
問題
f:id:inarizuuuushi:20180125014325p:plain:w300
答え
f:id:inarizuuuushi:20180125014443p:plain:w300

探索中...
f:id:inarizuuuushi:20180125013521g:plain:w300

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

ソースコード

gist.github.com