パターンの数
3x3パターンの数を調べてみました。
要素の種類は3つとします。スペース、荷物、壁を想定しています。
単純な組み合わせは、3の9乗で、19683です。
回転と反転による一致を考慮したところ、2862個でした。

この算出はそれなりに大変ですが、ここで必要な技術はソルバでも必要なものです。
皆さんもぜひやってみてください。
[PR]
# by sokoban | 2007-01-03 03:20 | パターン算出
CSS調整
クライアントブラウザのひとつであるFireFoxが、フォント指定できないことを、以前書きました。
サーバ側のCSSを直しました。このサイトがデフォルトで指定しているフォントを外しました。
これで、フォント指定できないクライアントでも、固定長で見ることができると思います。
[PR]
# by sokoban | 2006-12-30 14:43 | コラム
優劣の理由
優劣のある局面は、こんなものもあります。

 1)     2)
  ■■■■■  ■■■■■
  ----■  ----■
  --日-■  -日--■
  ■■■■■  ■■■■■

この1が優形、2が劣形です。
理由を、論理的に考えて見ましょう。

2において、荷物の右側のスペースの形は

  ○○○
  ×○○

となっています(丸部分)。このスペースの価値はどのようなものでしょうか。
通り抜けの通路にもならず、荷物をストックすることもできません。
1において、荷物の右側のスペースの形は

   ○○
   ×○

です。これは、2と比べても価値は同じです。
しかし荷物の左側のスペースは広くなっていて、価値が高くなっています。
よって、1の方が良い形であると言えます。
[PR]
# by sokoban | 2006-12-30 00:13 | 局面の優劣
押した方がいい形
この2つの形を考えます。

1)    2)
 ■--   ■--
 日--   -日-
 ■■■   ■■■

1を含む局面が解けないとします。そのとき、1が2の形になっても解けません。
2を含む局面が解けるとします。そのとき、2が1の形になっても解けます。
これを「1は2に優っている」「2は1に劣っている」と呼びます。

平たく言うと「2の形を見つけたら、とりあえず押して、1の形にしたほうがいい」
ということです。
この理論を私は「局面の優劣」と呼んでいます。
[PR]
# by sokoban | 2006-12-29 01:30 | 局面の優劣
パターン発見方法の補足
パターン発見の方法について、補足があります。
たとえば以下のようなもの。

日日-
日日-
---

これは単なる集四なので、排除する必要があります。
もちろんシチョウや準集四、角の死も排除します。

要するに、固定の死のような簡単に判別できるものが存在しないもので、
解くことができないものが、求めるパターンです。
[PR]
# by sokoban | 2006-12-29 01:11 | パターン算出
パターン発見方法
以下のようなテンプレートを用意します。
■■■■■■■■■
■十十十十十十十■
■-------■
■--○○○--■
■--○○○--■
■--○○○--■
■-------■
■大------■
■■■■■■■■■
丸印を可変部分とし、すべての組み合わせを調べます。荷物をすべてゴールに運べないのが、死に手パターンと言えます。とても簡単に数え上げることができます。
もちろん、反転・回転による一致と、「スペース→荷物→壁」変換による一致によって、パターンを絞り込みます。その結果、前述の4パターンが出てくるはずです。

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

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

■■■
日大日
---

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

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

 -■-
 日-■
 日日-

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

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

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