改めて、スペース、荷物と壁の三種でやってみました。
予測どおり、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
| パターン算出
|
カテゴリ
以前の記事
フォロー中のブログ
その他のジャンル
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||