<   2007年 01月 ( 18 )   > この月の画像一覧
無駄なスペース
またまた、最小化して考えて見ましょう。
以下の×印は、無駄なスペースです。

  A)
   --■-
   --×■
   ■××■
   -■■-
  B)
   --■-
   ■××■
   ■××■
   -■■-
  C)
   ■×■-
   ■××■
   ■××■
   -■■-
  D)
   -■■-
   ----
   ■××■
   -■■-

以下の△印は、どれかひとつは必要がないスペースです。

  F)
   --■-
   --△■
   ■△--
   -■--

先に示した、局面の優劣に関するパターンと比べてみてください。
ある程度形が一致するはずです。
[PR]
by sokoban | 2007-01-29 23:35 | 局面の優劣
押したほうがいい形たち
局面の優劣に関するパターンは、算出方法はややこしいです。自動化はまだアイデアがありません。
机上では、以下のようなものを考えています。いずれも、荷物を右に押します。

   --■-
   ---■
   日--■
   ■■■-

   --■-
   ■--■
   日--■
   -■■-

   -■--
   ■---
   日--■
   -■■-

   -■■-
   ---■
   日---
   ■■■■

   -■■-
   ■--■
   日---
   -■--

   -■--
   ■--■
   日--■
   -■--

ほかにもありそうです。
[PR]
by sokoban | 2007-01-27 03:19 | 局面の優劣
押したほうがいい理由
主題を変えて、局面の優劣について再び。視点を変えて説明します。

  ■■■■■
  ----■
  -日--■
  ■■■■■

この形では、とりあえず荷物を奥に押し込んだ方がいいことは既に述べました。
最小化して理由を検討してみます。

   --■-
   ---■
   ■--■
   -■■-

この形において、無駄なスペースがあります。

   --■-
   --×■
   ■××■
   -■■-

この×印のスペースは、利用できないので、埋めても問題ありません。

もとの形において、荷物を奥に押し込む手は、無駄なスペースを埋め、かつ他に利用されうる領域を広げるものです。
また、どちらにしろ将来逆方向に押すことになりますが、それを妨げることにはなりません。
以上より、とりあえず押したほうがいいと言えます。
[PR]
by sokoban | 2007-01-26 00:08 | 局面の優劣
過去の算出結果との一致
「過去の算出結果との一致」を考えます。
前提として、過去の算出結果をデータベースなどに記録しておくことが必要です。

たとえば、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 | パターン算出
メモリ調整
メモリを調整し、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 | 同一チェック