【解答】パズルのプログラミング【作成】

1 ：04/08/14 〜 最終レス ：2012/05/30

パズルの問題をプログラムで解いたり
プログラムで面を作成したりする方法を話し合うスレ。

2 ：

2

3 ：

3 PRINT "スリーセブンの3ゲット"

4 ：

15パズル、倉庫番、ナンプレ、お絵かきロジック、ライツアウト
ttp://www.ic-net.or.jp/home/takaken/

5 ：

覆面算
ttp://bach.istc.kobe-u.ac.jp/puzzle/

6 ：

数独、Ｎクイーン、カナオレ、ましゅ
ttp://rogiken.org/puzz/program/index.html

7 ：

ピクロス
ttp://www.alpha-net.ne.jp/users2/cult/java/

8 ：

ナンプレ
ttp://be__.at.infoseek.co.jp/java/nps/

9 ：

で、今、自分が挑戦してるのがナンバーリンクのソルバーだったりする。
15*15でも即答できるようになったが、問題は別解探索。
数字が通らないマスもあるのを前提にすると、10*10でも解けなくなる。
関西解探索ありの限度は、今は7*7ぐらいだ。

10 ：

バグﾃﾞﾀ━━━(ﾟ∀ﾟ)━━━!!!!!
計算順序でのものなので１から作り直します。
関西チェックは10*10なら30分ぐらいで発見できるレベル。まだまだだな。

11 ：

ｶﾞﾝｶﾞﾚ！

12 ：

頑張ってるー。今気がついたんだけど７×７のマスが１０×１０になると
面積は倍以上になるんだな。７×７で４９だけど１０×１０は１００マス。
どうりでここらへんから急に遅くなるはずだ。探索数から考えると５０マス増えたとして
２の５０乗倍に増えるということになるし。こりゃやっかいなＮＰ問題に手を出したかも。

13 ：

自分も作ろうと思ったのだが、
>>1はなにで作ってる？

14 ：

Delphiだよ。無料でＷｅｂにもそこそこ情報があるからこれにした。

15 ：

ｻﾝｸｽ
ちょっと勉強してみることにするよ。

16 ：

ｲﾝｽｺ完了ヽ(´ー｀)ノ
今日は眠いから明日にでものんびりいくとするよ。

17 ：

>>1
大変だなぁDelphiなんて。
学生だったらマイクロソフトがたまにやるイベントとかで
.net配ったりするからそれをもらったほうがいいかもね。

18 ：

>17
その.ＮＥＴはＣです？ＪＡです？ＶＢです？
言語選ぶ時にどれにしようか色々悩んだけどね。
２ＣＨやその他で色々調べた結果これになったよ。
>16
ガンガレー。Ｃより楽だしＶＢみたいに外部ＤＬＬがいらないから
ちょっとしたものを作って配布するのに便利だぞ。

19 ：

JavaScriptでスライドパズルなら作ったことがある、
解けるものと解けないものがあるのには驚いたな。

20 ：

今日の成果ー。見つけるまでの時間を測定するようにした。
現在、10*10で短絡解ありをチェックして平均１分半で見つけるように。
ようやく進歩が見えてきた感がある。
だが、10*10の短絡が無い盤面を短絡チェックしようとすると
無いと判明するまで６分３０秒。2.4Ｇｈｚでこれではまだまだっす。
>19　トポロジーというやつですな。

21 ：

とりあえず慣れるためにボンバーパズル4×4を作成。
問題自動作成と最低限の機能を持ったものが3時間ほどで完成ヽ(´ー｀)ノ
ちょっと慣れたからそろそろ解答プログラム作りに入る予定。
>>4-8にないものを作ろうと思案中。
でも出てないやつって難しいんだろうか・・・_|￣|○

22 ：

とりあえずプログラムならこの辺も押さえておかんと。特に最初の。
ペントミノ詰・数独・カックロ・四角に切れ・ひとりにしてくれ・美術館・橋かけ
http://www.pro.or.jp/~fuji/puzzlestudy/index.html
黒どこ
http://f24.aaacafe.ne.jp/~nikolist/puzzle/kurodoko.html
シンクローン
http://f24.aaacafe.ne.jp/~nikolist/puzzle/synchro.html

23 ：

