5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :名前は開発中のものです。:04/07/03 08:04 ID:/HqS7Sh0
国産パズルゲームの名作「倉庫番」の問題面を
自動で生成したり解いたりするには
どのようなプログラムを書けばいいでしょうか?

プログラムの達人から初心者まで
興味のある方は是非参加してください。

2 :名前は開発中のものです。:04/07/03 08:04 ID:/HqS7Sh0
公式
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 :名前は開発中のものです。:04/07/03 08:05 ID:/HqS7Sh0
まずは、縦10 x 横10、荷物3個くらいまでの
小さな問題面(を作る・解く)からだと思うのですが
何から手をつければよいのやら

作るためにはまず解けなければならないのか、
それとも解くルーチンが脆弱でもそこそこは作れるのかな?

4 :名前は開発中のものです。:04/07/03 08:31 ID:7RtovP1J
>>1
疋田センセにでも聞け。糸終


5 :名前は開発中のものです。:04/07/03 08:56 ID:T5561hDd
解けない面を作られても困るし作るよりも解く方が先。
で、そいつで解けるレベルのものなら作れると

6 :名前は開発中のものです。:04/07/03 13:20 ID:QlamLHhp
>>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 :名前は開発中のものです。:04/07/04 11:07 ID:39IxYScY
荷を引っ張る倉庫番プログラムなら簡単に問題作成できそう

8 :名前は開発中のものです。:04/07/04 20:54 ID:WaLy+q++
どっかで問題作成をプログラミングしてたような気がするが、どこだったかは忘れた

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

10 :名前は開発中のものです。:04/07/05 12:13 ID:+7Vba4Jo
すぐ飽きるとおもう一部の変質者以外

11 :名前は開発中のものです。:04/07/05 23:54 ID:n2HoeUWw
マルチスレか。良い根性してるな。

12 :名前は開発中のものです。:04/07/06 21:32 ID:+dqSWx6h
##########
#  $  .  #
#      . #
#    $   #
##     . #
###  $  ##
## @     #
##########

こんなんばっかになりそう。

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

14 :名前は開発中のものです。:04/07/07 22:31 ID:+MuW8iQV
>13
###################
# $              .#
# $              .#
# $              .#
# $              .#
# $              .#
# $              .#
# $            @ .#
#                 #
###################

15 :名前は開発中のものです。:04/07/07 23:43 ID:u5TlYlHT
>>13
手数 * (1 / 正当数) = 難易度

とかの方が良くないか?>>14みたいに手数は多いが同時に正当数がいっぱいある奴は当然難易度は下がると。

16 :名前は開発中のものです。:04/07/08 10:03 ID:NzVDRXHr
あとは面の広さか若しくは移動可能チップ数
さらに荷物の数も要素に加えて難易度を算出すれば
精度が高まる気がする。

17 :名前は開発中のものです。:04/07/08 17:17 ID:CnPgVFe8
倉庫番を解く for Windows
http://www.ic-net.or.jp/home/takaken/so/soko/index.html

参考にどうぞ

18 :12,14:04/07/08 17:49 ID:zY8B1Wlv
10×10の中心からランダムに領域を広げていくという方法で作った部屋の例1

##########  ##########  ##########  ##########
#     ####  ###    ###  ##########  ##########
## ##    #  ###     ##  # ###### #  ##########
##       #  ###      #  #  ##    #  ##########
##      ##  ###  #####  #        #  ###     ##
###     ##  ###  # ###  #   #    #  ###      #
###      #  ###     ##  #   #    #  ###      #
###      #  ###      #  #        #  ######   #
##       #  ###    ###  ##       #  ##########
##########  ##########  ##########  ##########


19 :12,14:04/07/08 17:50 ID:zY8B1Wlv
10×10の中心からランダムに領域を広げていくという方法で作った部屋の例2

##########  ##########  ##########  ########## 
####### ##  ##     ###  ####  #  #  #  # #   # 
###  #   #  ###    ###  ####  #  #  #  #     # 
##       #  ###      #  ####     #  #        # 
###      #  #        #  ###      #  ##       # 
###     ##  #        #  ####     #  #        # 
###     ##  #        #  ###   #  #  ###      # 
###    ###  #        #  ##    ## #  ###      # 
####  ####  #   #    #  ##    ####  ####     # 
##########  ##########  ##########  ########## 


20 :12,14:04/07/08 17:58 ID:zY8B1Wlv
#と全角スペースが同じ幅になるようなフォントで見て下ちい。

