解説エントリー
[http://www.bear-project.net/blog/2011/09/gdd2011-devquiz/](https://web.archive.org/web/20121123172459/http://www.bear-project.net:80/blog/2011/09/gdd2011-devquiz/ )

* [GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた](https://harapon.hatenablog.com/entry/20110912/1315805381)
* [GDD 2011 Japan イグナイト: DevQuiz 解説](https://www.youtube.com/watch?v=gXx2ZBrNMSg)
* [エンジニアを熱狂させたグーグル「DevQuiz」は、日本生まれ世界育ち](https://atmarkit.itmedia.co.jp/ait/articles/1202/14/news139.html)

スライドパズル

■slide.php
本体。answer.txtがあれば解答済みファイルとしてスキップに利用、答えはoutput.txtで出力。
どのパズルをスキップするか、およびパズルに応じたタスク管理を選択するロジックをクロージャで渡して演算を開始。

幅優先探索は、反復深化深さ優先探索ははどちらもブラインドサーチで3x3と3x4,4/3のみに対応。それ以上は=(壁)検知付きマンハッタン距離、正位置にあるピースに重みづけ、それに手数削減のための過去の移動距離をそれぞれコストとして合計したものを関数としてヒューリスティック探索。繰り返し検知、逆探索検索付き。消費メモリ、消費時間に応じて無回答。制限時間になってもヒューリスティック関数の値が上昇し続けてたら時間制限を延長する”もう少しかも、頑張れ"機能。"下端を除くゲーム盤面の端で1つ足りないだけの状態にペナルティの効果"は今ひとつ。

演算コスト削減は、マンハッタン距離コストマップ、移動可否マップの事前演算。メモリ省力化として配列のSplFixedArray使用等。基本的な探索実装で目標スコア3000後半程度。肝心のソルバーは強くないが想定の範囲は大体実装、OOPでメンテナンス性はある程度確保されたと自己評価。

クラス

PuzzuleRepository
ファイルからパズルオブジェクトを取り出せるリポジトリクラス。

Puzzle
パズルの基本データ。プロパティの公開されているデータ構造クラス。

Game
ゲーム状態を保持しパズルの基本操作ができるオブジェクト。方向と合わせてタスクとして登録される。

Play
ルールを知りプレイを行うクラス。ゲーム完了するまでループ実行。

Task
BFS, IDDFS, A*探索を行うためのタスクマネージメントクラス。
それぞれPHPのSplQueue、SplStack、SplPriorityQueueクラスを利用。

■merge.php
answer.txtとoutput.txtの各問題の成績の良い方を選びながら、手数内の範囲でmergeするスクリプト

■fix.php
output.txtが正常に記録されなかったときや誤って消してしまったときに画面ログから解答ファイルを生成するスクリプト。

■count.php
使用カウンタ表示

■v.php
デバックプリント