>>22
ｻﾝｸｽ!
なんか難しそうだけどよく読んで勉強するよ。

24 ：

なんとなく好きなぬりかべにすることに決定。
とりあえず初期段階の１の四方を黒にするのは成功。
ifの入れ子でエラーだしまくったよ････_|￣|○

25 ：

そして今caseに気づいた自分_|￣|○

26 ：

…1の四方なんてどうでもよいかと。
あと意外とぬりかべは面倒なので注意。
とりあえずその程度の腕だときついんじゃないかなあと思った。
ネタがかぶってもいいので簡単なパズルを練習に作ってみるのがよいかと。

27 ：

やっぱそうか(´･ω･｀)
ってことで見た感じ一番スタンダードな数独をやってる。
とりあえず順調にいってる予感。

28 ：

今日はエディタの進行。数字を置いたりズラしたりできるように。
高速解答の順序もなんとなくやりかたをつかめ始めた気がする。
基本として、枝狩りの時は初期の枝を重視すべし、だな。
やや時間がかかってもいいから、良くあるありえないパターンは
先にはじいておいた方が、大きな面が速く解ける。
ところで、ペントミノなんかの敷き詰め問題の解き方が
どうしても想像つかんのだが。

29 ：

>>28
ペントミノなら藤原氏のところにプログラムがあるよ。
左上から順に置けるところにピースを置いていくだけで、
今の計算機なら数秒で前階が出る。

30 ：

漏れはパズルを甘く見すぎてたようだ_|￣|○
けっこう難しいな･････
とりあえずじっくりいくか･･･

31 ：

>>29
なぜそんなやりかたでいいのか？という理由がわからんのですよ。
とてもいいかげんそうで穴があるように見えてしまう。
でも解けるらしい。なんで？

32 ：

左上から順につめつめに置いていくから、最後まで置けたときには必ず解になっている。
置けるパターンを全部試しているのだからあのやりかたで漏れているパターンはないはず。
盤面のプリント関数が用意してあるから、あちこち挿んで実行してみると動きがわかっていいよ。
氏の「再帰のお勉強」に割と詳しめの解説があります。

33 ：

>32
サンクス。やっと感覚的に理解できたよ。
再帰はわかってたけど、それをどう応用するのかがわからんかった。
パズル解答のプログラミングって、再帰は重要だよな。
初心者はまず、でこぼこのマス目を塗りつぶせるようなプログラムを作るべしと思う。

34 ：

今日のナンリンソルバー成果ー。ファイルのロード＆セーブ機能をつけた。
これでニコリのいろんな面を確かめられる。
今までテキストのコピペでやりくりしてたから楽になるぜ。
高速化も実行。チェックスピードは遅くなったものの全体的な解析力は向上。
10*10の全短絡解析を数秒〜11分で。数字が少ないと一気に長くなるな。
あと、物は試しに11*11の面をチェックしてみたら・・・１時間近くかかったよ＿|￣|○
これまで色々ブレイクスルーな方法で時間短縮してきたけど
もう一皮向けないとダメってことか。厳しいな。

35 ：

ソースや理論をageて皆でたたき台にすればいいんだがな。
ペンシルパズルはオープンソースモデルが向いているだろう。

36 ：

新たなるブレイクスルー発見。
10*10の短絡チェックを多くても２分以内で解析できるように。
11*11も３分程度で完了。でも15*15までにはまだまだ。
そろそろ遅くなってきたから、計算そのものの高速チューニングを検討してみる。

37 ：

そろそろハンドルつけます。あと、解析方法も晒してなかったから解説。
数字同士を繋げている線でなく、線が通過していない壁に注目しました。
ラインが通っているマスは上下左右のうち、２方がライン、２方が壁になります。
ある一つのマスがあるとして、その上と左を調べます。
上と左の壁数が
　２つの場合、右と下は壁は０です。
　１つの場合は、右か下どちらか一つが壁です。
　０の場合は、右と下は両方とも壁です。
数字の入っているマスの場合は１方がラインで、残り三方は壁です。そして
上と左の壁数が
　２つの場合は、右か下どちらか一つが壁です。
　１つの場合は、右と下は両方とも壁です。
　０の場合はありえません。
これを、左上から右に向けて１マスずつ壁を置いていき
ありえない状態になったら前に戻って別のパターンを調べます。（どちらかが壁の部分での分岐）
矛盾なく最後まで全部埋まったら同じ数字同士が繋がっているかチェック。
違う数字が繋がっていたらまた前に戻って別パターンを調べます。
これが基本的なやりかたです。

