【作る】倉庫番パズルの自動プログラム 【解く】

1 ：04/07/03 〜 最終レス ：12/01/06

国産パズルゲームの名作「倉庫番」の問題面を
自動で生成したり解いたりするには
どのようなプログラムを書けばいいでしょうか？
プログラムの達人から初心者まで
興味のある方は是非参加してください。

2 ：

公式
http://www.sokoban.jp/
クローン
http://perso.wanadoo.fr/mrbozo/sokoban/
http://www.sourcecode.se/sokoban/
http://www.sokomind.de/
問題面集
http://levels.sokomind.de/
http://www.sourcecode.se/sokoban/levels.php

3 ：

まずは、縦10 x 横10、荷物3個くらいまでの
小さな問題面(を作る・解く)からだと思うのですが
何から手をつければよいのやら
作るためにはまず解けなければならないのか、
それとも解くルーチンが脆弱でもそこそこは作れるのかな？

4 ：

>>1
疋田センセにでも聞け。糸終

5 ：

解けない面を作られても困るし作るよりも解く方が先。
で、そいつで解けるレベルのものなら作れると

6 ：

>>1
http://www.ic-net.or.jp/home/takaken/so/soko/index.html
http://www.ic-net.or.jp/home/takaken/nt/soko/index.html

7 ：

荷を引っ張る倉庫番プログラムなら簡単に問題作成できそう

8 ：

どっかで問題作成をプログラミングしてたような気がするが、どこだったかは忘れた

9 ：

疋田センセの書いたプログラムってネット上には無いの??
bit vol.26-27に紙か磁気で公開されてたりすんのかな。
あったとしても1994年だとWindows上では無理か。
Rogue系みたいに、毎回自動で作られたマップを遊べる倉庫番
なんてのがあるとアツイんだけどなー

10 ：

すぐ飽きるとおもう一部の変質者以外

11 ：

マルチスレか。良い根性してるな。

12 ：

＃＃＃＃＃＃＃＃＃＃
＃　　＄　　．　　＃
＃　　　　　　．　＃
＃　　　　＄　　　＃
＃＃　　　　　．　＃
＃＃＃　　＄　　＃＃
＃＃　＠　　　　　＃
＃＃＃＃＃＃＃＃＃＃
こんなんばっかになりそう。

13 ：

>>12
そんなんツマンネ
ざっと見た感じ17歩くらいか
難易度設定できたら
少しはマシになるかもな
n=ユーザー設定項目クリアに必要な最低歩数;
while(n歩以下で解けたら){やり直し;}
で50歩くらいを設定しとけば
少しは手応えのある面になると思うが

14 ：

>13
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃　＄　　　　　　　　　　　　　　．＃
＃　＄　　　　　　　　　　　　　　．＃
＃　＄　　　　　　　　　　　　　　．＃
＃　＄　　　　　　　　　　　　　　．＃
＃　＄　　　　　　　　　　　　　　．＃
＃　＄　　　　　　　　　　　　　　．＃
＃　＄　　　　　　　　　　　　＠　．＃
＃　　　　　　　　　　　　　　　　　＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

15 ：

>>13
手数 * (1 / 正当数) = 難易度
とかの方が良くないか？>>14みたいに手数は多いが同時に正当数がいっぱいある奴は当然難易度は下がると。

16 ：

あとは面の広さか若しくは移動可能チップ数
さらに荷物の数も要素に加えて難易度を算出すれば
精度が高まる気がする。

17 ：

倉庫番を解く for Windows
http://www.ic-net.or.jp/home/takaken/so/soko/index.html
参考にどうぞ

18 ：

10×10の中心からランダムに領域を広げていくという方法で作った部屋の例1
＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃
＃　　　　　＃＃＃＃　　＃＃＃　　　　＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃
＃＃　＃＃　　　　＃　　＃＃＃　　　　　＃＃　　＃　＃＃＃＃＃＃　＃　　＃＃＃＃＃＃＃＃＃＃
＃＃　　　　　　　＃　　＃＃＃　　　　　　＃　　＃　　＃＃　　　　＃　　＃＃＃＃＃＃＃＃＃＃
＃＃　　　　　　＃＃　　＃＃＃　　＃＃＃＃＃　　＃　　　　　　　　＃　　＃＃＃　　　　　＃＃
＃＃＃　　　　　＃＃　　＃＃＃　　＃　＃＃＃　　＃　　　＃　　　　＃　　＃＃＃　　　　　　＃
＃＃＃　　　　　　＃　　＃＃＃　　　　　＃＃　　＃　　　＃　　　　＃　　＃＃＃　　　　　　＃
＃＃＃　　　　　　＃　　＃＃＃　　　　　　＃　　＃　　　　　　　　＃　　＃＃＃＃＃＃　　　＃
＃＃　　　　　　　＃　　＃＃＃　　　　＃＃＃　　＃＃　　　　　　　＃　　＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃

