GDD2011 DevQuiz スライドパズル

http://blog.gijutsuya.jp/hrjn/2011/09/13/gdd-2011-dev-quiz1-3/ に触発されて、一応メモぐらいは残しておこうと書いてみる。

最初に問題を見たときは「それぞれのパズルに幾つかの解き方があって、それの組み合わせを頑張る感じかなー」とぼんやりと思ったんだけど、全然そんなことはなかった(w
ほら、RとDが多かったじゃん? (冷静に考えると当たり前

流れとしては

まずは幅優先で手数の短い答えをいくつか求めてみよう。
↓
冷静に考えると局面多いな、というかO(n!)か。んー、枝刈り頑張ってIDDFSやってみる感じ?
↓
んー、まぁそれなり。指数的に局面増えるからキャッシュ無理かなぁ…。壁がなければ部分問題(左/上のラインだけそろえて)に帰結できるんだけどなぁ…。
↓
焼きなましで得られた結果(数万手とかのオーダ)をうまく縮約する方法がないか考察。(こっち方向は全然思いつかなかったけど、何かあったりするのかな?)
↓
A*を試す。
↓
悪くない。あれ? この規模感なら局面のキャッシュできるんじゃね? あ、キャッシュできるなら双方向探索できるか。
↓
シンプルに実装して4000問弱ぐらい。(ここで初日終了)
↓
メモリを積み上げたマシンで評価関数の重み付けをいじって再挑戦を繰り返してして残り20問ぐらいまで。(他の方法も模索しつつ、1週間ぐらい)
↓
手動回答用のプログラムを書いて(w
↓
手動で左/上の列をいくらか揃えてやって、ソルバに突っ込む戦略で最後まで。