38 ：

ラインをくねらせる方法に比べると一次元的にチェックができるので
早く解析できるのですが、それでも時間がかかるので途中で色々なチェックを入れて
解析スピードを上げています。
例１：
→↓
←←
のようにコの字型にラインが曲がるのはありえないので
壁がこういう状態になったら戻ってやり直し。
例２：数字マスの壁を決定する時、上か左が開いていたら
その時点で繋がっている先の数字を調べてダメならやり直す。
などなどです。

39 ：

>>37
ナンリンソルバーとはすごいね
ところで、そのプログラムって、
すべてのマス目を線が通る解を全て出力する
もんと思っていい？

40 ：

>39
その通りです。
そして、プログラムをちょっと追加してやれば短絡解のチェックもできます。
数字の入ってないマスで上と左の壁数が
　２の場合、右と下の壁は０か２。
としてやれば線の通っていないマス目がある場合も探し出せます。
ただし、これをやると一気に計算時間が増えます。それを減らすのが現在の課題。

41 ：

>>40
空白のマス目全部を線が通る解を求めるなら、
例えば、盤面の隅なんかは線の通り方がかなり限定されるから
探索はある程度速いと思うけど、
短絡解だと限定できないから膨大な時間かからない？
自分は、短絡解まで出力するソルバーを、昔作ろうとして挫折したんだけどさw

42 ：

>>40
計算時間が一気に増えるってのは、その状況で壁数０としたときに矛盾（既にどうやってもつなぐことができない）
していることを判定できていないから、じゃないかな。
例えば
http://pc5.2ch.net/test/read.cgi/gamedev/1088809456/67
この左上で０を入れたときとか。それがさらに複雑になったものとか。
結果、後になって（それも相当に分岐して）から矛盾に気づく、と。

43 ：

>>42
ありがとう
そっちのリンク先読ませてもらった。
短絡解ありの問題は時間かかるけど、
解がユニークな問題は　１０×１０ くらいまではかなり速く解けるんだ。
いや、それにしてもすごいわ

44 ：

おおぅ、元スレばれたか。今ではもっと速くなってるよ。日々これ進化。
短絡解を探さないなら15*15でも即答だ。
短絡解チェックありでも10*10なら最大30秒に。
短絡解チェックありで15*15だと３０分以上かかるからまだまだだけどな。

45 ：

http://www8.plala.or.jp/ara3/puz/ac/1209.gif
これで短絡解も調べてどれくらいですか?

46 ：

２分１４秒。そこのはちょうどチェックに使ってたところ。
12*12は、６番で１２分１３秒かかった以外は多くても４分ってとこだった。
そろそろスピードアップ方法が煮詰まってきた感じ。
今日はこれまで。おやすみ〜。

47 ：

ダウトだ。短絡解を見つけられない場合が発生。
二個ある同じ数字を区別して無かったのでチェックのスルーが発生した。
今から組みなおします。
ところで勘違いされないように書いておくけど、短絡解チェックの場合に時間がかかるのは
短絡の解答が見つかるまでに時間がかかるという理由以外に。
　短絡解が無い場合は、最後まで全部チェックしきらなくてはいけない
からという理由があったりします。全部チェックして、これは短絡解の無い正当な面ですよと
証明できなくちゃいけないからなぁ。

48 ：

短絡解の原因発見。数字の区別じゃなかった。
しかも原因取り除いたらなぜか>45のが１分16秒に早まったよ。
ま、結果オーライｗ

49 ：

何かアルゴリズムの肝的な部分を、ソース引用最小限で
お話してくれ

50 ：

今週は夜勤なので昼にカキコ。
肝ったってどこが肝なのかいまいちわからんので概略から。
１マスの情報は右壁の有無と下壁の有無を01で持っています。
上の壁と左の壁は隣のマスの情報からもらいます。
上と左の壁情報から右と下の壁を決めます。やり方は上の通り。
□□□□ →１　それを一番上の左端から右へ向かって決定していき
□□□□ →２　一行埋まったら一つ下の行の左端から繰り返します。
□□□□ →３　パターンが合わなかったら分岐のあるところまで戻ってやり直し。
□□□□ →４　右下まで埋めきったら数字の繋がりをチェック。

