人気ブログランキング | 話題のタグを見る
三種で算出
改めて、スペース、荷物と壁の三種でやってみました。
予測どおり、4つのパターンが算出されました。以前書いたA-Dとの対応は以下の通りです。

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

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

   -日日
   日-日
   日日-

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

 -日日
 日-日
 日日-

 日日日
 日-日
 日日-

 日日日
 日-日
 日日日

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

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

D)
 -日日
 日-日
 日日-

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

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

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

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

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