カテゴリ:パターン算出( 13 )
過去の算出結果との一致
「過去の算出結果との一致」を考えます。
前提として、過去の算出結果をデータベースなどに記録しておくことが必要です。

たとえば、3種3x3の算出では、2種3x3の算出結果を利用できます。
3種4x3では、2種3x3と3種3x3と2種4x3の結果を利用できます。

わかりやすく、2種3x3を過去の算出として、説明します。
この形が算出済みです。

   -日日
   日-日
   日日-

これを含む形ならば、解けないものと判断できます。

たとえば2種3x4では

   -日日-
   -日-日
   --日日

3種3x3では

   -日■
   日-日
   日日-

といったものが対象です。

この場合パターンが1個しかないのでそれほどの効果は期待できませんが、数が多いと効果があるかも知れません。また、対象が大きくなるほど効果が出てくると思われます。
[PR]
by sokoban | 2007-01-23 20:41 | パターン算出
3種5x2答え
3種5x2で算出されたのは、これでした。

■-日-■
-■日■-

この形は「固定の予備状態」として知っていましたが、予測の時点では忘れていました。自動算出はやっぱり頼りになりますね。
[PR]
by sokoban | 2007-01-18 01:59 | パターン算出
2種4x3
2種4x3で、死に手パターン算出までやりました。

---------------------------
全組み合せ: 4096 (= 2^12)

重複排除後: 1120 / 4096

荷物が無し: 1 / 1120
集四など死: 285 / 1120
上記の残り: 834 / 1120

重複排除後: 812 / 834

解があった: 810 / 812
解答できず: 2 / 812
---------------------------

算出パターンは以下の2つです。
1)
 -日日
 日-日
 日日-
 ---
2)
 日日-
 日-日
 日-日
 日日-

見ての通り、1は3x3で算出されたものと同じです。
「過去の算出結果との一致」の処理が必要ですね。規模が大きくなるにしたがって、重要になってきます。
[PR]
by sokoban | 2007-01-14 15:56 | パターン算出
3種5x2
3種5x2の死に手パターン算出をやってみました。事前予測では、以下のものひとつだけが算出されると考えていました。

 ■-日-■
 -■■■-

しかし結果は違いました。プログラムによって新事実が判明したことになり、嬉しい結果となりました。内容は後日改めて投稿します。予想してみてください。
[PR]
by sokoban | 2007-01-13 01:25 | パターン算出
三種の算出データ
三種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 | パターン算出