19 ：

10×10の中心からランダムに領域を広げていくという方法で作った部屋の例2
＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　
＃＃＃＃＃＃＃　＃＃　　＃＃　　　　　＃＃＃　　＃＃＃＃　　＃　　＃　　＃　　＃　＃　　　＃　
＃＃＃　　＃　　　＃　　＃＃＃　　　　＃＃＃　　＃＃＃＃　　＃　　＃　　＃　　＃　　　　　＃　
＃＃　　　　　　　＃　　＃＃＃　　　　　　＃　　＃＃＃＃　　　　　＃　　＃　　　　　　　　＃　
＃＃＃　　　　　　＃　　＃　　　　　　　　＃　　＃＃＃　　　　　　＃　　＃＃　　　　　　　＃　
＃＃＃　　　　　＃＃　　＃　　　　　　　　＃　　＃＃＃＃　　　　　＃　　＃　　　　　　　　＃　
＃＃＃　　　　　＃＃　　＃　　　　　　　　＃　　＃＃＃　　　＃　　＃　　＃＃＃　　　　　　＃　
＃＃＃　　　　＃＃＃　　＃　　　　　　　　＃　　＃＃　　　　＃＃　＃　　＃＃＃　　　　　　＃　
＃＃＃＃　　＃＃＃＃　　＃　　　＃　　　　＃　　＃＃　　　　＃＃＃＃　　＃＃＃＃　　　　　＃　
＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　　＃＃＃＃＃＃＃＃＃＃　

20 ：

＃と全角スペースが同じ幅になるようなフォントで見て下ちい。

21 ：

ジャーナル アブストラクトVol.39 No.03 - 007
「倉庫番」の問題の自動作成
http://www.ipsj.or.jp/members/Journal/Jpn/3903/article007.html
ぐぐったらこんなん見つかった
でも会員じゃないと内容読めないみたい

22 ：

読んでみたけど別段どうという事のない論文だな。
普通にプログラミングの能力のある人なら
考え付きそうな事をやってるだけで。
作ってる問題は　盤は8x8, 荷物は3つ。
リンク先にあるように
・問題作成→解を求める→面白さを評価
というステップを繰り返して、詰まらない問題は自動判定して捨てて、
面白い問題がいくつ出来るか、とかやってる。
実験結果の例
　作成失敗　2
　解なし　153
　解ありだかつまらないと自動判定されて捨てられた　287
　解ありでプログラムで捨てられなかった　58
合計　500
500回ループさせて残った問題が58。そのうち筆者が実際に解いて
面白いと感じられた問題が13だったと。

23 ：

部屋の作り方
・初期状態は以下のようにする。
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
＃＃　　　　＃＃
＃＃　＃＃　＃＃
＃＃　　　　＃＃
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃
これに下の3つのパーツをランダムに投下して部屋を作る。
口口　（3*2の空白パーツ）
口口
口口
口口　（2*2の空白パーツ）
口口
口口口　（3*3の空白パーツの中央に壁）
口＃口
口口口
部屋のパーツを選ぶ事でつまらない部屋が出来ないようにするらしい。

24 ：

ゴールをおけないパターンにはどういうものがあるか考察してあり、
（まあ、ある程度考えれば考え付くようなパターン）
それをさけてゴールをランダムに配置。
また同様にある程度考えて荷物と人を配置。
面の作成はそれくらい。
次のステップで幅優先探索で最短の解を求める。
次の評価のステップだが、面白さの評価基準は
(1)手数、(2)荷物の持ち替え回数、(3)遠回り数、(4)部屋の広さ（マスの数）
を基準に判定している。
遠回りというのは、みかけの荷物とゴールの最短距離と
実際に荷物が移動した距離の差、らしい。
（距離は“マンハッタン距離”とか書いてある。）
持ち替えとは今持っている荷物を離し別の荷物を押す事を示す。
荷物の持ち替えが　多く必要な程、面白いと判断されるから、との事。
判定の具体的な数値は
・遠回りせずに解ける
・荷物の持ち替えが3回以下
・解が6手以内
の一つ以上あてはまったら、この問題を捨てる、との事。
考察に置いて、プログラムに実装されているかどうかに関わらず
以下のように述べている。
・荷物の持ち替え数のパラメータは難しさの評価に有効と言える。
・荷物の方向転換。面白い問題では同じ荷物を押し続ける時でも
　こまめに方向転換する必要がある傾向が認められる。
・手数。多い方がよいが、単に荷物とゴールの距離が遠いだけの事もある。
・遠回り。発見しやすい遠回りもあるので面白さに直結しない場合もある。

