AMF48

DevQuizが終わったので、結果をまとめておこうかと… 　回答数: 5000/5000 　L: 68088/72187 　R: 77650/81749 　U: 67642/72303 　D: 77117/81778 LRUDは、計17520個余っていますが、まだまだ削れるみたいですねぇ。 （5000問のうち、2509問だけは最適解と確認済） 【やったこと】 ※ちなみに、今回は評価関数を全く書いていませんｗ 1. 初期状態と、ゴール状態の双方から１手づつ展開 　・パネルの状態を表す文字列がキー、経路が値のマップを作成しながら展開 　・前方からの展開と、後方からの展開が一致すれば、経路をつないで回答とする 　・この方法だと、メモリー使用量がネックになって、確実に解けるのは４０手どまりでした… 　・ただ、それでも頑張ってまわせば1500問以上は解けていた気がします 2. 問題を分割（左端、上端偏） 　・左端あるい上端から１列づつ埋めて、問題を小さくして、総当りできるサイズに削る戦略 　・ただし、袋小路などが出来ないように、隣接ブロック数が１つ以下の部分は移動対象に追加 　・移動の対象にならないブロックを「?」に置き換えてパネルの状態を圧縮 　・ゴールは、「0」がどこにくるかわからないので、可能性がある分準備… 　・１列全てだと移動できない場合、分割して移動するように処理を追加 　・部分移動に成功した場合、移動済の部分は変更しない条件付きで経路探索を継続 　・ここまで書けば4900問ぐらいまで解けた気がします 3. 問題を分割（上下左右端偏） 　・下側、右側から埋めていくことを許容 　・下側などから埋めると「0」の位置が問題になるので、予めゴールの「0」を移動させておく必要あり（後で、その移動に使った分を、経路に追加しておく） 　・ここまで書くと4996問まで解けたと記憶しています 4. 残り４問を個別対応 　・３問は、初期に移動するブロックを指定すれば解けました。 　・１問は、ゴール状態を指定（＝「0」のずらし方を指定）でなんとか解けました。 5. この時点て３万ぐらいLRUDが足りなかったので…^^; 　・初期に与える移動ブロックを２行とか３行にするなど、部分移動量を増加（ロングパス狙いｗ） 　・初期ブロックの与え方を変えた２PGを実行し終わった時点で、8000ぐらい余裕ができて、無事ゴール♪ ＃150点獲得後は、総当りのPGを改良して、最適解がいくつあるのか数えていました… ＃Java7のFork/Joinをお試しに使ってみたので、性能評価したら公開したいかも… 【結論】 力技でも、満点は取れる！ｗ

いろいろ試行錯誤の結果、なんとかスライドパズルを５０００問解いて DevQuiz (Google Developer Day 2011に参加するための問題)で、 満点の150点を達成！ いろいろ書きたいこともあるけど、提出期間の終わる、来週の月曜まで 自粛規制っと…。今は画像だけ貼っておきますｗ