練習がてらなにかプログラムを書きたいと思っていたところ，友人が，プログラミングの課題で「美術館」というパズルを解くプログラムを書かされたという話を聞いた．
面白そうなので書いてみたところ，思ったよりも辛い問題で，躓いた点があったのでメモします．
1.概要
「美術館」というパズルゲームはニコリという出版社が生み出したパズルゲームで，Nクイーン問題みたいなパズル．ルールやサンプル問題などは以下を参照．
公式サイトはFlashのバージョンの問題からか，ChromeやFirefoxからはスッと試すことができなかったので，一度手でやってみたいという方は4番目のニコリパズル道場！という趣味で自作のパズルをあげてるサイトを見ると良いと思います．
2.解法
単純に深さ優先探索とかで書くと，探索空間が2^(WH)で増えていくので解くことはできない．
ただ，一度自分の手で解いてみるとわかりますが，とりあえず置いてみておかしいところが無いか確認する探索よりも，よく知られている経験則によって置く場所が決まることが多いです．
そういった人間でいう「解くためのコツ」を如何に高速に実装できるかがキモでした．
ただ問題によってはある経験則を消したほうが早くなる場合もあってこうしたら絶対に良くなると言い切るのは難しいです．
私の実装では置ける場所・明るくなった場所をbool型の2次元配列でもっておき，以下の制約を実装しました(1-2はルールの言い換え)．
- 数字マスの周りに置かれた照明の数が，数字マスの数字と一致した場合，その数字マスの周囲にはもう照明は置けない．
- 明るくなったマスには照明は置けない．
- 数字マスの数字が，置ける空白マスの数と一致している場合は，全ての置ける空白マスに照明をおける．(e.g. 数字4のマスの周りは全て置ける)
- 数字マスの周囲に，数字マスに書かれた数だけ照明を置く事ができない場合は条件を満たすことができないので探索を終える．
- 置くことができる暗いマスで，その縦列・横列に置ける場所がない場合はそのマスに照明を置ける．
- 置くことができない暗いマスで，その縦列・横列に置ける場所がない場合は条件を満たすことができないので探索を終える．
上記のルールに基づいていけば結構なマスを埋めることができます．
ただ，5はない方が早いこともあるしあったほうが早くなることもあるが，6番目の条件は，これがないとマトモに解けない問題もあります．
この条件でマスを埋めることができなくなった場合は
- 照明を置ける場所にとりあえず置いてみて条件が満たせないか確認し，もとに戻す．条件を満たせなかったらそのマスは置けないマスとなる．(e.g.数字3のマスの斜め方向には置けないなどの制約になる→Wikipediaの解法を参照)
- 数字の周りから先に探索する
という方針で探索領域を狭めながら探索を進めたところ，当方の環境でニコリのお試し問題すべてを4秒以内に解けるようになりました．
ただ公開するにあたって修正したのですが，修正する前のコードは半分ぐらいの時間で計算しているので実装の仕方次第でもう少し早くなるはずです．
3.ソースコード
サンプル入力・出力とともにGithub Gistにあげました．
サンプル入力はニコリのお試し問題からの引用です．
見た目を良くしたつもりなのですが500行を超えてます．
しかも整形しただけで計算時間が2倍になった理由がわからない……．
4.追記
書いた後に調べたところ，もっと良い経験則があるとのこと．爆速になるらしいので機会があったら実装したいです(多分しない)
0 件のコメント:
コメントを投稿