25 ：

考察の続き
・ゴールが邪魔。ゴールが隅の邪魔にならない所にあるのは簡単になりやすい。
　面白い問題の多くはゴールを荷物が何度も通過する。
・荷物の軌跡が複雑。荷物の軌跡が他の荷物の軌跡と交差したり
　絡み合ってると面白い事が多い。しかし軌跡が重ならなくても
　面白いものはある。
実際に作成された問題の例
（＃:壁, ・:ゴール, ＄:荷物, ■ゴール＋荷物, 人:人）
＃＃＃＃＃＃＃＃　＃＃＃＃＃＃＃＃
＃＃＃　　＃＃＃　＃＃＃＃＃＃＃＃
＃＃　　　　＃＃　＃＃　　・　＃＃
＃　・　・＄＃＃　＃＃人＃　■＃＃
＃　　＄人　　＃　＃＃　　＄　＃＃
＃＃＃＃■＃　＃　＃＃　＃■　＃＃
＃＃＃＃　　　＃　＃＃　　　　＃＃
＃＃＃＃＃＃＃＃　＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃　＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃　＃＃＃＃＃＃＃＃
＃＃　　　　＃＃　＃＃　・　■＃＃
＃＃・＃＃＄　＃　＃＃　　＃　　＃
＃　・・＄　　＃　＃＃人＄■　　＃
＃　　＃＄　　＃　＃＃＃　　　＃＃
＃　　人　＃＃＃　＃＃＃　　　＃＃
＃＃＃＃＃＃＃＃　＃＃＃＃＃＃＃＃
（以上）

26 ：

荷物をゴールに置いて逆の動作で荷物を移動して
問題を作ればいいかなと思っていたんだけど
著者らはそういう事はしていないですね。

27 ：

なるほど、つまり･･･
１：壁とゴールと人の最終形をランダムで作成。
２：ランダムに一つずつ荷物を引く
３：その形の最短手順を調べる
４：一番手数の多い面を初期配置とする
ってことか。

28 ：

いや待てよ、２：の引っ張りは、同じ形を繰り返す可能性が高いから無駄が多いかも。
だとしたら･･･
２：荷物を移動させた全パターンを調べる
３：一番最短の手数の多い面を初期配置とする
のほうが速いかもな。
なんか結局上のと似たようなものになってしまった。

29 ：

どうでも良いがいい加減空白調整してくれ。
読むに至らない論文は内容に依らず勝ちはない。

30 ：

マカー。

31 ：

自分で見てるとバッチリなんですよねぇ

32 ：

あれ？矯正IDになってる？

33 ：

? この板始めてだからよく知らない。（プログラム技術板からついて来た）

34 ：

漢なら自動プログラムなどに頼るな

35 ：

日経ソフトウエア2004年6月号
地球にやさしいアルゴリズム第8回
倉庫番を解くアルゴリズム
http://software.nikkeibp.co.jp/software/download/down04c.html
http://software.nikkeibp.co.jp/software/download/0406/algo0406.zip
さくら美緒、takaken、DeepGreen、疋田輝雄、
どのSolverが最も賢い？

36 ：

人が歩いた歩数でなく、荷物が動いた歩数で考えた方が楽なのだろうか？

37 ：

完成状態の盤面を0番として記憶しておく。
初期の荷物の状態を1として、そこから移行できる全状態を2以降の番号をつけて生成し、記憶。
１番からどの番号へ移行できるかも記憶しておく。
続いて、２番の状態から移行できる全状態を生成し、記憶。もちろん重複チェックもさせるので
前の番号へ移行できるような状態も作られる。
次々に生成していって、０番への移行ができるような盤面が現れたら解決方法あり。
１番からの深度チェックをしていって、荷物を何手動かしたかの最短を出す。
ただし確実な最短を出すためには全手数のチェックが必要。
解く方のやり方を想定してみたが、こんな感じなのか？

38 ：

大体そんな感じだと思う。
＞ただし確実な最短を出すためには全手数のチェックが必要。
幅優先探索でやれば最初に見つかったのが最短手順。
「幅優先探索」で検索してみて。
＞もちろん重複チェックもさせるので前の番号へ移行できるような状態も作られる。
？　前と同じ状態に戻る場合は発生させなくてよいと思う。