21 :名前は開発中のものです。:04/07/09 00:11 ID:4wETax93
ジャーナル アブストラクトVol.39 No.03 - 007
「倉庫番」の問題の自動作成
http://www.ipsj.or.jp/members/Journal/Jpn/3903/article007.html
ぐぐったらこんなん見つかった
でも会員じゃないと内容読めないみたい

22 :概要:04/07/09 03:13 ID:sexttaP2
読んでみたけど別段どうという事のない論文だな。
普通にプログラミングの能力のある人なら
考え付きそうな事をやってるだけで。

作ってる問題は 盤は8x8, 荷物は3つ。
リンク先にあるように
・問題作成→解を求める→面白さを評価
というステップを繰り返して、詰まらない問題は自動判定して捨てて、
面白い問題がいくつ出来るか、とかやってる。

実験結果の例
 作成失敗 2
 解なし 153
 解ありだかつまらないと自動判定されて捨てられた 287
 解ありでプログラムで捨てられなかった 58
合計 500

500回ループさせて残った問題が58。そのうち筆者が実際に解いて
面白いと感じられた問題が13だったと。

23 :セックスタップ2:04/07/09 03:24 ID:sexttaP2
部屋の作り方
・初期状態は以下のようにする。
########
########
##    ##
## ## ##
##    ##
########
########
########
########

これに下の3つのパーツをランダムに投下して部屋を作る。
口口 (3*2の空白パーツ)
口口
口口

口口 (2*2の空白パーツ)
口口

口口口 (3*3の空白パーツの中央に壁)
口#口
口口口

部屋のパーツを選ぶ事でつまらない部屋が出来ないようにするらしい。

24 :セックスタップ2:04/07/09 03:42 ID:sexttaP2
ゴールをおけないパターンにはどういうものがあるか考察してあり、
(まあ、ある程度考えれば考え付くようなパターン)
それをさけてゴールをランダムに配置。
また同様にある程度考えて荷物と人を配置。
面の作成はそれくらい。

次のステップで幅優先探索で最短の解を求める。

次の評価のステップだが、面白さの評価基準は
(1)手数、(2)荷物の持ち替え回数、(3)遠回り数、(4)部屋の広さ(マスの数)
を基準に判定している。
遠回りというのは、みかけの荷物とゴールの最短距離と
実際に荷物が移動した距離の差、らしい。
(距離は“マンハッタン距離”とか書いてある。)
持ち替えとは今持っている荷物を離し別の荷物を押す事を示す。
荷物の持ち替えが 多く必要な程、面白いと判断されるから、との事。

判定の具体的な数値は
・遠回りせずに解ける
・荷物の持ち替えが3回以下
・解が6手以内
の一つ以上あてはまったら、この問題を捨てる、との事。

考察に置いて、プログラムに実装されているかどうかに関わらず
以下のように述べている。
・荷物の持ち替え数のパラメータは難しさの評価に有効と言える。
・荷物の方向転換。面白い問題では同じ荷物を押し続ける時でも
 こまめに方向転換する必要がある傾向が認められる。
・手数。多い方がよいが、単に荷物とゴールの距離が遠いだけの事もある。
・遠回り。発見しやすい遠回りもあるので面白さに直結しない場合もある。

25 :セックスタップ2:04/07/09 04:06 ID:sexttaP2
考察の続き
・ゴールが邪魔。ゴールが隅の邪魔にならない所にあるのは簡単になりやすい。
 面白い問題の多くはゴールを荷物が何度も通過する。
・荷物の軌跡が複雑。荷物の軌跡が他の荷物の軌跡と交差したり
 絡み合ってると面白い事が多い。しかし軌跡が重ならなくても
 面白いものはある。

