【作る】倉庫番パズルの自動プログラム 【解く】
■ このスレッドは過去ログ倉庫に格納されています
0001名前は開発中のものです。
04/07/03 08:04ID:/HqS7Sh0自動で生成したり解いたりするには
どのようなプログラムを書けばいいでしょうか?
プログラムの達人から初心者まで
興味のある方は是非参加してください。
0042名前は開発中のものです。
04/08/01 11:46ID:YiQa0gMzそのプログラムそのものはどこかにないの?
0043名前は開発中のものです。
04/08/01 14:16ID:VNo3uGvtttp://web.archive.org/web/20020609073807/http://www.ne.jp/asahi/ai/yoshio/sokoban/main.htm
自動生成のプログラムそのものはないみたい
0044名前は開発中のものです。
04/08/07 00:22ID:xSvexrpgttp://www.graco.c.u-tokyo.ac.jp/kawai-kaneko-lab.html
0045名前は開発中のものです。
04/08/07 00:35ID:XI18DeZP0046名前は開発中のものです。
04/08/07 10:54ID:t8/IjFAcバイナリじゃないんだ。。。
readme.txtによるとBorland C++ Compilerでビルドせよとのこと。
Borland C++ Compilerは以下から無償で入手できるよ
http://www.borland.co.jp/cppbuilder/freecompiler/bcc55steps.html
メール登録(無料)が必要らしいね。
さすがにユーザー登録的な手続きまでするのは面倒くさいから
気が向いたら自分でチャレンジしてみて。
コンパイル自体は楽勝で誰だって出来るから
0047名前は開発中のものです。
04/08/09 07:53ID:LuKJ2ExA他のパズルの自動プログラムもOK?
0048名前は開発中のものです。
04/08/09 14:22ID:Bm7y7lhRいいんじゃないか?
0049名前は開発中のものです。
04/08/09 18:45ID:BKqxHMzO0050進可 ◆Sinka1my5k
04/08/10 00:00ID:50wtaTHUで、ナンバーリンクとは何かだが、ぐぐれば判るとおりマス目に書かれた同じ数字を
線で結んで全部繋ぐ紙面パズル。だが、これが別解を見つけるのが異様に困難な
パズルだったりする。複数解があるのは紙面パズルとして致命傷。
ショートカットでつなげられる答えがあるなどもってのほかだったりする。
自動で解くプログラムはいくつかあるようだけど、線が通らないマス目がある別解は
見つけられない。なので自分が挑戦してみようかと、こういう経緯。
0051進可 ◆Sinka1my5k
04/08/10 00:08ID:50wtaTHUここに線が引かれるはずだから、あーしてこーして・・・なんて線を延ばすやりかたがほぼ全部。
でも、このやりかたって、ショートカット解はみつけられなかったりするんだよな。
なんたって角地に線が通ることをまず確定させてるし。
で、自分が考え出したパターンはこれとは違い、線ではなくて壁を見るやりかた。
線を引かない部分を壁として、その壁の有無を総あたりでチェックする方法。
具体的なやりかたは次回に。
0052進可 ◆Sinka1my5k
04/08/10 11:21ID:x1eX9+9eスレ乗っ取りになりそうなので、どこか別の糞スレに移って
そこで解説したほうが良さそう。
0053名前は開発中のものです。
04/08/10 13:28ID:xunPxqDSいや、このスレもうほとんど止まってたし・・・このまま進めて欲しいな
0054進可 ◆Sinka1my5k
04/08/10 20:33ID:P6c4IZR0そうか、ならば・・・
0055進可 ◆Sinka1my5k
04/08/10 20:34ID:P6c4IZR0ル! { `ヽ, ∧
N { l ` ,、 i _|\/ ∨ ∨
ゝヽ _,,ィjjハ、 | \
`ニr‐tミ-rr‐tュ<≧rヘ > ここはしばらくMNR(もっとナンバーリンクの会)が
{___,リ ヽ二´ノ }ソ ∠ 乗っ取らせてもらうことにする!!
'、 `,-_-ュ u /| ∠
ヽ`┴ ' //l\ |/\∧ /
--─‐ァ'| `ニ--‐'´ / |`ー ..__ `´
く__レ1;';';';>、 / __ | ,=、 ___
「 ∧ 7;';';'| ヽ/ _,|‐、|」 |L..! {L..l ))
| |::.V;';';';'| /.:.|トl`´.! l _,,,l | _,,| , -,
! |:.:.:l;;';';';'|/.:.:.:||=|=; | | | | .l / 〃 ))
l |:.:.:.:l;';';'/.:.:.:.:| ! ヽ \!‐=:l/ `:lj 7
| |:.:.:.:.l;'/.:.:.:.:.:.! ヽ:::\:: ::::| ::l /
0056進可 ◆Sinka1my5k
04/08/10 20:35ID:P6c4IZR0> な なんだってー!! <
 ̄^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^ ̄
_,,.-‐-..,,_ _,,..--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>、
!、\ \. , ̄ γ/| ̄ 〃 \二-‐' //`
0057進可 ◆Sinka1my5k
04/08/10 20:36ID:P6c4IZR0/ `''.v'ν
i' / ̄""''--i 7
!ヘ /‐- 、u. |' ちょ、ちょっと待ってくれよキバヤシ、
|'' !゙ i.oニ'ー'〈ュニ! ナンバー(NUMBER)リンク(LINK)だったら
,`| u ..ゝ! 頭文字はMNLに・・・
<:::::\ (二> /
\::::\ '' /
\ \. , ̄
_
0058進可 ◆Sinka1my5k
04/08/10 20:38ID:P6c4IZR0|丶 \  ̄ ̄~Y〜 、
| \ __ / \
|ゝ、ヽ ─ / ヽ |
│ ヾ ゝ_ \ |
│ ヽ_ _ / /| |\ \|
\ヽ _ // / | \ |
ヽ\二_二// ∠二二二| ヘ| ナワヤ!勘違いをするな!
| | | ヽゝソゝ|TT|<ゝソ フ |/b} 日本放送協会(NHK)的な
ヾ| ヽ___ ノ/|| .ミ__ ノ | ノ 略語だから何の問題もない!
| 凵@ /フ
| u .F二二ヽ /|/
\. |/⌒⌒| イヽ
/. \ ==′/ |.| |
 ̄|| ヽ__/ / / ̄
\ヽ_____ノ ノ
0059進可 ◆Sinka1my5k
04/08/10 20:38ID:P6c4IZR0/ `''.v'ν
i' / ̄""''--i 7
!ヘ /‐- 、u. |'
|'' !゙ i.oニ'ー'〈ュニ! ・・・・・・・・・
,`| u ..ゝ!
<:::::\ (二> /
\::::\ '' /
\ \. , ̄
_
0060進可 ◆Sinka1my5k
04/08/10 21:24ID:P6c4IZR00061進可 ◆Sinka1my5k
04/08/10 22:11ID:P6c4IZR0ttp://www.nikoli.co.jp/puzzles/4/
で、このパズルだけど解き方の基本としてえいやっと線を引くってのがメインだったりする。
理詰めで少しづつ解いていくんじゃなくて、直感が大半な珍しいパズルでして・・・
で、作る方も同じく直感で作るわけだけど、困ったことに別解チェックがとても大変。
なんたって理詰めで解いていくパズルでないだけに、意外なところから線が引けたり
マス目が全部埋まらないショートカット解があったりと、難儀だったりするんだな。
0062進可 ◆Sinka1my5k
04/08/10 22:30ID:P6c4IZR0ソフトの存在はベクターに一つだけって状況で、しかもそれはショートカットの別解を
チェックできなかったりする。他のページの日記には、これの解答ソフトは
要望はあるけどモノが無い、と書かれている存在だそうで。
だったら俺が作ってやろうと思い立ったわけで・・・っていうか、実は理論なら
とうの昔にできていて、しかもその内容がとあるトコに掲載されたこともあったりして。
かなり昔のことなんだけどね。資料はまだ残っていたから作成はできるはず。
ただ、今回はこれを別解を確認できるように拡張していくという課題も追加。
0063進可 ◆Sinka1my5k
04/08/10 22:39ID:P6c4IZR0線を通過しない壁のほうに重みを置いてみる解き方です。
例えば上のニコリのページの問題。一番上の左端のマス目を通る線は
必ず右と下を通過するはずです。普通ならこの角の理論を適用して線を延ばしていくのですが
自分の考えはここからが違う。線を引く部分でなく、線を引かない上と左の壁に注目しました。
判りやすく下の答えを見てみましょう。線を引かない境界の点線に壁を引っ張ると
二つの法則を導きだされます。
「線を引くマスは必ず2方向が壁になる」
「数字の書いてあるマスは必ず3方向が壁になる」
この壁の数を利用して解いていこうというのが、自分の理論です。
0064進可 ◆Sinka1my5k
04/08/10 22:50ID:P6c4IZR0線を引くマスで上と左の壁数が
0なら、右と下は必ず壁になる。
1なら、右か下、どちらかが壁。
2なら、右と下は必ず壁が無い。
数字のマスで上の左の壁数が
0はありえないので、それ以前の壁がおかしい
1なら、右と下両方が壁になる。
2なら、右か下、どちらかが壁。
どちらかが壁の場合、仮に右を壁にして下を無しにしておいて次のマスへ進み
ありえない状況になったら戻って下だけ壁に変更して調べなおし、というやりかたです。
それでも駄目ならさらに前に戻って壁を変更します。
これを左上のスタート地点から右へと進めていって、右端についたら改行して
2段目の左端から、と進めていきます。ようするにしらみつぶしなんですね。
0065進可 ◆Sinka1my5k
04/08/10 23:06ID:P6c4IZR0線を伸ばしてどっちへ行くのか調べるとなると、それこそ上下左右好きな方向に
進められるので、相手の数字につくまで途方も無いパターンがあります。
が、この方法で調べていくなら少ないパターンで進めていける上に
壁に矛盾が無くなったら、最後に同じ数字同士が連結しているかを
チェックするだけですみます。
とりあえずこの上と左を見るやり方を、ガンマ方式と名づけます。命名理由は変換したらわかるはず。
実際には、これに加えてありえない壁の形になったらNGにするようプログラムした結果
11×11の面を即断で解けるようになりました。はい、実はもうプログラムはできてます。
今日一日でなんとか完成しました。ただ、盤面入力はテキストファイルだし、結果出力は
イメージに文字出力のみだしで、見た目がかなり汚いので発表はまだです。
っていうか、じっくり解説しながら作ろうと思ってたのに、一日でできるとは自分でもおもわなんだ。
というわけで今日はこれにて。
0066進可 ◆Sinka1my5k
04/08/11 13:00ID:0BPyFEfSそういえば、まだショートカットの探索方法書いてなかったな。
基本的には同じだけど、ショートカットができるってことは何も通らないマス目があるってこと。
これを便宜的に「壁マス」と呼ぶことにして話を進めます。
で、そこの部分の壁をどうするかだけど、線マスと壁マスの間は必ず壁があるが
壁と壁同士はあっても無くてもいいことになってややこしい。なので、壁マスは四方を必ず
壁に囲まれていると定義しておく。その考えで上の探索に追加。
線を引くマスで上と左の壁数が
0なら、右と下は必ず壁になる。
1なら、右か下、どちらかが壁。
*2なら、右と下は必ず壁が無いか、壁マスとして両方とも壁。
*の部分の探索を追加するだけ。ただ、これをやると探索数が一気に増えます。
7*7のショートカット解のみの面でテスト
ショートカット探索無し:解答0。79回探索。
ショートカット探索有り:解答430。3114906探索。
7*7ショートカット解なしの面でテスト
短絡無し:解答1。196回探索。
短絡有り:解答0。2992135回探索。
11*11の面でテストしましたが、短絡ありだと30分かけても戻ってきませんでした。
これでは実用にならないのでもうちょっと考えて見ます。
0067結果のテキスト出力
04/08/11 18:53ID:k24CCh2Y│┏┿━┿━┥1│
├╂┼─┼─┼─┤
│┃│2┝━┥2│
├┸┼─┼─┼─┤
│1│3┝━┥3│
└─┴─┴─┴─┘
こんなのどう?
0068進可 ◆Sinka1my5k
04/08/11 23:01ID:HfZVR1XVそんなふうにやりたいですなー。
ところで、最後に同じ数字を結んでいるかをチェックするのを
壁作成途中でもチェックするようにした結果
7*7ショートカット解なしの面でテスト
短絡無し:解答1。196→181回探索。
短絡有り:解答1。2992135→435102回探索。
と短くなりました。
(上の短絡有り:解答0。は解答1の間違いです。)
このおかげで15*15の面を短絡無しで
100秒かかっていたのが1秒かからなくなりました。
でも短絡ありだと10*10の面で帰ってこなくなるので、まだまだなにか
画期的なアイデアが必要です。
0069進可 ◆Sinka1my5k
04/08/12 13:12ID:FoaiKiVA途中チェック=現在のマスが数字で上か左が開いていたらリンク先を調べる
改行チェック=マスが一段埋まるたびにマス確定した上段数字マスの到達先を全部チェック。
7*7での回数
ショートカットチェック あり なし
最終チェックのみ 181 435102
+途中もチェック 179 303781
+改行もチェック 167 228814
数は減らせたけど、指数的に減ってないのでダメです。
10*10でショートカットありだと、探索が遅くなるばかりで解ける気配がぜんぜんありません。
ちなみに回数とは、最初のマスの壁の有無を確定して1回、次のマスの壁を確定して2回
という風に数えてます。それを考えると3ケタですんでるのは驚異的なんだけどね。
でもショートカット探索ありだと、ぜんぜん太刀打ちできないんだよな。
0070進可 ◆Sinka1my5k
04/08/12 13:18ID:FoaiKiVAhttp://hobby5.2ch.net/puzzle/
とりあえず7*7までならチェックできたし
これ以上の改良は、なんかとてつもなく長くなりそうだから
一旦ここで打ち切って、移動した方がよさげ。
倉庫番探索もそのうち考えます。
0071名前は開発中のものです。
04/08/12 17:51ID:6v5uYIwl0072進可 ◆Sinka1my5k
04/08/12 22:00ID:tDHsu3jMところで倉庫番で考えてるんだけど、荷物の位置を不確定にできないかなというアイデア。
例えば4×4の空間に荷物一個と人がいるとして
中央四つのどこかに荷物がある可能性がある場合はその場所をBとして
■■■■■■
■ ■
■ B .B ■
■ B .B ■
■ ■
■■■■■■
こんな感じにどれかに存在する可能性がある
0073進可 ◆Sinka1my5k
04/08/12 22:01ID:tDHsu3jM■■■■■■
■ B .B ■
■ ■
■ ■
■ ■
■■■■■■
こんな風に不確定の位置が変わる。
まだ大雑把な考えだから、これからどう発展させるかはわかってませんが
こんなアイデアもあるよということで晒しておきます。
0074進可 ◆Sinka1my5k
04/09/17 20:11:24ID:zbFgFr5Nナンバーリンクソルバーが形になったよ。
15*15でも1時間以内で解けます。
ttp://www.interq.or.jp/moonstone/person/numlink/index.html
0075進可 ◆Sinka1my5k
04/11/15 16:42:23ID:KRK43JVGttp://gamdev.org/up/img/1872.lzh
とりあえずは2ch上でやりとりできるようなシステムを作った
ボタンでマップチップのテキストを置く
テキストのセーブ&ロード
ステップの戻しと前進
プレイ中の面をテキストへコピー
プレイしたステップをテキストへコピー
書き出したステップをプレイ開始時に読み込み
■■■■■■■×
■×××××■■
■×田回回回×■
■×回××回足■
■×回××回×■
■×回回回◎×■
■×××××■■
■■■■■■■×
ddldllURdllluuuuurrrDDDuuullld
dRRDrUllluurD
こういう感じで面と解答ステップのやりとりが2ch上で可能に。
肝心な作り方と解き方は全然だけどな。
0076名前は開発中のものです。
04/11/15 18:00:20ID:ci0UTB+u0077名前は開発中のものです。
04/12/04 01:52:51ID:jMAxBzXc0078進可 ◆Sinka1my5k
2005/04/09(土) 20:30:09ID:FzAyxfw2解けるようなプログラムを作らないとダメなのではないだろうか?
もっと考えて、15パズルを解けるようなプログラムを作らないと
ダメなのではないだろうか?
0079名前は開発中のものです。
2005/04/09(土) 23:52:01ID:f0QdQ2zj0080名前は開発中のものです。
2005/04/09(土) 23:53:30ID:f0QdQ2zjttp://www.ic-net.or.jp/home/takaken/so/15pz/index.html
0081名前は開発中のものです。
2006/05/15(月) 15:01:25ID:iqNZ3zgN0082進可 ◆Sinka1my5k
2006/06/23(金) 01:17:15ID:rNoNlc0Cttp://news19.2ch.net/test/read.cgi/newsplus/1150945519/l50
北朝鮮がゲーム作ったと思ったら、ルールも面も日本のパクリだったよw
0083名前は開発中のものです。
2006/08/11(金) 14:34:16ID:XHr3GWC70084名前は開発中のものです。
2006/08/11(金) 15:36:04ID:+c/odd+z0085名前は開発中のものです。
2006/08/12(土) 06:15:40ID:2SZsaOQK詳しく
0086名前は開発中のものです。
2007/01/07(日) 01:43:57ID:3utMDeTC最近、倉庫番のはまりだまして活用させて頂いております。
大変ありがとうございます。
0087名前は開発中のものです。
2007/07/21(土) 13:46:08ID:ZgxFvFBuかれこれ数年解けません orz
0088名前は開発中のものです。
2007/07/26(木) 04:13:55ID:MyeVtBFN荷物ごとに可動範囲を設定
目標には置ける可能性のある荷物のインデックスでも持たせる
ある程度絞り込めそうだけど、どうだろ
書いてると作りたくなるw
0089名前は開発中のものです。
2008/08/12(火) 14:02:26ID:X38yz9YKこの人のがどうなったのか気になる
なんかすごい自信満々なんだがソルバがおいてない…
0090名前は開発中のものです。
2008/11/15(土) 17:39:16ID:50CPL4Xv0091名前は開発中のものです。
2010/08/27(金) 23:10:51ID:ys+uGMbs人の厳密な位置を無視して、
荷物の配置だけを状態とみた木で探索したら
木が小さくなったりしないかな。
荷物の配置が決まると「荷物を押さずに動ける範囲」という
部分空間がいくつかできる。
人の位置は、今どの部分空間にいるか?という情報だけに縮退させる。
最短解は出ないけど、荷物の移動回数の最短解と言う形でとりあえずの解は
効率的に出せそう。
このアプローチで組むのってすでにいっぱいやられてたりする?
0092名前は開発中のものです。
2010/08/28(土) 12:58:32ID:nNbfcnRUしかし、情報は「どの部分空間にいるか?」で持つよりも
「荷物をどっち方向に動かせるか?」で持った方が良くないか?
009391
2010/08/28(土) 19:05:52ID:9E55durhなるほど。
今のところ、部分空間の内で一番数字の若い位置を
その部分空間を特定する情報にして組み始めてた。
確かに >>92 まで出してからデータベース化した方が
最探索時に早いね。
データ量と一致判定の速さもそんなに変わらないし。
そっちに変えてみよう。
009491
2010/09/01(水) 00:05:03ID:dLsy+EFF7段目くらいで8000×3500程度の探索済み重複チェックが終わらない。
盤面みると全然進んでない。
まあハッシュすら使ってないし仕方ないか
0095名前は開発中のものです。
2010/09/26(日) 01:56:41ID:EUCOONMp意外でもないわ。
0096名前は開発中のものです。
2010/09/26(日) 02:11:47ID:maTkzKHY0097名前は開発中のものです。
2010/10/17(日) 01:11:39ID:js/8V7SCその後、ゴール部屋の中での最後の荷物整理部分をなくして、
ゴール部屋の玄関までくれば荷物が消えるようにしてxsokoban の screen.1 はクリアした。
ヒューリスティック過ぎて好きじゃないが。
ゴール部屋の自動検出も一応考えたが、実装がちょっと大変そう…
XSokoban は結構この手の無駄に広いゴール部屋があるのよね。
ソルバ対策?
0098名前は開発中のものです。
2012/01/06(金) 23:52:10.91ID:mG+XCcAE地球にやさしいアルゴリズム
第8回 倉庫番を解くアルゴリズム
http://itpro.nikkeibp.co.jp/article/COLUMN/20070411/268003/

作れた?
0100名前は開発中のものです。
2013/09/18(水) 17:05:38.21ID:c4Tb9xjV0101名前は開発中のものです。
2013/12/30(月) 02:53:18.83ID:O2CS7qV10102名前は開発中のものです。
2014/04/25(金) 21:48:55.16ID:a8hkhpLZttp://www13.plala.or.jp/amagame/hexmap/hexsouko.png
こちらで公開しています。
ttp://www13.plala.or.jp/amagame/hexmap/index.html
0103名前は開発中のものです。
2014/05/02(金) 09:06:46.51ID:lwQn6wmB微妙にスレ違いだったので転送しときました。
【ロードランナー】思考型パズルゲームを語れ【倉庫番】
http://ikura.2ch.net/test/read.cgi/puzzle/1092847576/
ていうかゲーム製作板はパズル総合スレなくてこのスレくらいしかないのね…
0104名前は開発中のものです。
2014/05/02(金) 09:09:09.05ID:lwQn6wmB0105名前は開発中のものです。
2014/05/04(日) 01:11:40.10ID:y/ah+wM+スライドパズル好きから見て、なんかムズムズする。
■ このスレッドは過去ログ倉庫に格納されています