51 ：

で、書いてて思ったけど一番の肝は時間短縮のダメ出しかな？
いかにしてありえないパターンを排除して短縮させるかってとこ。
最初に加えたのはコの字の禁止。上に書いたように
→↓
←←
となるパターンは右上と右下で壁がカタカナのコの形になって
線を引く時にはありえない。これを上下左右の向きそれぞれにチェック。
壁が ＿| の形に決まったら上のマスと左のマスを調べて |＿＿| になってたり
￣|
＿| になってたらＮＧで戻ります。￣| では左マスで |￣￣| を調べ、|＿では上マスの
|￣
|＿ を調べます。

52 ：

次に加えたのが途中でのチェック。数字のあるマスで上か左が開いていたら
塗りつぶしプログラムの要領で先端を調べて違う数字と繋がっていたらＮＧ。
ただ、検索範囲外まで調べてはいけないので下図の□から出た場合は
数字不明として仮にＯＫとしておきます。
□□□□
□□３
ここまで加えたチェックでも、短絡を探さないなら15*15で即答できます。
でも、壁マスあり条件の短絡を探すとなると7*7程度が限界です。

53 ：

そこで数字先をチェックする時に、ありえないパターンをＮＧとすることで
時間短縮することにしてみました。
例えば
４３２１
５　９10
６７８
のようにラインが回る場合はダメなので、壁の向こうにすでに通った跡があればＮＧです。
１２
■３
５４　のように壁越しの無駄な遠回りもＮＧなので、壁マスの向こうもチェックします。
このＮＧチェックを数字が書かれて無いマスにも適用し、上か左が開いていたら
調べるようにさせたところかなりの時間短縮ができました。

54 ：

そして壁が ＿| の状態なら上と左の先にある数字もチェックし
違う数字同士がむすばれていたらＮＧ。
続いて壁が ＿| の状態で、上を調べていったら左にたどり着くような
空ループになった状態もＮＧとしました。
このせいで探索回数の数字の伸びは遅くなったものの
より短い時間で解答を得ることができました。

55 ：

ところがまだまだ解析は遅い。なぜだろうと解析中の盤面を観察していると
無駄なチェックが多いのを発見。
１ □□■　例えばこの盤面で１の先が右端の下から出るパターンは数通りあります。
■■□■　でも上がどんなパターンでも、下の出口は同じです。１が右下から出るパターンは
■■□□　一回チェックしてＮＧが出れば、後はどんなパターンでもＮＧ確定です。
　 　 　 ↓
これはいくらなんでも無駄なので、マスを改行する時に下の壁のパターン＆壁が無い場合の
行き着く先の数字を調べて記憶し、前と同じパターンが出てきたらＮＧとします。
上の例なら最下段の改行で0001と記憶しておき、ＮＧで戻ってきて上のパターンを変え、
再度改行する時に、また同じ0001が出たら下を調べるまでもなくＮＧです。
あまり記憶数を増やすと逆にそれを調べるのに遅くなるので、500パターン程度の記憶にして
試したところ、劇的に速度が向上しました。これで10*10の探索が30秒以内に。
とまぁ、とりあえず入れてるチェックはこんなとこです。
ですが、15*15全チェックだと2時間やってもまだ序盤なので、もっと他にいい方法が無いか研究中。
今日はこんなとこでまた。

56 ：

シンプルなアルゴリズムでスパっと、という訳には行かないなあ

57 ：

ニコリなんかの数理系のパズルでナンリンだけは、
現実的な時間で、複数解チェックのできるプログラムがないと思う。

58 ：

それができると、PCBとかLSIとかのパターン作成に
応用が効くのに
あっちも力任せの世界

59 ：

もし効率的にできないとしても、確率的なアルゴリズムだとか、
局所的に短絡がないことを示すとか、いろんなアプローチがあると思う。

60 ：

>58
逆にＡ〜Ｅ同士を繋ぐ線の距離と曲げ回数を同じにしろ
っていうパズルはどうだろうと前向きに考えたりして。
あ〜時間縮まんねぇ。もう一度ざっぱり組みなおしてみよう。
今度は子プロセスの超入れ子構造無しでチャレンジ。

