DevQuiz，スライドパズルの解答コードを今更晒してみる
1ヶ月ぶりくらいの更新となってしまいました．
最近は何をしていたかというと，
- 学会発表に追われていた（9月上旬)
- スライドを作っては直しの日々
- DevQuizのコーディングと，アルゴリズムの試行錯誤に追われていた(9月上旬)
- 学会中も悶々と考えてたりなかったり（；^ω^）
- 自転車で一人旅していた(先週まで)
- 後ほどまとめて記事にします
って感じでした．
さて，先ほどGoogle Developer Dayへの参加可否のお知らせが順次届いてると公式発表され，1時間もしないうちにこちらにもお知らせが届きました！
━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 【 Google Developer Day 2011 Japan 】 参加確定のお知らせ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━ manji602 様 この度は「Google Developer Day 2011 Japan」にお申し込みいただき、誠にありがとうございます。 先般ご回答いただいた DevQuiz の結果、GDD 2011 にご参加いただけることが 決定いたしましたのでご連絡いたします。 なお参加証につきましては、10 月上旬より順次お送りいたしますので、今しばらくお待ちください。 ========================================================== Google Developer Day 2011 Japan ■日時： 2011 年 11 月 1 日（火） ■場所： パシフィコ横浜 会議センター 〒 220-0012 横浜市西区みなとみらい 1-1-1 （http://www.pacifico.co.jp/visitor/accessmap.html） ========================================================== 当日のご来場、心よりお待ち申し上げます。 主催： Google
ということで無事に参加できるようです．よかったー(^q^)
ちなみにDevQuizの結果はこんな感じです．
スライドパズル自体は2598/5000だったかと思います．
んで早速ですが解 答 コ ー ド を 晒 し ま す
以下ネタバレ注意
ソースはgithubに上げています．開発言語はjava，環境はeclipseでやりました．
https://github.com/manji602/DevQuiz2011
結構バタバタ作っていたので関数の名前やクラス名が適当です（；^ω^）軽めに解説をしておくとこんな感じ．
プログラム一覧
- block.java
- ブロックの配置の生データをintで保持．更に，0の位置をblank_positionで持っておく．
- quiz.java
- ファイル入出力関係など，問題を解く上で一番外側のレイヤの記述をしています．
アルゴリズム解説
基本的にはIDDFS（反復深化深さ優先探索）でやっています．（厳密にはちょっと違うかもしれません）hash.javaのextract関数で現在の盤面から次のとりうる盤面を展開して，find_next_target関数で次に展開すべき盤面を選ぶ，という操作を何度も繰り返します．
繰り返しの回数は25万回で止め，それ以上になったらスキップするようにしました．
extract関数について
- 現在の盤面から上下左右4方向に展開(もちろん位置的に不可能なものはスキップ），ゴールまでのマンハッタン距離を計算
- 展開した盤面を盤面候補リストに入れるかどうかの検討を行う．現在保持しているリスト内のマンハッタン距離の最大値を超えてしまうものは排除，最大値以下である場合はリスト内のマンハッタン距離が最大となる盤面候補を取り除く
find_next_target関数について
- 盤面候補リスト内から，ゴールまでのマンハッタン距離が最小となる物を選ぶ
- ここでfor文を0から順番に回していくと結果が偏ってしまう可能性があるので，ランダムにindexを取るようにしました．
このランダム要素によって，1回目のループで解けなかった問題が2回目で解けたり，なんてこともありましたｗ
実際にこのアルゴリズムが上手く回り始めたのが〆切3日前だったので，これ以上改善の余地がなく残念な感じに終わってしまいました．来年はもっと上を目指して頑張りたいです！
