04/08/10 22:11 P6c4IZR0
とりあえずナンバーリンクそのものの説明は以下のURLで
URLﾘﾝｸ(www.nikoli.co.jp)
で、このパズルだけど解き方の基本としてえいやっと線を引くってのがメインだったりする。
理詰めで少しづつ解いていくんじゃなくて、直感が大半な珍しいパズルでして・・・
で、作る方も同じく直感で作るわけだけど、困ったことに別解チェックがとても大変。
なんたって理詰めで解いていくパズルでないだけに、意外なところから線が引けたり
マス目が全部埋まらないショートカット解があったりと、難儀だったりするんだな。
62:進可 ◆Sinka1my5k
04/08/10 22:30 P6c4IZR0
で、これを解く為のソルバープログラムなんだけど、検索してみたところ
ソフトの存在はベクターに一つだけって状況で、しかもそれはショートカットの別解を
チェックできなかったりする。他のページの日記には、これの解答ソフトは
要望はあるけどモノが無い、と書かれている存在だそうで。
だったら俺が作ってやろうと思い立ったわけで・・・っていうか、実は理論なら
とうの昔にできていて、しかもその内容がとあるトコに掲載されたこともあったりして。
かなり昔のことなんだけどね。資料はまだ残っていたから作成はできるはず。
ただ、今回はこれを別解を確認できるように拡張していくという課題も追加。
63:進可 ◆Sinka1my5k
04/08/10 22:39 P6c4IZR0
さてさて、それで具体的なやり方だけど、上に書いてあるとおりマス目に線を引くんじゃなくて
線を通過しない壁のほうに重みを置いてみる解き方です。
例えば上のニコリのページの問題。一番上の左端のマス目を通る線は
必ず右と下を通過するはずです。普通ならこの角の理論を適用して線を延ばしていくのですが
自分の考えはここからが違う。線を引く部分でなく、線を引かない上と左の壁に注目しました。
判りやすく下の答えを見てみましょう。線を引かない境界の点線に壁を引っ張ると
二つの法則を導きだされます。
「線を引くマスは必ず２方向が壁になる」
「数字の書いてあるマスは必ず３方向が壁になる」
この壁の数を利用して解いていこうというのが、自分の理論です。
64:進可 ◆Sinka1my5k
04/08/10 22:50 P6c4IZR0
具体的には、あるマスAにおいて上と左の壁数を確認します。
線を引くマスで上と左の壁数が
０なら、右と下は必ず壁になる。
１なら、右か下、どちらかが壁。
２なら、右と下は必ず壁が無い。
数字のマスで上の左の壁数が
０はありえないので、それ以前の壁がおかしい
１なら、右と下両方が壁になる。
２なら、右か下、どちらかが壁。
どちらかが壁の場合、仮に右を壁にして下を無しにしておいて次のマスへ進み
ありえない状況になったら戻って下だけ壁に変更して調べなおし、というやりかたです。
それでも駄目ならさらに前に戻って壁を変更します。
これを左上のスタート地点から右へと進めていって、右端についたら改行して
２段目の左端から、と進めていきます。ようするにしらみつぶしなんですね。
65:進可 ◆Sinka1my5k
04/08/10 23:06 P6c4IZR0
でもこのしらみつぶし、結構有効な方法だったりします。
線を伸ばしてどっちへ行くのか調べるとなると、それこそ上下左右好きな方向に
進められるので、相手の数字につくまで途方も無いパターンがあります。
が、この方法で調べていくなら少ないパターンで進めていける上に
壁に矛盾が無くなったら、最後に同じ数字同士が連結しているかを
チェックするだけですみます。
とりあえずこの上と左を見るやり方を、ガンマ方式と名づけます。命名理由は変換したらわかるはず。
実際には、これに加えてありえない壁の形になったらNGにするようプログラムした結果
11×11の面を即断で解けるようになりました。はい、実はもうプログラムはできてます。
今日一日でなんとか完成しました。ただ、盤面入力はテキストファイルだし、結果出力は
イメージに文字出力のみだしで、見た目がかなり汚いので発表はまだです。
っていうか、じっくり解説しながら作ろうと思ってたのに、一日でできるとは自分でもおもわなんだ。
というわけで今日はこれにて。
66:進可 ◆Sinka1my5k
04/08/11 13:00 0BPyFEfS
続き～
そういえば、まだショートカットの探索方法書いてなかったな。
基本的には同じだけど、ショートカットができるってことは何も通らないマス目があるってこと。
これを便宜的に「壁マス」と呼ぶことにして話を進めます。
で、そこの部分の壁をどうするかだけど、線マスと壁マスの間は必ず壁があるが
壁と壁同士はあっても無くてもいいことになってややこしい。なので、壁マスは四方を必ず
壁に囲まれていると定義しておく。その考えで上の探索に追加。
線を引くマスで上と左の壁数が
０なら、右と下は必ず壁になる。
１なら、右か下、どちらかが壁。
＊２なら、右と下は必ず壁が無いか、壁マスとして両方とも壁。
＊の部分の探索を追加するだけ。ただ、これをやると探索数が一気に増えます。
７＊７のショートカット解のみの面でテスト
ショートカット探索無し：解答0。79回探索。
ショートカット探索有り：解答430。3114906探索。
7＊７ショートカット解なしの面でテスト
短絡無し：解答１。196回探索。
短絡有り：解答０。2992135回探索。
11＊11の面でテストしましたが、短絡ありだと３０分かけても戻ってきませんでした。
これでは実用にならないのでもうちょっと考えて見ます。
67:結果のテキスト出力
04/08/11 18:53 k24CCh2Y
┌─┬─┬─┬─┐
│┏┿━┿━┥１│
├╂┼─┼─┼─┤
│┃│２┝━┥２│
├┸┼─┼─┼─┤
│１│３┝━┥３│
└─┴─┴─┴─┘
こんなのどう？
68:進可 ◆Sinka1my5k
04/08/11 23:01 HfZVR1XV
>67
そんなふうにやりたいですなー。
ところで、最後に同じ数字を結んでいるかをチェックするのを
壁作成途中でもチェックするようにした結果
7＊７ショートカット解なしの面でテスト
短絡無し：解答１。196→181回探索。
短絡有り：解答１。2992135→435102回探索。
と短くなりました。
（上の短絡有り：解答０。は解答１の間違いです。）
このおかげで15＊15の面を短絡無しで
100秒かかっていたのが１秒かからなくなりました。
でも短絡ありだと10＊10の面で帰ってこなくなるので、まだまだなにか
画期的なアイデアが必要です。
69:進可 ◆Sinka1my5k
04/08/12 13:12 FoaiKiVA
最終ﾁｪｯｸ＝マス目に壁が全部埋まった時点で全部の数字の到達先を調べる
途中ﾁｪｯｸ＝現在のマスが数字で上か左が開いていたらリンク先を調べる
改行ﾁｪｯｸ＝マスが一段埋まるたびにマス確定した上段数字マスの到達先を全部ﾁｪｯｸ。
7*7での回数
ｼｮｰﾄｶｯﾄﾁｪｯｸ あり なし
最終ﾁｪｯｸのみ 181 435102
+途中もﾁｪｯｸ 179 303781
+改行もﾁｪｯｸ 167 228814
数は減らせたけど、指数的に減ってないのでダメです。
10*10でｼｮｰﾄｶｯﾄありだと、探索が遅くなるばかりで解ける気配がぜんぜんありません。
ちなみに回数とは、最初のマスの壁の有無を確定して１回、次のマスの壁を確定して2回
という風に数えてます。それを考えると３ケタですんでるのは驚異的なんだけどね。
でもｼｮｰﾄｶｯﾄ探索ありだと、ぜんぜん太刀打ちできないんだよな。
70:進可 ◆Sinka1my5k
04/08/12 13:18 FoaiKiVA
ところでパズル板ができたね。
URLﾘﾝｸ(hobby5.2ch.net)
とりあえず７＊７までならチェックできたし
これ以上の改良は、なんかとてつもなく長くなりそうだから
一旦ここで打ち切って、移動した方がよさげ。
倉庫番探索もそのうち考えます。
71:名前は開発中のものです。
04/08/12 17:51 6v5uYIwl
あ゛～、見てるだけで終わってしまった。
72:進可 ◆Sinka1my5k
04/08/12 22:00 tDHsu3jM
なんか新しいパターンがあったら伝えますですのことよ。
ところで倉庫番で考えてるんだけど、荷物の位置を不確定にできないかなというアイデア。
例えば４×４の空間に荷物一個と人がいるとして
中央四つのどこかに荷物がある可能性がある場合はその場所をBとして
■■■■■■
■ ■
■ B .B ■
■ B .B ■
■ ■
■■■■■■
こんな感じにどれかに存在する可能性がある
73:進可 ◆Sinka1my5k
04/08/12 22:01 tDHsu3jM
で、それを上に押し付けた場合は
■■■■■■
■ B .B ■
■ ■
■ ■
■ ■
■■■■■■
こんな風に不確定の位置が変わる。
まだ大雑把な考えだから、これからどう発展させるかはわかってませんが
こんなアイデアもあるよということで晒しておきます。
74:進可 ◆Sinka1my5k
04/09/17 20:11:24 zbFgFr5N
こっちにも報告
ナンバーリンクソルバーが形になったよ。
15*15でも１時間以内で解けます。
URLﾘﾝｸ(www.interq.or.jp)
75:進可 ◆Sinka1my5k
04/11/15 16:42:23 KRK43JVG
自主制作報告のほうにもｱｹﾞたけどこっちにも
URLﾘﾝｸ(gamdev.org)
とりあえずは２ｃｈ上でやりとりできるようなシステムを作った
ボタンでマップチップのテキストを置く
テキストのセーブ＆ロード
ステップの戻しと前進
プレイ中の面をテキストへコピー
プレイしたステップをテキストへコピー
書き出したステップをプレイ開始時に読み込み
■■■■■■■×
■×××××■■
■×田回回回×■
■×回××回足■
■×回××回×■
■×回回回◎×■
■×××××■■
■■■■■■■×
ddldllURdllluuuuurrrDDDuuullld
dRRDrUllluurD
こういう感じで面と解答ステップのやりとりが２ｃｈ上で可能に。
肝心な作り方と解き方は全然だけどな。
76:名前は開発中のものです。
04/11/15 18:00:20 ci0UTB+u
このスレなにげに楽しみにしてるのでがんがれ
77:名前は開発中のものです。
04/12/04 01:52:51 jMAxBzXc
あー
78:進可 ◆Sinka1my5k
05/04/09 20:30:09 FzAyxfw2
ふと考えた。倉庫番を解くプログラムを作る前に、スライドパズルを
解けるようなプログラムを作らないとダメなのではないだろうか？
もっと考えて、１５パズルを解けるようなプログラムを作らないと
ダメなのではないだろうか？
79:名前は開発中のものです。
05/04/09 23:52:01 f0QdQ2zj
作れるんじゃね？
80:名前は開発中のものです。
05/04/09 23:53:30 f0QdQ2zj
つーか
URLﾘﾝｸ(www.ic-net.or.jp)
81:名前は開発中のものです。
06/05/15 15:01:25 iqNZ3zgN
82:進可 ◆Sinka1my5k
06/06/23 01:17:15 rNoNlc0C
【北朝鮮】「悪いやつらをなくそう」 国家公式サイトにオンラインゲーム登場 日本人と米国人の泥棒を退治
ｽﾚﾘﾝｸ(newsplus板)l50
北朝鮮がゲーム作ったと思ったら、ルールも面も日本のパクリだったよｗ
83:名前は開発中のものです。
06/08/11 14:34:16 XHr3GWC7
状態空間探索も知らずに頑張っていたのか・・・
84:名前は開発中のものです。
06/08/11 15:36:04 +c/odd+z
しかし倉庫番というのはなんでああも中途半端な所へ荷物を「片付ける」必要があるのだろう。
85:名前は開発中のものです。
06/08/12 06:15:40 2SZsaOQK
>状態空間探索
詳しく
86:名前は開発中のものです。
07/01/07 01:43:57 3utMDeTC
>>75
最近、倉庫番のはまりだまして活用させて頂いております。
大変ありがとうございます。
87:名前は開発中のものです。
07/07/21 13:46:08 ZgxFvFBu
携帯版 倉庫番Firststep の37面が
かれこれ数年解けません orz
88:名前は開発中のものです。
07/07/26 04:13:55 MyeVtBFN
絶対荷物を移動させない位置を塗り潰し
荷物ごとに可動範囲を設定
目標には置ける可能性のある荷物のインデックスでも持たせる
ある程度絞り込めそうだけど、どうだろ
書いてると作りたくなるｗ
89:名前は開発中のものです。
08/08/12 14:02:26 X38yz9YK
URLﾘﾝｸ(vintermann.paranoidkoala.org)
この人のがどうなったのか気になる
なんかすごい自信満々なんだがソルバがおいてない…
90:名前は開発中のものです。
08/11/15 17:39:16 50CPL4Xv
YASGenあるじゃん