テスト版(Ver1.1)から公開版(Ver2.7)まで

(Ver1.1)当初のテスト版(19997/08/15　HP公開)

　基本アルゴリズムは、「ハッシュ法(幅優先探索)」です。普通の「15パズル」とか「箱入り娘」とかの「スライディングブロックパズル」は殆どこれでおしまいなのですが、倉庫番には人間味のある特有なルールがあり、アルゴリズム的に工夫の余地が大いにある様なのです。当初のテスト版[８×８(荷物４個)]では、次の２つの枝刈りを組み込みました。

「デッドゾーン(進入禁止域)」 　一端ここに荷物を運んだらもう脱出不可能な場所があります。そんな地帯を事前に調査しておきます。(右図は1例)
「フリーズチェック(凍結状態検査)」 　全く身動きが取れなくなってしまった状態かをチェックしながら探索を進めます。(右図は1例)

(Ver1.2)最短解とは「手数」or「歩数」？

　荷物を押す回数について最小解(最小手数)を見つけるのがプログラム上合理的なのですが、解答表示でおもいっきりバカな動きをしたりします。歩く歩数について最小解(最短歩数)を見つける様に変更しまた。しかし、これによってメモリ消費が増えプログラムも大きくなってしまった。(どうしよう)

(Ver1.3)凍結状態を先読みする

　「フリーズチェック」は完全に凍結してしまった場合にその局面を探索から外します。しかし、まだ凍結してないが将来必ず凍結してしまう状況があります。これは閉空間を形成している荷物付近で発生します。

「局所探索法(閉空間ミニ探索)」 　閉空間を形成している局所部分を抽出して、ここだけでミニ探索を実行してみます。(右図は1例)

(Ver1.4)未完に終わった超高速手詰まりチェック

　残念なことに「局所探索法」は手間のかかるチェック法です。さらに、「デッドゾーン」「フリーズチェック」「局所探索法」のいずれでもチェック出来ない手詰まりパターンがあります。図がその例で、つまり、デッドゾーンは状況により変化するのです。ここでこれら総てを統合して、しかも高速にチェックしてしまう方法を思い付きました。

「多次元テーブル高速チェック法」 　「デッドゾーン」とは、荷物１個で許されないパターンのことです。同様に荷物２個の組み合わせで許されないパターン、荷物３個の組み合せで許されないパターンがあると考え方を統合する。これらのパターンを事前調査して多次元配列変数に登録しておきます。(しかし、プログラムが難しくて未完成です)

　

(Ver1.5)逆解き法は使えます

　この頃に「倉庫番INDEX」のおきやす氏とメールのやり取りがあり、大変貴重な情報を頂きました。
1992年頃に、「倉庫番自動解析プログラムコンテスト」(シンキングラビット開催)があり、優秀賞(審査員特別賞)は倉庫を逆から（格納された状態から）解くプログラムだったと言うのです。これにはシビレました。そして、私はこのアイデアをこんな風に応用しました。

「逆解き挟みうち法」 　解答発見までの通常の探索量は図の青と水色の合計面積です。しかし「逆解き法」を併用させ、途中で両者の探索の衝突地点を探す様にすると、水色の探索部分は不要になるのです。これで探索量は約半分になります。

(Ver1.6)笑って下さい「運が良けりゃ君」

　この頃になると、「最小手数」とか「最短歩数」とかはどうでもよくなりました。解けなければ何んにもならないのです。爆発的に増大する探索量をなんとしても押えたいという気持ちで、こんなことをしてみました。

「運が良けりゃ君」
　乱数を発生させ、その結果しだいで探索を間引きする。(情けない失敗策でした)

(Ver2.7)集団お見合いは男女同数がいい(19997/10/03　HP公開)

　「逆解き挟みうち法」はみごとに成功しました。しかし、探索結果の内部状態を調べてみると、先ほどの図のようには成っていなかったのです。両者の探索量の増加傾向はまちまちで、もっと贅肉を切り落せるのです。

「間口幅調整式逆解き挟みうち法」 　両者の探索パターンの増加傾向に違いがあると左図のように水色の探索部分が無駄なのです。そこで、両者の探索先端の間口幅に大きな差が生じないように、どちらの探索を優先するかを随時調整しながら進行します。すると右図のようにスッキリします。

→

「ハッシュ法(幅優先探索)」(Ver1.1)

「デッドゾーン(進入禁止域)」(Ver1.1)

「フリーズチェック(凍結状態検査)」(Ver1.1)

「局所探索法(閉空間ミニ探索)」(Ver1.3)

「間口幅調整式逆解き挟みうち法」(Ver2.7)

・ソースコード	soko207.java　(1997/10/15　24:00　update)
・その他の必要なファイル
	item0.gif	item1.gif	item2.gif	item3.gif	item4.gif
	item5.gif	item6.gif	item7.gif	item8.gif
・アプレットサイズ	width=400　height=364

　このソースコードはバグ取りで時々更新されることがあります。
　参考になる部分があればご自由に応用改良してかまいませんが、参考資料(高橋謙一郎作)として紹介して下さいね。