04/08/10 00:00 50wtaTHU
49だが、ハンドルさらし。とりあえず今日は面を読み込んで表示するところまでできた。
で、ナンバーリンクとは何かだが、ぐぐれば判るとおりマス目に書かれた同じ数字を
線で結んで全部繋ぐ紙面パズル。だが、これが別解を見つけるのが異様に困難な
パズルだったりする。複数解があるのは紙面パズルとして致命傷。
ショートカットでつなげられる答えがあるなどもってのほかだったりする。
自動で解くプログラムはいくつかあるようだけど、線が通らないマス目がある別解は
見つけられない。なので自分が挑戦してみようかと、こういう経緯。
51:進可 ◆Sinka1my5k
04/08/10 00:08 50wtaTHU
んで実際にどうみつけるかだけど、いろいろ探ってみたところ
ここに線が引かれるはずだから、あーしてこーして・・・なんて線を延ばすやりかたがほぼ全部。
でも、このやりかたって、ショートカット解はみつけられなかったりするんだよな。
なんたって角地に線が通ることをまず確定させてるし。
で、自分が考え出したパターンはこれとは違い、線ではなくて壁を見るやりかた。
線を引かない部分を壁として、その壁の有無を総あたりでチェックする方法。
具体的なやりかたは次回に。
52:進可 ◆Sinka1my5k
04/08/10 11:21 x1eX9+9e
すまんけど、解説するとかなり長々した文になりそうだ。
スレ乗っ取りになりそうなので、どこか別の糞スレに移って
そこで解説したほうが良さそう。
53:名前は開発中のものです。
04/08/10 13:28 xunPxqDS
>>52
いや、このスレもうほとんど止まってたし・・・このまま進めて欲しいな
54:進可 ◆Sinka1my5k
04/08/10 20:33 P6c4IZR0
>53
そうか、ならば・・・
55:進可 ◆Sinka1my5k
04/08/10 20:34 P6c4IZR0
,ィィ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
_人人人人人人人人人人人人人人_
> な なんだってー!! <
 ̄^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
_,,.-‐-..,,_
/ `''.v'ν
i' / ̄""''--i 7
!ヘ /‐- 、u. |' ちょ、ちょっと待ってくれよキバヤシ、
|'' !゙ i.oニ'ー'〈ュニ! ナンバー(NUMBER)リンク(LINK)だったら
,`| u ..ゝ! 頭文字はMNLに・・・
<:::::\ (二> /
\::::\ '' /
\ \. , ̄
_
58:進可 ◆Sinka1my5k
04/08/10 20:38 P6c4IZR0
|丶 \  ̄ ̄~Y~ 、
| \ __ / \
|ゝ、ヽ ─ / ヽ |
│ ヾ ゝ_ \ |
│ ヽ_ _ / /| |\ \|
\ヽ _ // / | \ |
ヽ\二_二// ∠二二二| ヘ| ナワヤ!勘違いをするな!
| | | ヽゝソゝ|TT|<ゝソ フ |/b} 日本放送協会(NHK)的な
ヾ| ヽ___ ノ/|| .ミ__ ノ | ノ 略語だから何の問題もない!
| ⊿ /フ
| u .F二二ヽ /|/
\. |/⌒⌒| イヽ
/. \ ==′/ |.| |
 ̄|| ヽ__/ / / ̄