39 ：

指数オーダーで状態が増えていくから全列挙ベースじゃ規模の小さい問題しか解けない。
これは探索の方向を変えたところでどうしようもない。
人間が解いて面白いような規模の問題を解くのは無理っぽい。
で、どうするかというとA*とか分枝限定法とかの下界値を利用して枝刈りするような手法が使われる。
もっともそっちの世界でも倉庫番は難しい問題として知られてるから、良い方法が作れればそれだけで論文書けるかも。
まあ、そこまでいかなくても単純なA*くらいは入れた方が良いと思う。
経路探索にも使える（というかそっちの方が多い）から知ってて損はないし。

40 ：

ご意見どうもでつ。なるほど、かなり奥が深そうだ。
調べてみたら、双方向探索とか行き詰まりのつぶしとか色々あるようだし。

41 ：

プログラムによる自動生成全52面
ttp://www.ne.jp/asahi/ai/yoshio/sokoban/auto52/index.html

42 ：

>>41
そのプログラムそのものはどこかにないの？

43 ：

移転前
ttp://web.archive.org/web/20020609073807/http://www.ne.jp/asahi/ai/yoshio/sokoban/main.htm
自動生成のプログラムそのものはないみたい

44 ：

この小田原研究が見たいが、見つからない。
ttp://www.graco.c.u-tokyo.ac.jp/kawai-kaneko-lab.html

45 ：

>>35をコンパイルしたの頂けないでしょうか

46 ：

>>45
バイナリじゃないんだ。。。
readme.txtによるとBorland C++ Compilerでビルドせよとのこと。
Borland C++ Compilerは以下から無償で入手できるよ
http://www.borland.co.jp/cppbuilder/freecompiler/bcc55steps.html
メール登録(無料)が必要らしいね。
さすがにユーザー登録的な手続きまでするのは面倒くさいから
気が向いたら自分でチャレンジしてみて。
コンパイル自体は楽勝で誰だって出来るから

47 ：

いきなりネタ無くなってる感がするんだが
他のパズルの自動プログラムもＯＫ？

48 ：

基本は変わらないし、参考になるから
いいんじゃないか？

49 ：

それじゃ、昔やったナンバーリンクの自動解答に挑戦してみる。

50 ：

49だが、ハンドルさらし。とりあえず今日は面を読み込んで表示するところまでできた。
で、ナンバーリンクとは何かだが、ぐぐれば判るとおりマス目に書かれた同じ数字を
線で結んで全部繋ぐ紙面パズル。だが、これが別解を見つけるのが異様に困難な
パズルだったりする。複数解があるのは紙面パズルとして致命傷。
ショートカットでつなげられる答えがあるなどもってのほかだったりする。
自動で解くプログラムはいくつかあるようだけど、線が通らないマス目がある別解は
見つけられない。なので自分が挑戦してみようかと、こういう経緯。

51 ：

んで実際にどうみつけるかだけど、いろいろ探ってみたところ
ここに線が引かれるはずだから、あーしてこーして・・・なんて線を延ばすやりかたがほぼ全部。
でも、このやりかたって、ショートカット解はみつけられなかったりするんだよな。
なんたって角地に線が通ることをまず確定させてるし。
で、自分が考え出したパターンはこれとは違い、線ではなくて壁を見るやりかた。
線を引かない部分を壁として、その壁の有無を総あたりでチェックする方法。
具体的なやりかたは次回に。

52 ：

すまんけど、解説するとかなり長々した文になりそうだ。
スレ乗っ取りになりそうなので、どこか別の糞スレに移って
そこで解説したほうが良さそう。

53 ：

>>52
いや、このスレもうほとんど止まってたし・・・このまま進めて欲しいな

54 ：

>53
そうか、ならば・・・

55 ：

