人気ブログランキング | 話題のタグを見る
パターン発見方法
以下のようなテンプレートを用意します。
■■■■■■■■■
■十十十十十十十■
■-------■
■--○○○--■
■--○○○--■
■--○○○--■
■-------■
■大------■
■■■■■■■■■
丸印を可変部分とし、すべての組み合わせを調べます。荷物をすべてゴールに運べないのが、死に手パターンと言えます。とても簡単に数え上げることができます。
もちろん、反転・回転による一致と、「スペース→荷物→壁」変換による一致によって、パターンを絞り込みます。その結果、前述の4パターンが出てくるはずです。

3x3の四角形だけでなく、いろんな形でこの方法が使えます。また、ゴールを含めたパターンも発見できます。

このアイデアは10年くらい前から持っているんですが、まだ深くはやってません。卒論や修論の題材を探している方、やってみませんか。
# by sokoban | 2006-12-26 23:26 | パターン算出
フォント
このブログでは、フォントが固定長であることが前提です。
たとえば、

■■■
日大日
---

↑こういうのがちゃんと正方形に見えなければなりません。
最近気づいたのですが、FireFoxではフォントの設定をどうしようとも、全角の四角形「■」のサイズが小さくなってしまいます。困ったものです。

FireFoxは好きでしたが、これにはがっかりです。私は普段、Operaを使ってます。おすすめです。
# by sokoban | 2006-12-26 22:48 | コラム
論文
えらく久しぶりに書きます。
以前紹介した小田原氏の論文が、いつのまにかPDFダウンロード可能になってました。面をいくつかに分割する手法のようです。ゴールが一箇所に集中している面向け。パターンマッチングでは小さいパターンに限定されるのに対し、この方法では大きさに強いという印象でした。
# by sokoban | 2006-12-26 22:45 | 文献
マッチング回数
このパターンでの基準座標は2つでした。
改めて、4つ3x3パターンについて基準座標を数えると、A,B,C.Dでそれぞれ2,2,4,2です。よって、マッチングの回数は2*8+2*8+4*8+2*8=80ということになります。
1手ごとにマッチングをするとしても、たいしたコストではありません。どの程度の効果があるかは検討の余地がありますが、これによって還って解けなくなる、という心配はありません。メモリの圧迫はなく、消費するのは時間だけだからです。
# by sokoban | 2005-02-06 23:12 | アルゴリズム
動かした荷物についてのマッチング
3x3パターンマッチングについてです。ここではこの形を例にします。

 -■-
 日-■
 日日-

さて、動かした荷物を基準としたマッチングでは、基準座標を決めます。このパターンでは、3つの座標がありえます。以下に×印で示しました。

1)
 -■-
 ×-■
 日日-
2)
 -■-
 日-■
 ×日-
3)
 -■-
 日-■
 日×-

このパターンは線対称なので、(1)と(3)は同じです。よって、基準座標は2つです。
それぞれについて回転・反転の8つの形でマッチングをすることになります。
なお、(2)は線対称なので、反転形を省くことができます。
# by sokoban | 2005-01-14 02:01 | アルゴリズム