メモリ調整
メモリを調整し、512MBまで使用可能にして試しました。3種4x3について、重複排除まで。

全組合せは3の12乗で531441個、重複排除後では134865個。
かかった時間は9分10秒でした。元は30分たってもできなかったので、同一チェックの改善は効果的だったといえます。

他のサイズの場合では、メモリ調整によって多少速くなりました。35秒が31秒になるという程度です。

インデックス法ではこの辺が限界かなと思います。4x4や3x5の場合は必要時間がぐっと増えるでしょう。ゴールを含めた4種についても考えると、さらに工夫が必要になりそうです。とりあえずはこのスピードでよしとして、3種4x3の規模までに限定して実験を進めることにします。
[PR]
# by sokoban | 2007-01-13 01:06 | 同一チェック
プログラミング
私はこの研究を、Javaでプログラミングしつつ進めています。この類のものは、配列やリストが大活躍しますので、そのあたりに強い言語を選ぶことになります。

最近Java SE 5.0を使い始めたのですが、これまでのJ2SDK 1.4に比べてとても便利になりました。Genericsです。 簡単に言えば、リストなどに型指定をするものです。これにより、プログラミングのミスで型が不一致、ということがありません。

列挙型もすばらしいです。回転、反転による8パターン(非正方形では4パターン)を示すものとして使ってみたところ、コードが簡潔でわかりやすくなりました。
[PR]
# by sokoban | 2007-01-12 03:25 | コラム
インデックス法
同一チェックを、インデックス法を採用して工夫しました。
考え方は単純で、3種の場合はそのうちの2種について、それぞれの数をインデックスとします。2種の数が一致する範囲では、全探索します。

たとえばこんなパターンとします。
 ABB
 AAA
 AAC
3種の数をそれぞれ数えると、Aが6個、Bが2個、Cが1個です。この場合はa=6,b=2をインデックスとします。AとBの数が決まればCの数が決まるので、これで十分です。

これだけですが、かなり時間は短くなりました。
2種4x4の場合3分以上かかっていたのが、30秒ほどになりました。
3種3x3の場合は13秒ほどだったのが1秒ほどです。
しかし3種4x3では、メモリ不足で失敗しました。あらためて、メモリの使用許可サイズを増やしてやってみることにします。
[PR]
# by sokoban | 2007-01-12 01:36 | 同一チェック
重複排除までのコスト
3種3x3パターンの算出において、全組合せに対して同一チェックをして、「重複排除後」として2862個が残るまでにかかる時間に注目します。この場合、13秒ほどでした。
これが2種3x3だと0.1秒もかかりません。2種4x3だと1秒程度、2種4x4だと3分以上になります。
3種4x3では、30分たっても終わりませんでした。このように、ちょっと広くなったり種類が増えたりすると、急激にコストが増大します。

今のところ、同一チェックにはたいした工夫がありません。いわゆるバカサーチで、全探索をしています。荷物や壁の数ごとにまとめておくとか、インデックスのようなものがあると良いでしょう。
同一チェックで定番なのはハッシュ法ですが、ちょっと複雑になるので、とりあえずは単純な手法でやってみようと思います。
[PR]
# by sokoban | 2007-01-11 01:50 | 同一チェック
三種の算出データ
三種3x3のパターン算出したときの、数値としてのデータを書いておきます。

---------------------------
全組み合せ: 19683 (= 3^9)

重複排除後: 2862 / 19683

荷物が無し: 102 / 2862
集四など死: 1494 / 2862
上記の残り: 1266 / 2862

重複排除後: 1154 / 1266

解があった: 1150 / 1154
解答できず: 4 / 1154
---------------------------

結果、4個でした。
時間は計り忘れましたが、数分規模でした。
[PR]
# by sokoban | 2007-01-11 01:21 | パターン算出
三種で算出
改めて、スペース、荷物と壁の三種でやってみました。
予測どおり、4つのパターンが算出されました。以前書いたA-Dとの対応は以下の通りです。

Aに対応:
   -■-
   日-■
   日日-
Bに対応:
   日日-
   ■-■
   日日-
Cに対応:
   ■日-
   日-■
   日日-
Dに対応:
   -日日
   日-日
   日日-

これにより、予測が正しいことを確認できました。
この調子で、より大きいパターンの算出もしたいところです。しかし、ちょっと大きくなると急激にコスト(この場合は時間)が増大します。例によって、いろいろと工夫が必要になってきます。
[PR]
# by sokoban | 2007-01-10 02:33 | パターン算出
変換による一致検査適用
スペース→荷物→壁の変換による一致検査を適用しました。その結果、残ったのはひとつのパターンで、予定通りこれでした。

   -日日
   日-日
   日日-

これで、スペースと荷物によるパターンについては終了です。次は壁を入れてやってみます。
[PR]
# by sokoban | 2007-01-10 01:23 | パターン算出
ソートしておく
一致を調べるときに重要なのは、ソートされていることです。これは倉庫番に限らず一般に言えます。ソート済みを前提とできるかどうかで、探索量がずいぶんちがいます。
たとえばこの場合では、「スペースが多いほど小さい」「壁が多いほど大きい」と定義し、昇順にソートしておきます。
また、最初のジェネレートの時に工夫すれば、最初からソートされた状態にもできます。この辺のテクニックは、規模が大きくなると効果が出てきます。
[PR]
# by sokoban | 2007-01-07 20:19 | パターン算出
変換による一致
20個が集四のものと書きましたが、間違えていました。
18個でした。ということは残り3個です。以下のようなものでした。

 -日日
 日-日
 日日-

 日日日
 日-日
 日日-

 日日日
 日-日
 日日日

これは、最初のひとつだけで十分です。うっかり忘れてましたが、スペース→荷物→壁の変換による一致を考慮する必要があります。
さて、この一致検査にもひと工夫があります。
[PR]
# by sokoban | 2007-01-06 04:17 | パターン算出
スペースと荷物だけのパターン
わかりやすいように、スペースと荷物の二種類としてみます。三種類の時と比べて格段に少なくなります。まずは二種類で、算出アルゴリズムを確立しましょう。

この場合は、以前書いた3x3の死に手パターン4つ(ABCD)のうち、以下のものだけが該当します。

D)
 -日日
 日-日
 日日-

これだけを導き出したら、パターンの算出が成功したことになります。

単純な組み合わせの数は2の9乗で512個。回転・反転を考慮して算出したら、102個でした。

この102個について、以下のテンプレートと簡易ソルバを使って、解けないものを調べます。

■■■■■■■■■
■十十十十十十十■
■十十-----■
■--○○○--■
■--○○○--■
■--○○○--■
■-------■
■大------■
■■■■■■■■■

その結果、21個のが解けないものでした。目的のパターンも含まれています。
残りの20個は、集四が含まれているものでした。あとは、集四チェックを追加するだけです。
[PR]
# by sokoban | 2007-01-04 22:35 | パターン算出