　　　 ,ｨｨr--　 ..__､j
　　 ﾙ! {　　　　　　 ｀ヽ,　　　　　　　∧
　 N { l `　　　　,、　　　i　＿|＼/ ∨　∨
　 ゝヽ　　　_,,ｨjjハ、 　 |　＼
　　`ニr‐tﾐ-rr‐ｔｭ<≧rﾍ　　 >　ここはしばらくMNR（もっとナンバーリンクの会）が
　　 　 {___,ﾘ ヽ二´ﾉ　 }ｿ　∠　乗っ取らせてもらうことにする！！
　　　　'､ `,-_-ｭ　 u /|　　 ∠
　　　 　 ヽ`┴ '　／／l＼　　|／＼∧　 /
--─‐ｧ'|　｀ニ--‐'´　/　 |`ｰ　..__　　 `´
　 　 く__レ1;';';';>､　 /　__ |　 ,=､　___
　　 「　∧ 7;';';'|　ヽ/ _,|‐､|」 |Ｌ..! {L..l　))
　　 |　 |::.V;';';';'|　/.:.|トl｀´.!　l _,,,ｌ | _,,|　 , -,
　 　 !　|:.:.:l;;';';';'|/.:.:.:||=|=; |　| 　 | |　.l /　〃 ))
　　　 l |:.:.:.:l;';';'/.:.:.:.:| ! ヽ　＼!‐=:l/ `:lj　 7
　　　 | |:.:.:.:.l;'/.:.:.:.:.:.! ヽ:::＼::　 ::::|　 ::l　/

56 ：

　　　　　　＿人人人人人人人人人人人人人人＿
　 　 　 　 ＞　　　　な　なんだってー！！　　　　＜
　　　　 　 ￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^￣
　 　 　 　 _,,.-‐-..,,_　　　　　　 _,,..--v--..,_
　　　　／　　　　　｀''.v'ν　Σ´　 　 　 　 `､_,.-'""｀´""ヽ
　　　 i' 　 ／￣""''--i 7　　 | ,.ｲi,i,i,､ ､,､ Σ　　　 　 　 　 ヽ
. 　 　 !ﾍ /‐- 、u.　　 |' 　 　 |ﾉ-､ ' ` `,_`　| /i'i^iﾍ､ ,､、 　 |
　　　 |'' !ﾞ　i.oﾆ'ｰ'〈ｭﾆ! 　 　 iiヽ~oj.`'<_o.7 !'.__ ' ' ``_,,....､　.|
.　　　,`| u 　 　 　 ..ゝ! 　 　 ‖　 .j　　　　 (} 'o〉 `''o'ヽ　|',`i
_,,..-<:::::＼ 　 (二> ／　 　 　 ! 　_`-っ　 / | 　7　　￣ u |i'/
. |、　＼:::::＼　'' ／　　　 　 　 ＼　''　／〃.ヽ `''⊃　　,　'v>、
　!､＼　 ＼.　,￣　　　　　　　 γ/|￣　〃　　 ＼二-‐' ／／`

57 ：

　　 　 _,,.-‐-..,,_　　　　
　　／　　　　　｀''.v'ν
　 i' 　 ／￣""''--i 7　
　 !ﾍ /‐- 、u.　　 |' 　 ちょ、ちょっと待ってくれよキバヤシ、
　 |'' !ﾞ　i.oﾆ'ｰ'〈ｭﾆ!　　ナンバー（NUMBER）リンク（LINK）だったら
　,`| u 　 　 　 ..ゝ!　　 頭文字はMNLに・・・
<:::::＼ 　 (二> ／ 　　
　＼::::＼　'' ／
＼　＼.　,￣
　　　　＿

58 ：

　　 |丶　　　＼　　￣￣~Ｙ〜　､
　　|　　＼　＿＿　　　　/　　　　＼
　 |ゝ､ヽ　　─　　　　　/　　　　ヽ　|
　│ ヾ　ゝ＿　　　　　　　　　＼　　|
　│　　ヽ＿ ＿ ／　/| |＼　　　＼｜
　　＼ヽ　　　＿ ／/ / |　　＼　　 ｜
　　　ヽ＼二＿二//　∠二二二| ﾍ| 　　　ナワヤ！勘違いをするな！
　　　　| | | ヽゝｿゝ|TT|<ゝｿ ﾌ　|/ｂ｝ 　　　日本放送協会（NHK）的な
　　　　ヾ| ヽ＿__ ﾉ/|| .ミ＿＿ ﾉ | ﾉ 　　　　略語だから何の問題もない！
　　　　　 | 　 　 　 �凵@　　　　 /ﾌ
　　　　　　|　u　.F二二ヽ　　 /|/
　　　　　　＼. 　 |/⌒⌒|　　 ｲヽ
　　　　　　/. ＼　 ＝＝′／ |.| |
　　　　 ￣|｜　 ヽ＿＿／　　/ /￣
　　　　　　＼ヽ＿＿＿＿＿ノ ﾉ

59 ：

　　 　 _,,.-‐-..,,_　　　　
　　／　　　　　｀''.v'ν
　 i' 　 ／￣""''--i 7　
　 !ﾍ /‐- 、u.　　 |' 　
　 |'' !ﾞ　i.oﾆ'ｰ'〈ｭﾆ!　・・・・・・・・・
　,`| u 　 　 　 ..ゝ!　　
<:::::＼ 　 (二> ／ 　　
　＼::::＼　'' ／
＼　＼.　,￣
　　　　＿

60 ：

すまん、連続投稿に引っかったから普通に進めることにする。←バカ者

61 ：

とりあえずナンバーリンクそのものの説明は以下のURLで
ttp://www.nikoli.co.jp/puzzles/4/
で、このパズルだけど解き方の基本としてえいやっと線を引くってのがメインだったりする。
理詰めで少しづつ解いていくんじゃなくて、直感が大半な珍しいパズルでして・・・
で、作る方も同じく直感で作るわけだけど、困ったことに別解チェックがとても大変。
なんたって理詰めで解いていくパズルでないだけに、意外なところから線が引けたり
マス目が全部埋まらないショートカット解があったりと、難儀だったりするんだな。

62 ：

で、これを解く為のソルバープログラムなんだけど、検索してみたところ
ソフトの存在はベクターに一つだけって状況で、しかもそれはショートカットの別解を
チェックできなかったりする。他のページの日記には、これの解答ソフトは
要望はあるけどモノが無い、と書かれている存在だそうで。
だったら俺が作ってやろうと思い立ったわけで・・・っていうか、実は理論なら
とうの昔にできていて、しかもその内容がとあるトコに掲載されたこともあったりして。
かなり昔のことなんだけどね。資料はまだ残っていたから作成はできるはず。
ただ、今回はこれを別解を確認できるように拡張していくという課題も追加。

63 ：

さてさて、それで具体的なやり方だけど、上に書いてあるとおりマス目に線を引くんじゃなくて
線を通過しない壁のほうに重みを置いてみる解き方です。
例えば上のニコリのページの問題。一番上の左端のマス目を通る線は
必ず右と下を通過するはずです。普通ならこの角の理論を適用して線を延ばしていくのですが
自分の考えはここからが違う。線を引く部分でなく、線を引かない上と左の壁に注目しました。
判りやすく下の答えを見てみましょう。線を引かない境界の点線に壁を引っ張ると
二つの法則を導きだされます。
　「線を引くマスは必ず２方向が壁になる」
　「数字の書いてあるマスは必ず３方向が壁になる」
この壁の数を利用して解いていこうというのが、自分の理論です。

64 ：

具体的には、あるマスAにおいて上と左の壁数を確認します。
線を引くマスで上と左の壁数が
　０なら、右と下は必ず壁になる。
　１なら、右か下、どちらかが壁。
　２なら、右と下は必ず壁が無い。
数字のマスで上の左の壁数が
　０はありえないので、それ以前の壁がおかしい
　１なら、右と下両方が壁になる。
　２なら、右か下、どちらかが壁。
どちらかが壁の場合、仮に右を壁にして下を無しにしておいて次のマスへ進み
ありえない状況になったら戻って下だけ壁に変更して調べなおし、というやりかたです。
それでも駄目ならさらに前に戻って壁を変更します。
これを左上のスタート地点から右へと進めていって、右端についたら改行して
２段目の左端から、と進めていきます。ようするにしらみつぶしなんですね。

65 ：

でもこのしらみつぶし、結構有効な方法だったりします。
線を伸ばしてどっちへ行くのか調べるとなると、それこそ上下左右好きな方向に
進められるので、相手の数字につくまで途方も無いパターンがあります。
が、この方法で調べていくなら少ないパターンで進めていける上に
壁に矛盾が無くなったら、最後に同じ数字同士が連結しているかを
チェックするだけですみます。
とりあえずこの上と左を見るやり方を、ガンマ方式と名づけます。命名理由は変換したらわかるはず。
実際には、これに加えてありえない壁の形になったらNGにするようプログラムした結果
11×11の面を即断で解けるようになりました。はい、実はもうプログラムはできてます。
今日一日でなんとか完成しました。ただ、盤面入力はテキストファイルだし、結果出力は
イメージに文字出力のみだしで、見た目がかなり汚いので発表はまだです。
っていうか、じっくり解説しながら作ろうと思ってたのに、一日でできるとは自分でもおもわなんだ。
というわけで今日はこれにて。

66 ：

続き〜
そういえば、まだショートカットの探索方法書いてなかったな。
基本的には同じだけど、ショートカットができるってことは何も通らないマス目があるってこと。
これを便宜的に「壁マス」と呼ぶことにして話を進めます。
で、そこの部分の壁をどうするかだけど、線マスと壁マスの間は必ず壁があるが
壁と壁同士はあっても無くてもいいことになってややこしい。なので、壁マスは四方を必ず
壁に囲まれていると定義しておく。その考えで上の探索に追加。
線を引くマスで上と左の壁数が
　０なら、右と下は必ず壁になる。
　１なら、右か下、どちらかが壁。
＊２なら、右と下は必ず壁が無いか、壁マスとして両方とも壁。
＊の部分の探索を追加するだけ。ただ、これをやると探索数が一気に増えます。
７＊７のショートカット解のみの面でテスト
ショートカット探索無し：解答0。79回探索。
ショートカット探索有り：解答430。3114906探索。
7＊７ショートカット解なしの面でテスト
短絡無し：解答１。196回探索。
短絡有り：解答０。2992135回探索。
11＊11の面でテストしましたが、短絡ありだと３０分かけても戻ってきませんでした。
これでは実用にならないのでもうちょっと考えて見ます。

67 ：

┌─┬─┬─┬─┐
│┏┿━┿━┥１│
├╂┼─┼─┼─┤
│┃│２┝━┥２│
├┸┼─┼─┼─┤
│１│３┝━┥３│
└─┴─┴─┴─┘
こんなのどう？

68 ：

>67
そんなふうにやりたいですなー。
ところで、最後に同じ数字を結んでいるかをチェックするのを
壁作成途中でもチェックするようにした結果
7＊７ショートカット解なしの面でテスト
短絡無し：解答１。196→181回探索。
短絡有り：解答１。2992135→435102回探索。
と短くなりました。
（上の短絡有り：解答０。は解答１の間違いです。）
このおかげで15＊15の面を短絡無しで
100秒かかっていたのが１秒かからなくなりました。
でも短絡ありだと10＊10の面で帰ってこなくなるので、まだまだなにか
画期的なアイデアが必要です。

69 ：

最終ﾁｪｯｸ＝マス目に壁が全部埋まった時点で全部の数字の到達先を調べる
途中ﾁｪｯｸ＝現在のマスが数字で上か左が開いていたらリンク先を調べる
改行ﾁｪｯｸ＝マスが一段埋まるたびにマス確定した上段数字マスの到達先を全部ﾁｪｯｸ。
7*7での回数
ｼｮｰﾄｶｯﾄﾁｪｯｸ　あり　なし
最終ﾁｪｯｸのみ　181　435102
+途中もﾁｪｯｸ　 179　303781
+改行もﾁｪｯｸ　　167　228814
数は減らせたけど、指数的に減ってないのでダメです。
10*10でｼｮｰﾄｶｯﾄありだと、探索が遅くなるばかりで解ける気配がぜんぜんありません。
ちなみに回数とは、最初のマスの壁の有無を確定して１回、次のマスの壁を確定して2回
という風に数えてます。それを考えると３ケタですんでるのは驚異的なんだけどね。
でもｼｮｰﾄｶｯﾄ探索ありだと、ぜんぜん太刀打ちできないんだよな。

70 ：

ところでパズル板ができたね。
http://hobby5.2ch.net/puzzle/
とりあえず７＊７までならチェックできたし
これ以上の改良は、なんかとてつもなく長くなりそうだから
一旦ここで打ち切って、移動した方がよさげ。
倉庫番探索もそのうち考えます。

71 ：

あ゛〜、見てるだけで終わってしまった。

72 ：

なんか新しいパターンがあったら伝えますですのことよ。
ところで倉庫番で考えてるんだけど、荷物の位置を不確定にできないかなというアイデア。
例えば４×４の空間に荷物一個と人がいるとして
中央四つのどこかに荷物がある可能性がある場合はその場所をBとして
■■■■■■
■　 　 　 　 ■
■　 B .B 　 ■
■　 B .B 　 ■
■　 　 　 　 ■
■■■■■■
こんな感じにどれかに存在する可能性がある

73 ：

で、それを上に押し付けた場合は
■■■■■■
■　 B .B 　 ■
■　 　 　 　 ■
■　 　 　 　 ■
■　 　 　 　 ■
■■■■■■
こんな風に不確定の位置が変わる。
まだ大雑把な考えだから、これからどう発展させるかはわかってませんが
こんなアイデアもあるよということで晒しておきます。

74 ：

こっちにも報告
ナンバーリンクソルバーが形になったよ。
15*15でも１時間以内で解けます。
ttp://www.interq.or.jp/moonstone/person/numlink/index.html

75 ：

自主制作報告のほうにもｱｹﾞたけどこっちにも
ttp://gamdev.org/up/img/1872.lzh
とりあえずは２ｃｈ上でやりとりできるようなシステムを作った
ボタンでマップチップのテキストを置く
テキストのセーブ＆ロード
ステップの戻しと前進
プレイ中の面をテキストへコピー
プレイしたステップをテキストへコピー
書き出したステップをプレイ開始時に読み込み
■■■■■■■×
■×××××■■
■×田回回回×■
■×回××回足■
■×回××回×■
■×回回回◎×■
■×××××■■
■■■■■■■×
ddldllURdllluuuuurrrDDDuuullld
dRRDrUllluurD
こういう感じで面と解答ステップのやりとりが２ｃｈ上で可能に。
肝心な作り方と解き方は全然だけどな。

76 ：

このスレなにげに楽しみにしてるのでがんがれ

77 ：

あー

78 ：

ふと考えた。倉庫番を解くプログラムを作る前に、スライドパズルを
解けるようなプログラムを作らないとダメなのではないだろうか？
もっと考えて、１５パズルを解けるようなプログラムを作らないと
ダメなのではないだろうか？

79 ：

作れるんじゃね？

80 ：

つーか
ttp://www.ic-net.or.jp/home/takaken/so/15pz/index.html

81 ：

82 ：

【北朝鮮】「悪いやつらをなくそう」 国家公式サイトにオンラインゲーム登場　日本人と米国人の泥棒を退治　
ttp://news19.2ch.net/test/read.cgi/newsplus/1150945519/l50
北朝鮮がゲーム作ったと思ったら、ルールも面も日本のパクリだったよｗ

83 ：

状態空間探索も知らずに頑張っていたのか・・・

84 ：

しかし倉庫番というのはなんでああも中途半端な所へ荷物を「片付ける」必要があるのだろう。

85 ：

>状態空間探索
詳しく

86 ：

>>75
最近、倉庫番のはまりだまして活用させて頂いております。
大変ありがとうございます。

87 ：

携帯版 倉庫番Firststep の37面が
かれこれ数年解けません orz

88 ：

絶対荷物を移動させない位置を塗り潰し
荷物ごとに可動範囲を設定
目標には置ける可能性のある荷物のインデックスでも持たせる
ある程度絞り込めそうだけど、どうだろ
書いてると作りたくなるｗ

89 ：

http://vintermann.paranoidkoala.org/archives/000077.html
この人のがどうなったのか気になる
なんかすごい自信満々なんだがソルバがおいてない…

90 ：

YASGenあるじゃん

91 ：

人がうろうろさせると探索空間が発散するので、
人の厳密な位置を無視して、
荷物の配置だけを状態とみた木で探索したら
木が小さくなったりしないかな。
荷物の配置が決まると「荷物を押さずに動ける範囲」という
部分空間がいくつかできる。
人の位置は、今どの部分空間にいるか？という情報だけに縮退させる。
最短解は出ないけど、荷物の移動回数の最短解と言う形でとりあえずの解は
効率的に出せそう。
このアプローチで組むのってすでにいっぱいやられてたりする？

92 ：

自分は聞いたことはないな。
しかし、情報は「どの部分空間にいるか？」で持つよりも
「荷物をどっち方向に動かせるか？」で持った方が良くないか？

93 ：

>>92
なるほど。
今のところ、部分空間の内で一番数字の若い位置を
その部分空間を特定する情報にして組み始めてた。
確かに >>92 まで出してからデータベース化した方が
最探索時に早いね。
データ量と一致判定の速さもそんなに変わらないし。
そっちに変えてみよう。

94 ：

うーん。xsokoban の screen.1 すら解けないな(笑)
７段目くらいで8000×3500程度の探索済み重複チェックが終わらない。
盤面みると全然進んでない。
まあハッシュすら使ってないし仕方ないか

95 ：

意外に一般的なやり方のようでした。
意外でもないわ。

96 ：

そうなの？

97 ：

google 上位の pdf の初心者向けソルバ解説とかそれだった
その後、ゴール部屋の中での最後の荷物整理部分をなくして、
ゴール部屋の玄関までくれば荷物が消えるようにしてxsokoban の screen.1 はクリアした。
ヒューリスティック過ぎて好きじゃないが。
ゴール部屋の自動検出も一応考えたが、実装がちょっと大変そう…
XSokoban は結構この手の無駄に広いゴール部屋があるのよね。
ソルバ対策？

98 ：12/01/06

こんな記事がITproにあった
地球にやさしいアルゴリズム
第8回　倉庫番を解くアルゴリズム
http://itpro.nikkeibp.co.jp/article/COLUMN/20070411/268003/