04/08/01 03:05 Q2G2XU2Z.net
プログラムによる自動生成全52面
URLリンク(www.ne.jp)
42:名前は開発中のものです。
04/08/01 11:46 YiQa0gMz.net
>>41
そのプログラムそのものはどこかにないの?
43:名前は開発中のものです。
04/08/01 14:16 VNo3uGvt.net
移転前
URLリンク(web.archive.org)
自動生成のプログラムそのものはないみたい
44:名前は開発中のものです。
04/08/07 00:22 xSvexrpg.net
この小田原研究が見たいが、見つからない。
URLリンク(www.graco.c.u-tokyo.ac.jp)
45:名前は開発中のものです。
04/08/07 00:35 XI18DeZP.net
>>35をコンパイルしたの頂けないでしょうか
46:名前は開発中のものです。
04/08/07 10:54 t8/IjFAc.net
>>45
バイナリじゃないんだ。。。
readme.txtによるとBorland C++ Compilerでビルドせよとのこと。
Borland C++ Compilerは以下から無償で入手できるよ
URLリンク(www.borland.co.jp)
メール登録(無料)が必要らしいね。
さすがにユーザー登録的な手続きまでするのは面倒くさいから
気が向いたら自分でチャレンジしてみて。
コンパイル自体は楽勝で誰だって出来るから
47:名前は開発中のものです。
04/08/09 07:53 LuKJ2ExA.net
いきなりネタ無くなってる感がするんだが
他のパズルの自動プログラムもOK?
48:名前は開発中のものです。
04/08/09 14:22 Bm7y7lhR.net
基本は変わらないし、参考になるから
いいんじゃないか?
49:名前は開発中のものです。
04/08/09 18:45 BKqxHMzO.net
それじゃ、昔やったナンバーリンクの自動解答に挑戦してみる。
50:進可 ◆Sinka1my5k
04/08/10 00:00 50wtaTHU.net
49だが、ハンドルさらし。とりあえず今日は面を読み込んで表示するところまでできた。
で、ナンバーリンクとは何かだが、ぐぐれば判るとおりマス目に書かれた同じ数字を
線で結んで全部繋ぐ紙面パズル。だが、これが別解を見つけるのが異様に困難な
パズルだったりする。複数解があるのは紙面パズルとして致命傷。
ショートカットでつなげられる答えがあるなどもってのほかだったりする。
自動で解くプログラムはいくつかあるようだけど、線が通らないマス目がある別解は
見つけられない。なので自分が挑戦してみようかと、こういう経緯。
51:進可 ◆Sinka1my5k
04/08/10 00:08 50wtaTHU.net
んで実際にどうみつけるかだけど、いろいろ探ってみたところ
ここに線が引かれるはずだから、あーしてこーして・・・なんて線を延ばすやりかたがほぼ全部。
でも、このやりかたって、ショートカット解はみつけられなかったりするんだよな。
なんたって角地に線が通ることをまず確定させてるし。
で、自分が考え出したパターンはこれとは違い、線ではなくて壁を見るやりかた。
線を引かない部分を壁として、その壁の有無を総あたりでチェックする方法。
具体的なやりかたは次回に。
52:進可 ◆Sinka1my5k
04/08/10 11:21 x1eX9+9e.net
すまんけど、解説するとかなり長々した文になりそうだ。
スレ乗っ取りになりそうなので、どこか別の糞スレに移って
そこで解説したほうが良さそう。
53:名前は開発中のものです。
04/08/10 13:28 xunPxqDS.net
>>52
いや、このスレもうほとんど止まってたし・・・このまま進めて欲しいな
54:進可 ◆Sinka1my5k
04/08/10 20:33 P6c4IZR0.net
>53
そうか、ならば・・・
55:進可 ◆Sinka1my5k
04/08/10 20:34 P6c4IZR0.net
,ィィr-- ..__、j
ル! { `ヽ, ∧
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 /
56:進可 ◆Sinka1my5k
04/08/10 20:35 P6c4IZR0.net
_人人人人人人人人人人人人人人_
> な なんだってー!! <
 ̄^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>、
!、\ \. , ̄ γ/| ̄ 〃 \二-‐' //`
57:進可 ◆Sinka1my5k
04/08/10 20:36 P6c4IZR0.net
_,,.-‐-..,,_
/ `''.v'ν
i' / ̄""''--i 7
!ヘ /‐- 、u. |' ちょ、ちょっと待ってくれよキバヤシ、
|'' !゙ i.oニ'ー'〈ュニ! ナンバー(NUMBER)リンク(LINK)だったら
,`| u ..ゝ! 頭文字はMNLに・・・
<:::::\ (二> /
\::::\ '' /
\ \. , ̄
_
58:進可 ◆Sinka1my5k
04/08/10 20:38 P6c4IZR0.net
|丶 \  ̄ ̄~Y~ 、
| \ __ / \
|ゝ、ヽ ─ / ヽ |
│ ヾ ゝ_ \ |
│ ヽ_ _ / /| |\ \|
\ヽ _ // / | \ |
ヽ\二_二// ∠二二二| ヘ| ナワヤ!勘違いをするな!
| | | ヽゝソゝ|TT|<ゝソ フ |/b} 日本放送協会(NHK)的な
ヾ| ヽ___ ノ/|| .ミ__ ノ | ノ 略語だから何の問題もない!
| ⊿ /フ
| u .F二二ヽ /|/
\. |/⌒⌒| イヽ
/. \ ==′/ |.| |
 ̄|| ヽ__/ / / ̄
\ヽ_____ノ ノ
59:進可 ◆Sinka1my5k
04/08/10 20:38 P6c4IZR0.net
_,,.-‐-..,,_
/ `''.v'ν
i' / ̄""''--i 7
!ヘ /‐- 、u. |'
|'' !゙ i.oニ'ー'〈ュニ! ・・・・・・・・・
,`| u ..ゝ!
<:::::\ (二> /
\::::\ '' /
\ \. , ̄
_
60:進可 ◆Sinka1my5k
04/08/10 21:24 P6c4IZR0.net
すまん、連続投稿に引っかったから普通に進めることにする。←バカ者
61:進可 ◆Sinka1my5k
04/08/10 22:11 P6c4IZR0.net
とりあえずナンバーリンクそのものの説明は以下のURLで
URLリンク(www.nikoli.co.jp)
で、このパズルだけど解き方の基本としてえいやっと線を引くってのがメインだったりする。
理詰めで少しづつ解いていくんじゃなくて、直感が大半な珍しいパズルでして・・・
で、作る方も同じく直感で作るわけだけど、困ったことに別解チェックがとても大変。
なんたって理詰めで解いていくパズルでないだけに、意外なところから線が引けたり
マス目が全部埋まらないショートカット解があったりと、難儀だったりするんだな。
62:進可 ◆Sinka1my5k
04/08/10 22:30 P6c4IZR0.net
で、これを解く為のソルバープログラムなんだけど、検索してみたところ
ソフトの存在はベクターに一つだけって状況で、しかもそれはショートカットの別解を
チェックできなかったりする。他のページの日記には、これの解答ソフトは
要望はあるけどモノが無い、と書かれている存在だそうで。
だったら俺が作ってやろうと思い立ったわけで・・・っていうか、実は理論なら
とうの昔にできていて、しかもその内容がとあるトコに掲載されたこともあったりして。
かなり昔のことなんだけどね。資料はまだ残っていたから作成はできるはず。
ただ、今回はこれを別解を確認できるように拡張していくという課題も追加。
63:進可 ◆Sinka1my5k
04/08/10 22:39 P6c4IZR0.net
さてさて、それで具体的なやり方だけど、上に書いてあるとおりマス目に線を引くんじゃなくて
線を通過しない壁のほうに重みを置いてみる解き方です。
例えば上のニコリのページの問題。一番上の左端のマス目を通る線は
必ず右と下を通過するはずです。普通ならこの角の理論を適用して線を延ばしていくのですが
自分の考えはここからが違う。線を引く部分でなく、線を引かない上と左の壁に注目しました。
判りやすく下の答えを見てみましょう。線を引かない境界の点線に壁を引っ張ると
二つの法則を導きだされます。
「線を引くマスは必ず2方向が壁になる」
「数字の書いてあるマスは必ず3方向が壁になる」
この壁の数を利用して解いていこうというのが、自分の理論です。
64:進可 ◆Sinka1my5k
04/08/10 22:50 P6c4IZR0.net
具体的には、あるマスAにおいて上と左の壁数を確認します。
線を引くマスで上と左の壁数が
0なら、右と下は必ず壁になる。
1なら、右か下、どちらかが壁。
2なら、右と下は必ず壁が無い。
数字のマスで上の左の壁数が
0はありえないので、それ以前の壁がおかしい
1なら、右と下両方が壁になる。
2なら、右か下、どちらかが壁。
どちらかが壁の場合、仮に右を壁にして下を無しにしておいて次のマスへ進み
ありえない状況になったら戻って下だけ壁に変更して調べなおし、というやりかたです。
それでも駄目ならさらに前に戻って壁を変更します。
これを左上のスタート地点から右へと進めていって、右端についたら改行して
2段目の左端から、と進めていきます。ようするにしらみつぶしなんですね。
65:進可 ◆Sinka1my5k
04/08/10 23:06 P6c4IZR0.net
でもこのしらみつぶし、結構有効な方法だったりします。
線を伸ばしてどっちへ行くのか調べるとなると、それこそ上下左右好きな方向に
進められるので、相手の数字につくまで途方も無いパターンがあります。
が、この方法で調べていくなら少ないパターンで進めていける上に
壁に矛盾が無くなったら、最後に同じ数字同士が連結しているかを
チェックするだけですみます。
とりあえずこの上と左を見るやり方を、ガンマ方式と名づけます。命名理由は変換したらわかるはず。
実際には、これに加えてありえない壁の形になったらNGにするようプログラムした結果
11×11の面を即断で解けるようになりました。はい、実はもうプログラムはできてます。
今日一日でなんとか完成しました。ただ、盤面入力はテキストファイルだし、結果出力は
イメージに文字出力のみだしで、見た目がかなり汚いので発表はまだです。
っていうか、じっくり解説しながら作ろうと思ってたのに、一日でできるとは自分でもおもわなんだ。
というわけで今日はこれにて。
66:進可 ◆Sinka1my5k
04/08/11 13:00 0BPyFEfS.net
続き~
そういえば、まだショートカットの探索方法書いてなかったな。
基本的には同じだけど、ショートカットができるってことは何も通らないマス目があるってこと。
これを便宜的に「壁マス」と呼ぶことにして話を進めます。
で、そこの部分の壁をどうするかだけど、線マスと壁マスの間は必ず壁があるが
壁と壁同士はあっても無くてもいいことになってややこしい。なので、壁マスは四方を必ず
壁に囲まれていると定義しておく。その考えで上の探索に追加。
線を引くマスで上と左の壁数が
0なら、右と下は必ず壁になる。
1なら、右か下、どちらかが壁。
*2なら、右と下は必ず壁が無いか、壁マスとして両方とも壁。
*の部分の探索を追加するだけ。ただ、これをやると探索数が一気に増えます。
7*7のショートカット解のみの面でテスト
ショートカット探索無し:解答0。79回探索。
ショートカット探索有り:解答430。3114906探索。
7*7ショートカット解なしの面でテスト
短絡無し:解答1。196回探索。
短絡有り:解答0。2992135回探索。
11*11の面でテストしましたが、短絡ありだと30分かけても戻ってきませんでした。
これでは実用にならないのでもうちょっと考えて見ます。
67:結果のテキスト出力
04/08/11 18:53 k24CCh2Y.net
┌─┬─┬─┬─┐
│┏┿━┿━┥1│
├╂┼─┼─┼─┤
│┃│2┝━┥2│
├┸┼─┼─┼─┤
│1│3┝━┥3│
└─┴─┴─┴─┘
こんなのどう?
68:進可 ◆Sinka1my5k
04/08/11 23:01 HfZVR1XV.net
>67
そんなふうにやりたいですなー。
ところで、最後に同じ数字を結んでいるかをチェックするのを
壁作成途中でもチェックするようにした結果
7*7ショートカット解なしの面でテスト
短絡無し:解答1。196→181回探索。
短絡有り:解答1。2992135→435102回探索。
と短くなりました。
(上の短絡有り:解答0。は解答1の間違いです。)
このおかげで15*15の面を短絡無しで
100秒かかっていたのが1秒かからなくなりました。
でも短絡ありだと10*10の面で帰ってこなくなるので、まだまだなにか
画期的なアイデアが必要です。
69:進可 ◆Sinka1my5k
04/08/12 13:12 FoaiKiVA.net
最終チェック=マス目に壁が全部埋まった時点で全部の数字の到達先を調べる
途中チェック=現在のマスが数字で上か左が開いていたらリンク先を調べる
改行チェック=マスが一段埋まるたびにマス確定した上段数字マスの到達先を全部チェック。
7*7での回数
ショートカットチェック あり なし
最終チェックのみ 181 435102
+途中もチェック 179 303781
+改行もチェック 167 228814
数は減らせたけど、指数的に減ってないのでダメです。
10*10でショートカットありだと、探索が遅くなるばかりで解ける気配がぜんぜんありません。
ちなみに回数とは、最初のマスの壁の有無を確定して1回、次のマスの壁を確定して2回
という風に数えてます。それを考えると3ケタですんでるのは驚異的なんだけどね。
でもショートカット探索ありだと、ぜんぜん太刀打ちできないんだよな。
70:進可 ◆Sinka1my5k
04/08/12 13:18 FoaiKiVA.net
ところでパズル板ができたね。
URLリンク(hobby5.2ch.net)
とりあえず7*7までならチェックできたし
これ以上の改良は、なんかとてつもなく長くなりそうだから
一旦ここで打ち切って、移動した方がよさげ。
倉庫番探索もそのうち考えます。
71:名前は開発中のものです。
04/08/12 17:51 6v5uYIwl.net
あ゛~、見てるだけで終わってしまった。
72:進可 ◆Sinka1my5k
04/08/12 22:00 tDHsu3jM.net
なんか新しいパターンがあったら伝えますですのことよ。
ところで倉庫番で考えてるんだけど、荷物の位置を不確定にできないかなというアイデア。
例えば4×4の空間に荷物一個と人がいるとして
中央四つのどこかに荷物がある可能性がある場合はその場所をBとして
■■■■■■
■ ■
■ B .B ■
■ B .B ■
■ ■
■■■■■■
こんな感じにどれかに存在する可能性がある
73:進可 ◆Sinka1my5k
04/08/12 22:01 tDHsu3jM.net
で、それを上に押し付けた場合は
■■■■■■
■ B .B ■
■ ■
■ ■
■ ■
■■■■■■
こんな風に不確定の位置が変わる。
まだ大雑把な考えだから、これからどう発展させるかはわかってませんが
こんなアイデアもあるよということで晒しておきます。
74:進可 ◆Sinka1my5k
04/09/17 20:11:24 zbFgFr5N.net
こっちにも報告
ナンバーリンクソルバーが形になったよ。
15*15でも1時間以内で解けます。
URLリンク(www.interq.or.jp)
75:進可 ◆Sinka1my5k
04/11/15 16:42:23 KRK43JVG.net
自主制作報告のほうにもアゲたけどこっちにも
URLリンク(gamdev.org)
とりあえずは2ch上でやりとりできるようなシステムを作った
ボタンでマップチップのテキストを置く
テキストのセーブ&ロード
ステップの戻しと前進
プレイ中の面をテキストへコピー
プレイしたステップをテキストへコピー
書き出したステップをプレイ開始時に読み込み
■■■■■■■×
■×××××■■
■×田回回回×■
■×回××回足■
■×回××回×■
■×回回回◎×■
■×××××■■
■■■■■■■×
ddldllURdllluuuuurrrDDDuuullld
dRRDrUllluurD
こういう感じで面と解答ステップのやりとりが2ch上で可能に。
肝心な作り方と解き方は全然だけどな。
76:名前は開発中のものです。
04/11/15 18:00:20 ci0UTB+u.net
このスレなにげに楽しみにしてるのでがんがれ
77:名前は開発中のものです。
04/12/04 01:52:51 jMAxBzXc.net
あー
78:進可 ◆Sinka1my5k
05/04/09 20:30:09 FzAyxfw2.net
ふと考えた。倉庫番を解くプログラムを作る前に、スライドパズルを
解けるようなプログラムを作らないとダメなのではないだろうか?
もっと考えて、15パズルを解けるようなプログラムを作らないと
ダメなのではないだろうか?
79:名前は開発中のものです。
05/04/09 23:52:01 f0QdQ2zj.net
作れるんじゃね?
80:名前は開発中のものです。
05/04/09 23:53:30 f0QdQ2zj.net
つーか
URLリンク(www.ic-net.or.jp)
81:名前は開発中のものです。
06/05/15 15:01:25 iqNZ3zgN.net
82:進可 ◆Sinka1my5k
06/06/23 01:17:15 rNoNlc0C.net
【北朝鮮】「悪いやつらをなくそう」 国家公式サイトにオンラインゲーム登場 日本人と米国人の泥棒を退治
スレリンク(newsplus板)l50
北朝鮮がゲーム作ったと思ったら、ルールも面も日本のパクリだったよw
83:名前は開発中のものです。
06/08/11 14:34:16 XHr3GWC7.net
状態空間探索も知らずに頑張っていたのか・・・
84:名前は開発中のものです。
06/08/11 15:36:04 +c/odd+z.net
しかし倉庫番というのはなんでああも中途半端な所へ荷物を「片付ける」必要があるのだろう。
85:名前は開発中のものです。
06/08/12 06:15:40 2SZsaOQK.net
>状態空間探索
詳しく
86:名前は開発中のものです。
07/01/07 01:43:57 3utMDeTC.net
>>75
最近、倉庫番のはまりだまして活用させて頂いております。
大変ありがとうございます。
87:名前は開発中のものです。
07/07/21 13:46:08 ZgxFvFBu.net
携帯版 倉庫番Firststep の37面が
かれこれ数年解けません orz
88:名前は開発中のものです。
07/07/26 04:13:55 MyeVtBFN.net
絶対荷物を移動させない位置を塗り潰し
荷物ごとに可動範囲を設定
目標には置ける可能性のある荷物のインデックスでも持たせる
ある程度絞り込めそうだけど、どうだろ
書いてると作りたくなるw
89:名前は開発中のものです。
08/08/12 14:02:26 X38yz9YK.net
URLリンク(vintermann.paranoidkoala.org)
この人のがどうなったのか気になる
なんかすごい自信満々なんだがソルバがおいてない…
90:名前は開発中のものです。
08/11/15 17:39:16 50CPL4Xv.net
YASGenあるじゃん
91:名前は開発中のものです。
10/08/27 23:10:51 ys+uGMbs.net
人がうろうろさせると探索空間が発散するので、
人の厳密な位置を無視して、
荷物の配置だけを状態とみた木で探索したら
木が小さくなったりしないかな。
荷物の配置が決まると「荷物を押さずに動ける範囲」という
部分空間がいくつかできる。
人の位置は、今どの部分空間にいるか?という情報だけに縮退させる。
最短解は出ないけど、荷物の移動回数の最短解と言う形でとりあえずの解は
効率的に出せそう。
このアプローチで組むのってすでにいっぱいやられてたりする?
92:名前は開発中のものです。
10/08/28 12:58:32 nNbfcnRU.net
自分は聞いたことはないな。
しかし、情報は「どの部分空間にいるか?」で持つよりも
「荷物をどっち方向に動かせるか?」で持った方が良くないか?
93:91
10/08/28 19:05:52 9E55durh.net
>>92
なるほど。
今のところ、部分空間の内で一番数字の若い位置を
その部分空間を特定する情報にして組み始めてた。
確かに >>92 まで出してからデータベース化した方が
最探索時に早いね。
データ量と一致判定の速さもそんなに変わらないし。
そっちに変えてみよう。
94:91
10/09/01 00:05:03 dLsy+EFF.net
うーん。xsokoban の screen.1 すら解けないな(笑)
7段目くらいで8000×3500程度の探索済み重複チェックが終わらない。
盤面みると全然進んでない。
まあハッシュすら使ってないし仕方ないか
95:名前は開発中のものです。
10/09/26 01:56:41 EUCOONMp.net
意外に一般的なやり方のようでした。
意外でもないわ。
96:名前は開発中のものです。
10/09/26 02:11:47 maTkzKHY.net
そうなの?
97:名前は開発中のものです。
10/10/17 01:11:39 js/8V7SC.net
google 上位の pdf の初心者向けソルバ解説とかそれだった
その後、ゴール部屋の中での最後の荷物整理部分をなくして、
ゴール部屋の玄関までくれば荷物が消えるようにしてxsokoban の screen.1 はクリアした。
ヒューリスティック過ぎて好きじゃないが。
ゴール部屋の自動検出も一応考えたが、実装がちょっと大変そう…
XSokoban は結構この手の無駄に広いゴール部屋があるのよね。
ソルバ対策?
98:名前は開発中のものです。
12/01/06 23:52:10.91 mG+XCcAE.net
こんな記事がITproにあった
地球にやさしいアルゴリズム
第8回 倉庫番を解くアルゴリズム
URLリンク(itpro.nikkeibp.co.jp)
99:電脳プリオン 【東電 76.4 %】 【18.6m】
13/09/16 16:07:55.62 G554mz3j.net BE:121623034-PLT(12080)
sssp://img.2ch.net/ico/folder1_13.gif
作れた?
100:名前は開発中のものです。
13/09/18 17:05:38.21 c4Tb9xjV.net
疲れた
101:名前は開発中のものです。
13/12/30 02:53:18.83 O2CS7qV1.net
浮上
102:名前は開発中のものです。
14/04/25 21:48:55.16 a8hkhpLZ.net
へクスマップの倉庫番を作ってみました。
URLリンク(www13.plala.or.jp)
こちらで公開しています。
URLリンク(www13.plala.or.jp)
103:名前は開発中のものです。
14/05/02 09:06:46.51 lwQn6wmB.net
>>102
微妙にスレ違いだったので転送しときました。
【ロードランナー】思考型パズルゲームを語れ【倉庫番】
スレリンク(puzzle板)
ていうかゲーム製作板はパズル総合スレなくてこのスレくらいしかないのね…
104:名前は開発中のものです。
14/05/02 09:09:09.05 lwQn6wmB.net
ってことでぜひへクスタイプのソルバ作って難しい面量産しれw
105:名前は開発中のものです。
14/05/04 01:11:40.10 y/ah+wM+.net
ギザギザ無視して隣のマスに移動できるのが
スライドパズル好きから見て、なんかムズムズする。