GDD2011 DevQuiz のチャレンジクイズ「スライドパズル」ソルバーです。

満点は取れませんでしたが、Core i5-2520M/Z21、8GB Memory の 64 bit PC で、シングルスレッドで 4600 問以上を 1.1 時間程度で解答します。 ページファイルを有効にして 20GB ほどのヒープを利用できるようにすれば、4800 問以上を 3 時間ちょっとで解答してくれます。

各々の解答は最適解とは限りませんが、最適に近い解を計算してくれます。

上記スペックの PC で、１つの問題を解く際に保持する履歴数の上限を決めるパラメータを変化させたときの * ヒープ使用量（目視確認） * 処理時間 * 解答数・割合 は以下のとおりです。

| 保持履歴数上限 | ヒープ使用量 | 処理時間 | 解答数 (割合) | |:------------|:-----------|:---------|:-------------| |65,536 (2^16)|約 66 MB |80 秒 |1,597 (31.9%) | |262,144 (2^18)|約 75 MB |273 秒 (約 4.5 分)|2,856 (57.1%) | |1,048,576 (2^20)|約 88 MB |742 秒 (約 12.4 分)|3,841 (76.8%) | |4,194,304 (2^22)|約 195 MB |2,091 秒 (約 35 分)|4,440 (88.8%) | |8,388,608 (2^23)|約 340 MB |3,885 秒 (約 1.1 時間)|4,616 (92.3%) |

ソルバーの戦略については、次の URL のブログに書きました。 http://blog.k11i.biz/2011/09/gdd2011-devquiz.html