実際に作成された問題の例
(#:壁, ・:ゴール, $:荷物, ■ゴール+荷物, 人:人)

######## ########
###  ### ########
##    ## ##  ・ ##
# ・ ・$## ##人# ■##
#  $人  # ##  $ ##
####■# # ## #■ ##
####   # ##    ##
######## ########

######## ########
######## ########
##    ## ## ・ ■##
##・##$ # ##  #  #
# ・・$  # ##人$■  #
#  #$  # ###   ##
#  人 ### ###   ##
######## ########

(以上)

26 :セックスタップ2:04/07/09 04:27 ID:sexttaP2
荷物をゴールに置いて逆の動作で荷物を移動して
問題を作ればいいかなと思っていたんだけど
著者らはそういう事はしていないですね。

27 :名前は開発中のものです。:04/07/09 10:34 ID:mw4kM0V8
なるほど、つまり・・・

1:壁とゴールと人の最終形をランダムで作成。

2:ランダムに一つずつ荷物を引く

3:その形の最短手順を調べる

4:一番手数の多い面を初期配置とする

ってことか。

28 :名前は開発中のものです。:04/07/09 10:43 ID:mw4kM0V8
いや待てよ、2:の引っ張りは、同じ形を繰り返す可能性が高いから無駄が多いかも。
だとしたら・・・

2:荷物を移動させた全パターンを調べる

3:一番最短の手数の多い面を初期配置とする

のほうが速いかもな。

なんか結局上のと似たようなものになってしまった。

29 :名前は開発中のものです。:04/07/10 00:11 ID:AGnyOuyl
どうでも良いがいい加減空白調整してくれ。

読むに至らない論文は内容に依らず勝ちはない。


30 :セックスタップ2:04/07/10 00:19 ID:ErOnlOXh
マカー。

31 :セックスタップ2:04/07/10 00:20 ID:ErOnlOXh
自分で見てるとバッチリなんですよねぇ

32 :名前は開発中のものです。:04/07/10 00:23 ID:AGnyOuyl
あれ?矯正IDになってる?

33 :セックスタップ2:04/07/10 00:26 ID:ErOnlOXh
? この板始めてだからよく知らない。(プログラム技術板からついて来た)

34 :名無しさん@そうだ選挙に行こう:04/07/11 09:25 ID:YxVEQ1eT
漢なら自動プログラムなどに頼るな

35 :名前は開発中のものです。:04/07/13 07:26 ID:gifgN+Yd
日経ソフトウエア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 :名前は開発中のものです。:04/07/27 12:57 ID:H2IKfXqP
人が歩いた歩数でなく、荷物が動いた歩数で考えた方が楽なのだろうか?

37 :名前は開発中のものです。:04/07/28 13:16 ID:awaEZIr2
完成状態の盤面を0番として記憶しておく。
初期の荷物の状態を1として、そこから移行できる全状態を2以降の番号をつけて生成し、記憶。
1番からどの番号へ移行できるかも記憶しておく。
続いて、2番の状態から移行できる全状態を生成し、記憶。もちろん重複チェックもさせるので
前の番号へ移行できるような状態も作られる。

次々に生成していって、0番への移行ができるような盤面が現れたら解決方法あり。
1番からの深度チェックをしていって、荷物を何手動かしたかの最短を出す。
ただし確実な最短を出すためには全手数のチェックが必要。

解く方のやり方を想定してみたが、こんな感じなのか?

38 :名前は開発中のものです。:04/07/28 23:27 ID:OaJflA5G
大体そんな感じだと思う。

>ただし確実な最短を出すためには全手数のチェックが必要。
幅優先探索でやれば最初に見つかったのが最短手順。
「幅優先探索」で検索してみて。

>もちろん重複チェックもさせるので前の番号へ移行できるような状態も作られる。
? 前と同じ状態に戻る場合は発生させなくてよいと思う。

39 :名前は開発中のものです。:04/07/29 01:54 ID:EpgRoJim
指数オーダーで状態が増えていくから全列挙ベースじゃ規模の小さい問題しか解けない。
これは探索の方向を変えたところでどうしようもない。
人間が解いて面白いような規模の問題を解くのは無理っぽい。

で、どうするかというとA*とか分枝限定法とかの下界値を利用して枝刈りするような手法が使われる。
もっともそっちの世界でも倉庫番は難しい問題として知られてるから、良い方法が作れればそれだけで論文書けるかも。

まあ、そこまでいかなくても単純なA*くらいは入れた方が良いと思う。
経路探索にも使える(というかそっちの方が多い)から知ってて損はないし。

40 :37:04/07/29 05:40 ID:4YxMTCfg
ご意見どうもでつ。なるほど、かなり奥が深そうだ。
調べてみたら、双方向探索とか行き詰まりのつぶしとか色々あるようだし。

41 :名前は開発中のものです。:04/08/01 03:05 ID:Q2G2XU2Z
プログラムによる自動生成全52面
ttp://www.ne.jp/asahi/ai/yoshio/sokoban/auto52/index.html

42 :名前は開発中のものです。:04/08/01 11:46 ID:YiQa0gMz
>>41
そのプログラムそのものはどこかにないの?

43 :名前は開発中のものです。:04/08/01 14:16 ID:VNo3uGvt
移転前
ttp://web.archive.org/web/20020609073807/http://www.ne.jp/asahi/ai/yoshio/sokoban/main.htm

自動生成のプログラムそのものはないみたい

44 :名前は開発中のものです。:04/08/07 00:22 ID:xSvexrpg
この小田原研究が見たいが、見つからない。
ttp://www.graco.c.u-tokyo.ac.jp/kawai-kaneko-lab.html

45 :名前は開発中のものです。:04/08/07 00:35 ID:XI18DeZP
>>35をコンパイルしたの頂けないでしょうか


46 :名前は開発中のものです。:04/08/07 10:54 ID:t8/IjFAc
>>45
バイナリじゃないんだ。。。
readme.txtによるとBorland C++ Compilerでビルドせよとのこと。

Borland C++ Compilerは以下から無償で入手できるよ
http://www.borland.co.jp/cppbuilder/freecompiler/bcc55steps.html
メール登録(無料)が必要らしいね。

さすがにユーザー登録的な手続きまでするのは面倒くさいから
気が向いたら自分でチャレンジしてみて。
コンパイル自体は楽勝で誰だって出来るから

47 :名前は開発中のものです。:04/08/09 07:53 ID:LuKJ2ExA
いきなりネタ無くなってる感がするんだが
他のパズルの自動プログラムもOK?

48 :名前は開発中のものです。:04/08/09 14:22 ID:Bm7y7lhR
基本は変わらないし、参考になるから
いいんじゃないか?

49 :名前は開発中のものです。:04/08/09 18:45 ID:BKqxHMzO
それじゃ、昔やったナンバーリンクの自動解答に挑戦してみる。

50 :進可 ◆Sinka1my5k :04/08/10 00:00 ID:50wtaTHU
49だが、ハンドルさらし。とりあえず今日は面を読み込んで表示するところまでできた。

で、ナンバーリンクとは何かだが、ぐぐれば判るとおりマス目に書かれた同じ数字を
線で結んで全部繋ぐ紙面パズル。だが、これが別解を見つけるのが異様に困難な
パズルだったりする。複数解があるのは紙面パズルとして致命傷。
ショートカットでつなげられる答えがあるなどもってのほかだったりする。

自動で解くプログラムはいくつかあるようだけど、線が通らないマス目がある別解は
見つけられない。なので自分が挑戦してみようかと、こういう経緯。

51 :進可 ◆Sinka1my5k :04/08/10 00:08 ID:50wtaTHU
んで実際にどうみつけるかだけど、いろいろ探ってみたところ
ここに線が引かれるはずだから、あーしてこーして・・・なんて線を延ばすやりかたがほぼ全部。
でも、このやりかたって、ショートカット解はみつけられなかったりするんだよな。
なんたって角地に線が通ることをまず確定させてるし。

で、自分が考え出したパターンはこれとは違い、線ではなくて壁を見るやりかた。
線を引かない部分を壁として、その壁の有無を総あたりでチェックする方法。
具体的なやりかたは次回に。

52 :進可 ◆Sinka1my5k :04/08/10 11:21 ID:x1eX9+9e
すまんけど、解説するとかなり長々した文になりそうだ。
スレ乗っ取りになりそうなので、どこか別の糞スレに移って
そこで解説したほうが良さそう。

53 :名前は開発中のものです。:04/08/10 13:28 ID:xunPxqDS
>>52
いや、このスレもうほとんど止まってたし・・・このまま進めて欲しいな

54 :進可 ◆Sinka1my5k :04/08/10 20:33 ID:P6c4IZR0
>53
そうか、ならば・・・

55 :進可 ◆Sinka1my5k :04/08/10 20:34 ID: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 ID: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 ID:P6c4IZR0
     _,,.-‐-..,,_    
  /     `''.v'ν
  i'   / ̄""''--i 7 
  !ヘ /‐- 、u.   |'   ちょ、ちょっと待ってくれよキバヤシ、
  |'' !゙ i.oニ'ー'〈ュニ!  ナンバー(NUMBER)リンク(LINK)だったら
 ,`| u       ..ゝ!   頭文字はMNLに・・・
<:::::\   (二> /   
 \::::\ '' /
\ \. , ̄
    _

58 :進可 ◆Sinka1my5k :04/08/10 20:38 ID:P6c4IZR0

   |丶   \   ̄ ̄~Y〜 、
  |  \ __    /    \
  |ゝ、ヽ  ─     /    ヽ |
 │ ヾ ゝ_         \  |
 │  ヽ_ _ / /| |\   \|
  \ヽ   _ // / |  \   |
   ヽ\二_二// ∠二二二| ヘ|    ナワヤ!勘違いをするな!
    | | | ヽゝソゝ|TT|<ゝソ フ |/b}    日本放送協会(NHK)的な
    ヾ| ヽ___ ノ/|| .ミ__ ノ | ノ     略語だから何の問題もない!
      |       凵@     /フ
      | u .F二二ヽ   /|/
      \.   |/⌒⌒|   イヽ
      /. \  ==′/ |.| |
      ̄||  ヽ__/  / / ̄
      \ヽ_____ノ ノ

59 :進可 ◆Sinka1my5k :04/08/10 20:38 ID:P6c4IZR0
     _,,.-‐-..,,_    
  /     `''.v'ν
  i'   / ̄""''--i 7 
  !ヘ /‐- 、u.   |'  
  |'' !゙ i.oニ'ー'〈ュニ! ・・・・・・・・・
 ,`| u       ..ゝ!  
<:::::\   (二> /   
 \::::\ '' /
\ \. , ̄
    _

60 :進可 ◆Sinka1my5k :04/08/10 21:24 ID:P6c4IZR0
すまん、連続投稿に引っかったから普通に進めることにする。←バカ者

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


62 :進可 ◆Sinka1my5k :04/08/10 22:30 ID:P6c4IZR0
で、これを解く為のソルバープログラムなんだけど、検索してみたところ
ソフトの存在はベクターに一つだけって状況で、しかもそれはショートカットの別解を
チェックできなかったりする。他のページの日記には、これの解答ソフトは
要望はあるけどモノが無い、と書かれている存在だそうで。

だったら俺が作ってやろうと思い立ったわけで・・・っていうか、実は理論なら
とうの昔にできていて、しかもその内容がとあるトコに掲載されたこともあったりして。
かなり昔のことなんだけどね。資料はまだ残っていたから作成はできるはず。
ただ、今回はこれを別解を確認できるように拡張していくという課題も追加。

63 :進可 ◆Sinka1my5k :04/08/10 22:39 ID:P6c4IZR0
さてさて、それで具体的なやり方だけど、上に書いてあるとおりマス目に線を引くんじゃなくて
線を通過しない壁のほうに重みを置いてみる解き方です。
例えば上のニコリのページの問題。一番上の左端のマス目を通る線は
必ず右と下を通過するはずです。普通ならこの角の理論を適用して線を延ばしていくのですが
自分の考えはここからが違う。線を引く部分でなく、線を引かない上と左の壁に注目しました。

判りやすく下の答えを見てみましょう。線を引かない境界の点線に壁を引っ張ると
二つの法則を導きだされます。
 「線を引くマスは必ず2方向が壁になる」
 「数字の書いてあるマスは必ず3方向が壁になる」

この壁の数を利用して解いていこうというのが、自分の理論です。

64 :進可 ◆Sinka1my5k :04/08/10 22:50 ID:P6c4IZR0
具体的には、あるマスAにおいて上と左の壁数を確認します。

線を引くマスで上と左の壁数が
 0なら、右と下は必ず壁になる。
 1なら、右か下、どちらかが壁。
 2なら、右と下は必ず壁が無い。
数字のマスで上の左の壁数が
 0はありえないので、それ以前の壁がおかしい
 1なら、右と下両方が壁になる。
 2なら、右か下、どちらかが壁。

どちらかが壁の場合、仮に右を壁にして下を無しにしておいて次のマスへ進み
ありえない状況になったら戻って下だけ壁に変更して調べなおし、というやりかたです。
それでも駄目ならさらに前に戻って壁を変更します。
これを左上のスタート地点から右へと進めていって、右端についたら改行して
2段目の左端から、と進めていきます。ようするにしらみつぶしなんですね。

65 :進可 ◆Sinka1my5k :04/08/10 23:06 ID:P6c4IZR0
でもこのしらみつぶし、結構有効な方法だったりします。
線を伸ばしてどっちへ行くのか調べるとなると、それこそ上下左右好きな方向に
進められるので、相手の数字につくまで途方も無いパターンがあります。
が、この方法で調べていくなら少ないパターンで進めていける上に
壁に矛盾が無くなったら、最後に同じ数字同士が連結しているかを
チェックするだけですみます。

とりあえずこの上と左を見るやり方を、ガンマ方式と名づけます。命名理由は変換したらわかるはず。

実際には、これに加えてありえない壁の形になったらNGにするようプログラムした結果
11×11の面を即断で解けるようになりました。はい、実はもうプログラムはできてます。
今日一日でなんとか完成しました。ただ、盤面入力はテキストファイルだし、結果出力は
イメージに文字出力のみだしで、見た目がかなり汚いので発表はまだです。

っていうか、じっくり解説しながら作ろうと思ってたのに、一日でできるとは自分でもおもわなんだ。
というわけで今日はこれにて。

66 :進可 ◆Sinka1my5k :04/08/11 13:00 ID: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 ID:k24CCh2Y
┌─┬─┬─┬─┐
│┏┿━┿━┥1│
├╂┼─┼─┼─┤
│┃│2┝━┥2│
├┸┼─┼─┼─┤
│1│3┝━┥3│
└─┴─┴─┴─┘
こんなのどう?

68 :進可 ◆Sinka1my5k :04/08/11 23:01 ID: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 ID:FoaiKiVA
最終チェック=マス目に壁が全部埋まった時点で全部の数字の到達先を調べる
途中チェック=現在のマスが数字で上か左が開いていたらリンク先を調べる
改行チェック=マスが一段埋まるたびにマス確定した上段数字マスの到達先を全部チェック。

7*7での回数
ショートカットチェック あり なし
最終チェックのみ 181 435102
+途中もチェック  179 303781
+改行もチェック  167 228814

数は減らせたけど、指数的に減ってないのでダメです。
10*10でショートカットありだと、探索が遅くなるばかりで解ける気配がぜんぜんありません。
ちなみに回数とは、最初のマスの壁の有無を確定して1回、次のマスの壁を確定して2回
という風に数えてます。それを考えると3ケタですんでるのは驚異的なんだけどね。
でもショートカット探索ありだと、ぜんぜん太刀打ちできないんだよな。

70 :進可 ◆Sinka1my5k :04/08/12 13:18 ID:FoaiKiVA
ところでパズル板ができたね。
http://hobby5.2ch.net/puzzle/
とりあえず7*7までならチェックできたし
これ以上の改良は、なんかとてつもなく長くなりそうだから
一旦ここで打ち切って、移動した方がよさげ。

倉庫番探索もそのうち考えます。

71 :名前は開発中のものです。:04/08/12 17:51 ID:6v5uYIwl
あ゛〜、見てるだけで終わってしまった。

72 :進可 ◆Sinka1my5k :04/08/12 22:00 ID:tDHsu3jM
なんか新しいパターンがあったら伝えますですのことよ。
ところで倉庫番で考えてるんだけど、荷物の位置を不確定にできないかなというアイデア。

例えば4×4の空間に荷物一個と人がいるとして
中央四つのどこかに荷物がある可能性がある場合はその場所をBとして

■■■■■■
■        ■
■  B .B   ■
■  B .B   ■
■        ■
■■■■■■
こんな感じにどれかに存在する可能性がある

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

74 :進可 ◆Sinka1my5k :04/09/17 20:11:24 ID:zbFgFr5N
こっちにも報告
ナンバーリンクソルバーが形になったよ。
15*15でも1時間以内で解けます。
ttp://www.interq.or.jp/moonstone/person/numlink/index.html

75 :進可 ◆Sinka1my5k :04/11/15 16:42:23 ID:KRK43JVG
自主制作報告のほうにもアゲたけどこっちにも
ttp://gamdev.org/up/img/1872.lzh
とりあえずは2ch上でやりとりできるようなシステムを作った


ボタンでマップチップのテキストを置く
テキストのセーブ&ロード
ステップの戻しと前進
プレイ中の面をテキストへコピー
プレイしたステップをテキストへコピー
書き出したステップをプレイ開始時に読み込み

■■■■■■■×
■×××××■■
■×田回回回×■
■×回××回足■
■×回××回×■
■×回回回◎×■
■×××××■■
■■■■■■■×

ddldllURdllluuuuurrrDDDuuullld
dRRDrUllluurD

こういう感じで面と解答ステップのやりとりが2ch上で可能に。

肝心な作り方と解き方は全然だけどな。

76 :名前は開発中のものです。:04/11/15 18:00:20 ID:ci0UTB+u
このスレなにげに楽しみにしてるのでがんがれ

77 :名前は開発中のものです。:04/12/04 01:52:51 ID:jMAxBzXc
あー

31 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)