61 ：

何が大変って、普通に解けるけど短絡解もある面、というのを探すのが大変。
うっかりではできちゃうけど、作ろうと思って作れるもんじゃないからなぁ。
過去のニコリさばくりまくっちゃったよ。

62 ：

めちゃくちゃ遠回りする経路をいっぱい盛り込めば簡単に短絡するよ。
あと、チェッカは稠密解がなくてもいいなら適当に数字を一個減らせば別解の山。

63 ：

なるほど、数を減らして短絡解ってのはやってたけど遠回りはやってなかった。
考えてみれば普通に解けるかどうかだけは即チェックできるんだから
数字をちょっとずつ移動させながらチェックしていけばいいんだな。サンクス。
あと、昨日思いついたんだけど、２方向だけ決まっている状態だと、残り二方向は
まだ壁不確定な時があるけど、三方向決まっていれば残り一方向は絶対確定なんだよな。
つまり、壁を確定させるのを二行目からやっていけば、一番上の行は確定されるんだよな。
□□□□　これでＡを仮決定させる、上のマスは必ず確定。これを右へ伸ばしていく。
Ａ.□□□　仮の状態は２から３に増えるけど、仮定で進めていく行は半分になる。
10*10ならマス100。今までの一行２択方式で考えると最下段は自動決定として
2＾90なので、約1.2*10＾27通り。ゼロが27個つく。
この２行３択方式で考えると、3＾50で約7.2*10＾23。ゼロが23個。
超大雑把に見積もっても1000倍の差があるな。
15*15なら1.6*10＾63と、1.3*10＾50でゼロが13個分の差。
１から組みなおしが必要だから時間がかかるけどやってみる価値はあるかも。

64 ：

ます目の決定の順序を動的に変化させると結構速くなりますよ。

65 ：

└┘ 無条件で無駄。
└─┘└──┘ 間に初期配置の数字がなければ無駄。
間が3以上の└…┘は調べる場所が広くて少し大変。
落としどころは└──┘くらいかなあ。

66 ：