\ヽ_____ノ ノ
59:進可 ◆Sinka1my5k
04/08/10 20:38 P6c4IZR0
_,,.-‐-..,,_
/ `''.v'ν
i' / ̄""''--i 7
!ヘ /‐- 、u. |'
|'' !゙ i.oニ'ー'〈ュニ! ・・・・・・・・・
,`| u ..ゝ!
<:::::\ (二> /
\::::\ '' /
\ \. , ̄
_
60:進可 ◆Sinka1my5k
04/08/10 21:24 P6c4IZR0
すまん、連続投稿に引っかったから普通に進めることにする。←バカ者
61:進可 ◆Sinka1my5k
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
さてさて、それで具体的なやり方だけど、上に書いてあるとおりマス目に線を引くんじゃなくて
線を通過しない壁のほうに重みを置いてみる解き方です。
例えば上のニコリのページの問題。一番上の左端のマス目を通る線は
必ず右と下を通過するはずです。普通ならこの角の理論を適用して線を延ばしていくのですが
自分の考えはここからが違う。線を引く部分でなく、線を引かない上と左の壁に注目しました。
判りやすく下の答えを見てみましょう。線を引かない境界の点線に壁を引っ張ると
二つの法則を導きだされます。
「線を引くマスは必ず2方向が壁になる」
「数字の書いてあるマスは必ず3方向が壁になる」
この壁の数を利用して解いていこうというのが、自分の理論です。
64:進可 ◆Sinka1my5k
04/08/10 22:50 P6c4IZR0
具体的には、あるマスAにおいて上と左の壁数を確認します。
線を引くマスで上と左の壁数が
0なら、右と下は必ず壁になる。
1なら、右か下、どちらかが壁。
2なら、右と下は必ず壁が無い。
数字のマスで上の左の壁数が
0はありえないので、それ以前の壁がおかしい
1なら、右と下両方が壁になる。
2なら、右か下、どちらかが壁。
どちらかが壁の場合、仮に右を壁にして下を無しにしておいて次のマスへ進み
ありえない状況になったら戻って下だけ壁に変更して調べなおし、というやりかたです。
それでも駄目ならさらに前に戻って壁を変更します。
これを左上のスタート地点から右へと進めていって、右端についたら改行して
2段目の左端から、と進めていきます。ようするにしらみつぶしなんですね。
65:進可 ◆Sinka1my5k
04/08/10 23:06 P6c4IZR0
でもこのしらみつぶし、結構有効な方法だったりします。
線を伸ばしてどっちへ行くのか調べるとなると、それこそ上下左右好きな方向に
進められるので、相手の数字につくまで途方も無いパターンがあります。
が、この方法で調べていくなら少ないパターンで進めていける上に
壁に矛盾が無くなったら、最後に同じ数字同士が連結しているかを
チェックするだけですみます。
とりあえずこの上と左を見るやり方を、ガンマ方式と名づけます。命名理由は変換したらわかるはず。
実際には、これに加えてありえない壁の形になったらNGにするようプログラムした結果
11×11の面を即断で解けるようになりました。はい、実はもうプログラムはできてます。
今日一日でなんとか完成しました。ただ、盤面入力はテキストファイルだし、結果出力は
イメージに文字出力のみだしで、見た目がかなり汚いので発表はまだです。
っていうか、じっくり解説しながら作ろうと思ってたのに、一日でできるとは自分でもおもわなんだ。
というわけで今日はこれにて。
66:進可 ◆Sinka1my5k
04/08/11 13:00 0BPyFEfS
続き~
そういえば、まだショートカットの探索方法書いてなかったな。
基本的には同じだけど、ショートカットができるってことは何も通らないマス目があるってこと。
これを便宜的に「壁マス」と呼ぶことにして話を進めます。
で、そこの部分の壁をどうするかだけど、線マスと壁マスの間は必ず壁があるが
壁と壁同士はあっても無くてもいいことになってややこしい。なので、壁マスは四方を必ず
壁に囲まれていると定義しておく。その考えで上の探索に追加。
線を引くマスで上と左の壁数が
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
┌─┬─┬─┬─┐
│┏┿━┿━┥1│
├╂┼─┼─┼─┤
│┃│2┝━┥2│
├┸┼─┼─┼─┤
│1│3┝━┥3│
└─┴─┴─┴─┘
こんなのどう?
68:進可 ◆Sinka1my5k
04/08/11 23:01 HfZVR1XV
>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
最終チェック=マス目に壁が全部埋まった時点で全部の数字の到達先を調べる
途中チェック=現在のマスが数字で上か左が開いていたらリンク先を調べる
改行チェック=マスが一段埋まるたびにマス確定した上段数字マスの到達先を全部チェック。
7*7での回数
ショートカットチェック あり なし
最終チェックのみ 181 435102
+途中もチェック 179 303781
+改行もチェック 167 228814
数は減らせたけど、指数的に減ってないのでダメです。
10*10でショートカットありだと、探索が遅くなるばかりで解ける気配がぜんぜんありません。
ちなみに回数とは、最初のマスの壁の有無を確定して1回、次のマスの壁を確定して2回
という風に数えてます。それを考えると3ケタですんでるのは驚異的なんだけどね。
でもショートカット探索ありだと、ぜんぜん太刀打ちできないんだよな。
70:進可 ◆Sinka1my5k
04/08/12 13:18 FoaiKiVA
ところでパズル板ができたね。
URLリンク(hobby5.2ch.net)
とりあえず7*7までならチェックできたし
これ以上の改良は、なんかとてつもなく長くなりそうだから
一旦ここで打ち切って、移動した方がよさげ。
倉庫番探索もそのうち考えます。
71:名前は開発中のものです。
04/08/12 17:51 6v5uYIwl
あ゛~、見てるだけで終わってしまった。
72:進可 ◆Sinka1my5k
04/08/12 22:00 tDHsu3jM
なんか新しいパターンがあったら伝えますですのことよ。
ところで倉庫番で考えてるんだけど、荷物の位置を不確定にできないかなというアイデア。
例えば4×4の空間に荷物一個と人がいるとして
中央四つのどこかに荷物がある可能性がある場合はその場所を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でも1時間以内で解けます。
URLリンク(www.interq.or.jp)
75:進可 ◆Sinka1my5k
04/11/15 16:42:23 KRK43JVG
自主制作報告のほうにもアゲたけどこっちにも
URLリンク(gamdev.org)
とりあえずは2ch上でやりとりできるようなシステムを作った
ボタンでマップチップのテキストを置く
テキストのセーブ&ロード
ステップの戻しと前進
プレイ中の面をテキストへコピー
プレイしたステップをテキストへコピー
書き出したステップをプレイ開始時に読み込み
■■■■■■■×
■×××××■■
■×田回回回×■
■×回××回足■
■×回××回×■
■×回回回◎×■
■×××××■■
■■■■■■■×
ddldllURdllluuuuurrrDDDuuullld
dRRDrUllluurD
こういう感じで面と解答ステップのやりとりが2ch上で可能に。
肝心な作り方と解き方は全然だけどな。
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
ふと考えた。倉庫番を解くプログラムを作る前に、スライドパズルを
解けるようなプログラムを作らないとダメなのではないだろうか?
もっと考えて、15パズルを解けるようなプログラムを作らないと
ダメなのではないだろうか?
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
北朝鮮がゲーム作ったと思ったら、ルールも面も日本のパクリだったよw
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
絶対荷物を移動させない位置を塗り潰し
荷物ごとに可動範囲を設定
目標には置ける可能性のある荷物のインデックスでも持たせる
ある程度絞り込めそうだけど、どうだろ
書いてると作りたくなるw
89:名前は開発中のものです。
08/08/12 14:02:26 X38yz9YK
URLリンク(vintermann.paranoidkoala.org)
この人のがどうなったのか気になる
なんかすごい自信満々なんだがソルバがおいてない…
90:名前は開発中のものです。
08/11/15 17:39:16 50CPL4Xv
YASGenあるじゃん