動的変化はどっちを先に埋めれば速くなるかの把握が･･･
斜めに埋めていくような探索も考えたけど、どう考えても逆に遅くなるしなぁ。
└─┘└──┘ のチェックは
□□□□　の１の先をチェックする時の帰りに、壁向こうに通った番号が無いかを
□■■□　入れ子構造でチェックしているので、壁で直線ショートカットできる
□■■１　パターンは全部チェックしてますです。
今日は子プロセスの超入れ子構造無しで１から組み立ててみたけど
逆に5％ほど遅くなっちゃったよ(´・ω・`)ｼｮﾎﾞｰﾝ
今度は２段三方向での方式にチャレンジしてみる。

67 ：

ふと思い直し、子プロ無しでできるようになったクイックバック方式を
試したところ、>>45のが51秒に。
１ □■■　やり方は、例えば左の図で３をチェックしてNG判定した時に戻る場合は
■□■■　一度左に戻って、さらに改行して戻って右端につき、さらに左へとなりますが
■３ 　　　　この時、途中で分岐できる部分があったら、その分岐から再度進み始めます。
分岐部分で形を変え、また３の位置に進んでも、３での繋がりは同じなので結局NGです。
そこで、こういう場合には３の一つ上の場所まで無条件でバックするようにしてやれば
余計な探索を減らすことができます。このおかげで探索時間が大幅に減らせるように。
もう無理かと思ってたけど、まだまだ縮められるようです。

68 ：

用語が不正確でわかりにくいです。
もう少し詳しく説明して頂けるとありがたい。

69 ：

ズレ無しで枠線＆数字を描くのはちょっと時間かかるんでこれでもやってお待ちくだされ。
ttp://gamdev.org/up/img/1120.lzh
マウスで１から数字を置いて実行させるだけ。置いた数字は移動もできます。

70 ：

添付されていた例題が気になったので。
......1............6
.2..........3.......
....................
..........6......5..
...7................
......5.4......9....
..1................2
.....9....8.........
.3................7.
.......4.....8......

71 ：

いっぱい短絡しておかしいなあと思ったら2桁ごとの区切りでしたか。
線じゃなくて壁でわけると、盤面がフィルオミノっぽくて面白いですねえ。

72 ：

ダメです、２段三方向、まったく変わりません。考えてみれば
２
１　の順でマスを決定させるのって、上下を入れ換えてもパターン数同じじゃないか。
さらには、横に１２と並べるのとも同じじゃないか。ぐはぁ、無駄だったぁ！
発展させて考えると、短絡解探索の全検索は、マスの決定順序をどう変えても
パターン数は変わらないということになるな。途中チェックでなるべく速くダメパターンを消せるか？
のほうが重要だということになる。ダメパターンのチェックがしやすいような順番ならＯＫ
ということにもなるけど、今のところ今の一列ごとに改行方法が一番早そうだし。

73 ：

>71
はいそうです。テキストだけ見るとちょっと驚くと思います。
でも、１〜99の数字を使えるようにするための処置ですんで。

74 ：

探索の順序について。
例えば、
+++12345+
+++++++++
+++++++++
となってるとすると、
+++12345+
++++234++
+++++3+++
と決まります。
順番に探索するより早く矛盾を導ける可能性があります。

75 ：

クイックバック方式の説明。
右から左端へ順々に決めて改行していき、３の部分まで決めてこうなった場合。
┼─┼─┼─┼
│１ │２ │　 │
┼┃┼┃┼─┼　　一度戻ってやり直すのですが、この場合、２の下にある分岐から
│┃│┗━┓│　　再度やり直すことになります。
┼┃┼─┼┃┼
│３ │
┼─┼
┼─┼─┼─┼　　そうすると◎の所がこう変化してまた前進することになり
│１ │２ │　 │　　１と３の関係は変わらないので無駄な探索になります。
┼┃┼┃┼─┼
│┃│◎│
┼　 ┼┃┼　 ┼
│３ │
┼─┼
┼─┼─┼─┼　なので、探索時につけた番号を記憶しておき
│１ｆ│２ │　 │　その番号のマスがでるまで何があろうと
┼┃┼┃┼─┼　ひたすらバックするというのがクイックバック方式です。
│　ｆ│┗━┓│
┼┃┼─┼┃┼
│３ｆ│
┼─┼

76 ：

┼─┼─┼─┼　この場合、スタート地点以外の、ｆがついたところまでバックするので
│１ｆ│２ │　 │　３の上のマスまで戻り、余計な探索を減らせることになります。
┼┃┼─┼─┼　
│┗━　 │　 │
┼　 ┼─┼─┼　ちょっとわかりにくい例図ですいません。
│３ｆ│
┼─┼

77 ：

そして今日の新たな進歩。>>55のパターンチェックを廃止しました。
一回チェックするごとに500回ほどループが入り、非常に遅くなるので撤去。
変わりに　複数ありえるパターンの場合には最後のパターン以外は却下に
１ ■■■　例えば>55にあったパターンなら、一番初めに調べる配置はこうで
□■■■　
□□□□　
１ □□□　一番最後に調べる配置はこうなります。これを利用して
■■■□　
■■■□
□■　盤面に、この形が出るようなパターンはＮＧとしました。　
□□　そうすれば上の場合なら一番最後のパターン以外はＮＧです。
□□　そして右上から左下へ伸びる場合も考慮し、このパターンもＮＧに
□■
このおかげで、>45のが８秒875にまで短縮しました。（ペン４の2.4Ｇhz）
なんだか目標の15*15の短絡チェックにだいぶ近づいてきた気がします。

78 ：

>75
助言サンクス。でも、ナンバーリンクの場合そういう類の配置のパターンが出てくる頻度は
かなり低いのであまり有効ではないかと。でも、ぬりかべならかなり効果のありそうな方法だ。

79 ：

番号違った>74氏すまぬ。

80 ：

>77から微妙に進歩。
「最後のパターン以外はNG」なのを「最初のパターン以外はNG」に。これで少し短くなった。
そして、この最初パターン限定方式を追加したことにより、>53の遠回りパターンが
２ １
３ ■　に類似した状態にしか、ほとんどありえなくなったので
４ ５　 壁越しﾁｪｯｸは上下方向のみに。しかも上から調べれるのと下から調べるのは
　　　　同じだというのに気がついたので、上方向のみのチェックにして更に短縮。
これで>45が６秒625に。

81 ：

一度詳しくホムペで絵つきでがっつり解説した方がいいんだろうけど
その労力を短縮につぎ込んだ方が効率がいいだろうしなぁ、と思ってしまう。
目標は15*15の短絡なしチェックを１時間以内に、だから
そこまで完成したらプロジェクトX風に解説してみたいねｗ
あれからの進歩。上と左の先端の変な繋がりチェックを＿|のマス目のみにした。
右と下のみに進む繋がりは記憶しておいてすぐチェックできるように。
その他細かくIF文の数を減らしたりバグを取ったり。
これで>45が04.391に。>77の頃から見ると半分以下になったな。
それでも15*15は手に負えないよ。単純に考えるとマス目が10個増えると
2の10乗で1024倍時間が増える。約1000倍としたら20個で約1000000倍。
12*12から15*15はマスが111個増えるんだよね…

82 ：

こっちに書くの忘れてた。今回の成果。
ttp://gamdev.org/up/img/1180.lzh

83 ：

今日の成果。目標に届いたかもしれない。
今、古いニコリひっくり返して入力してチェックしてるけど
一番時間がかかった面で３０分。あとは数分といった程度で確認終了できるようになった。
今回はロジックではなく、休憩のさせかたを変更。
これまでのは一回探索するごとにほんのちょっぴり休み（sleep(0)）を入れていたんだが
それを5000回に一回しっかり休ませる（sleep(1)）ようにしたら、劇的に速く＆CPU負荷が減った。
今日の成果と例の>45の履歴を確認してみる。
8/23　２分１４秒
8/23　１分１６秒
8/29　５１秒
9/04　８秒875
9/05　６秒625
9/06　４秒391
9/08　２秒046　＊今回
なんつーか自分で言うのもなんだけどすげぇ。最初の遅さがもう何年も前のようだ。
ただ、5000回固定だと遅いCPUには高負荷になってしまうので、使う側で指定できるようにします。

84 ：

sleep すると OS のスケジューラの周期分くらいは最低待たされるからねえ。
それに関数呼び出しコストもばかにならないし。usleep 使うてのはどうでしょう。
これだけ速くなったら 15x15 もいけるんでないの?
手元のソルバでも 45 のが 5 秒くらいですが、
15x15 が(ものによっては)数十分から一時間くらいで解けますよ。

85 ：

あ、一番かかったってのは15x15ですか。

86 ：

出社前に気がついてよかった。>85　その通りです。
15*15が最大３０分、通常数分です。
ちなみにCPU100%でぶん回すとさらに時間が短くなります。
usleepは帰ってから調べてみます。サンクス。

87 ：

ベンチマーク問題。
...............
.......1.......
.....2...3.....
...4...5...6...
.....7...8.....
.......7.......
.....6...2.....
.9.5.......3.8.
.....b...a.....
.......9.......
.....c...d.....
...a...b...c...
.....1...d.....
.......4.......
...............
470519069ノード、607.86秒 @ P4 2.8GHz でした。

88 ：

usleepを調べてみたり試してみたりしましたが、うちのDELでは扱えないようでした。
それでもめげずにぅぉりゃっ！更に高速化＆便利に！
ttp://www.interq.or.jp/moonstone/person/NLsolv05.lzh
テキスト読込機能を付けました。コピー＆ペーストで>87のような面が読み込めます。
オプション機能を付けました。探索何回ごとに表示させるか指定できます。
コ・マ・オ・ク・リ・モ・デ・キ・マ・ス・ヨ
シャア専用モードをつけましたw　通常の約３倍で探索します。CPUの発熱に注意。

89 ：

ナンバーリンクの解法プログラム、
↓の本にも載っているみたいだけど、これはどうなん？
ttp://www.pro.or.jp/~fuji/computerbooks/algorithm/nanopico.bit.html

90 ：

いや、どうなんって言われても。その本、見たこと無いです（＾＾；
発売が十年前か。手に入れるのは厳しいな･･･

91 ：

アマゾンで調べたけど、２〜３日で発送ＯＫっぽいぞ。

92 ：

仕事しながらふと考えてた。数字を入れる場所を数箇所指定して
後はその場所に総当りで数字を入れて、短絡無しの唯一解が出る面だけを
抽出するソフトはどうだろうか？と。でも、しばらくしてから自己否定。
そんなソフトを作ったら、ソフトを持ってる人が優遇されすぎる。
配置が綺麗なだけの味気ない面ばかりが増えそうだ。
っていうより、それはナンバーリンクの熱的な死ではないか？
まぁ考えすぎっちゃ考えすぎだってのは判ってるけどね。
どっちにしろ今は作るのは止めときます。
半分は自分のため、もう半分はニコリのために作ったんだから
必要なのは短絡解の判定ができるソルバー機能のみでよし。

93 ：

>91
ぅぉ、チェックしてみます。

94 ：

ところで今は左上から一方向にサーチしてるみたいだけど、これ
　　 １ 　 ２
　■→　 ←■
３↓　 　 　 ↓４
５↑　 　 　 ↑６
　■→　 ←■
　　 ７ 　 ８
こういう風に四隅二方向から、１２３４５６７８…の順で１つずつサーチ
したらどうだろう？
もしくは１４８５の四隅一方向からとか、１８の二方向はさみうちとか。

95 ：

今日は酔ってるので一人でこんなの作って笑ってたりする。
1+++++++++
++++++++++
+++4++++++
++++++++++
++++++++++
++++1+++++
++++++++++
++++++++++
+24+++++++
+++++32++3
設置数最少設定。しかも短絡なし。でも目で解けそうだ。
>94　自分も色々考えてみたけど、古い決定部分がいつまでも表に出ていると効率悪いみたい。
ぐるーっと回って、などのやり方は、１の次の段で失敗がわかった時に
同じように、またぐるーっと手を戻さないといけないし。
なるべく表面積を少なくする＝仮決定部分がすぐ埋まる＝失敗した時にすぐ判明、ってことかな？

96 ：

>>95
「このまま進めたら破綻」ってのを極力早期に発見できないかな、と。
＜多方向から探索

97 ：

このままでは漏れの人生破綻

98 ：

短絡ありのテスト問題。
...............
.....a...2.....
..b....7....3..
......8........
...34.....5....
........b......
.a...........1.
...9.......5...
.c...........6.
......4........
....8.....76...
........1......
..9....2....c..
.....d...d.....
...............
30.58 sec.

99 ：

手怪我した。しばらく進行遅れる。タイプし難い。
>96
うん、俺もいかにして「このまま進めたら破綻」を速めにできるか考えたけど
ばらさないでまとめた方が良いみたいなんだよね。
例えば四隅の簡易版として上下２分割で上下交互に進めていくとした場合
下で破綻が出たら上もついでに戻らないといけないようになるし。
だったら探索をまとめて中央付近を速く埋めた方が破綻が少なくてすむ。
線の重要度は真ん中が高い。真ん中が決まらんと相手番号が未定のケースが増えるし。

100read 1read

1read 100read

TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▲

得意なペンシルパズル苦手なペンシルパズル (224)
得意なペンシルパズル苦手なペンシルパズル (224)
ジグソーパズル　5ピース目 (772)
得意なペンシルパズル苦手なペンシルパズル (224)
▲▼部屋に飾ってるパズル▼▲ (226)
パズル板雑談スレッド・ふたことめ (890)
--log9.info------------------
起業しようぜ４ (431)
プログラマーはアニメをみよう! ５クール (501)
◆個人事業主(フリーランサー)専門スレ38本目◆ (621)
アセンブラ言語やマシン語は覚えておくべきですか？ (351)
テストデータに「test」とか「てst」とかもうやめろ (371)
TWO == イラッつとするコーディングスタイル (925)
プログラマーをマジギレさせる言動 2 (287)
基本情報技術者試験 (431)
VB6システム、未だリプレイスせず拡張中 (232)
仕様書、設計書について (947)
フリー/SOHOプログラマの確定申告2010/2011 (562)
できるプログラマーはキーボードを静かに使う：２ (787)
プログラミング初心者あるある (253)
N88 BASIC (706)
シェアウェア作者の愚痴 29 (808)
UMLなんていらない (393)
--log55.com------------------
★2ch.scは何故失敗したのか
★クロール批判要望スレ
★削ジェンヌに文句ある人集合
★迷惑行為報告担当 - 小さな親切募集中 2
★2ch.scへの要望スレ Part3
★かっこう観測所
★スレ立て人キャップ
★2ch.scニュース系板観測所