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

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

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

1 :名無しさん@お腹いっぱい。:04/08/14 13:50 ID:7ki1y5sx

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

2 :トコノイタンハ ◆WfuO0J/v7s :04/08/14 13:58 ID:hTx1p71T
2

3 :名無しさん@お腹いっぱい。:04/08/14 14:01 ID:UHcoHh3/
3 PRINT "スリーセブンの3ゲット"

4 :名無しさん@お腹いっぱい。:04/08/14 14:03 ID:7ki1y5sx
15パズル、倉庫番、ナンプレ、お絵かきロジック、ライツアウト
ttp://www.ic-net.or.jp/home/takaken/


5 :名無しさん@お腹いっぱい。:04/08/14 14:06 ID:7ki1y5sx
覆面算
ttp://bach.istc.kobe-u.ac.jp/puzzle/

6 :名無しさん@お腹いっぱい。:04/08/14 14:10 ID:7ki1y5sx
数独、Nクイーン、カナオレ、ましゅ
ttp://rogiken.org/puzz/program/index.html

7 :名無しさん@お腹いっぱい。:04/08/14 14:26 ID:7ki1y5sx
ピクロス
ttp://www.alpha-net.ne.jp/users2/cult/java/

8 :名無しさん@お腹いっぱい。:04/08/14 14:29 ID:7ki1y5sx
ナンプレ
ttp://be__.at.infoseek.co.jp/java/nps/

9 :名無しさん@お腹いっぱい。:04/08/14 14:41 ID:7ki1y5sx
で、今、自分が挑戦してるのがナンバーリンクのソルバーだったりする。
15*15でも即答できるようになったが、問題は別解探索。
数字が通らないマスもあるのを前提にすると、10*10でも解けなくなる。
関西解探索ありの限度は、今は7*7ぐらいだ。

10 :1:04/08/16 02:44 ID:0E+z1gMx
バグデタ━━━(゚∀゚)━━━!!!!!

計算順序でのものなので1から作り直します。
関西チェックは10*10なら30分ぐらいで発見できるレベル。まだまだだな。

11 :名無しさん@お腹いっぱい。:04/08/16 02:59 ID:C3xr2C0e
ガンガレ!

12 :1:04/08/16 21:51 ID:wrHS2bqC
頑張ってるー。今気がついたんだけど7×7のマスが10×10になると
面積は倍以上になるんだな。7×7で49だけど10×10は100マス。

どうりでここらへんから急に遅くなるはずだ。探索数から考えると50マス増えたとして
2の50乗倍に増えるということになるし。こりゃやっかいなNP問題に手を出したかも。

13 :名無しさん@お腹いっぱい。:04/08/16 22:44 ID:C3xr2C0e
自分も作ろうと思ったのだが、
>>1はなにで作ってる?

14 :1:04/08/16 23:42 ID:wrHS2bqC
Delphiだよ。無料でWebにもそこそこ情報があるからこれにした。

15 :名無しさん@お腹いっぱい。:04/08/17 00:06 ID:bMR+h5U6
サンクス
ちょっと勉強してみることにするよ。

16 :名無しさん@お腹いっぱい。:04/08/17 01:09 ID:bMR+h5U6
インスコ完了ヽ(´ー`)ノ
今日は眠いから明日にでものんびりいくとするよ。

17 :名無しさん@お腹いっぱい。:04/08/17 01:47 ID:ZLlmZOVP
>>1
大変だなぁDelphiなんて。
学生だったらマイクロソフトがたまにやるイベントとかで
.net配ったりするからそれをもらったほうがいいかもね。

18 :1:04/08/17 11:18 ID:sSAf5Cli
>17
その.NETはCです?JAVAです?VBです?
言語選ぶ時にどれにしようか色々悩んだけどね。
2CHやその他で色々調べた結果これになったよ。

>16
ガンガレー。Cより楽だしVBみたいに外部DLLがいらないから
ちょっとしたものを作って配布するのに便利だぞ。

19 :名無しさん@お腹いっぱい。:04/08/17 11:31 ID:gHKgIX0b
JavaScriptでスライドパズルなら作ったことがある、
解けるものと解けないものがあるのには驚いたな。

20 :1:04/08/17 19:09 ID:sSAf5Cli
今日の成果ー。見つけるまでの時間を測定するようにした。

現在、10*10で短絡解ありをチェックして平均1分半で見つけるように。
ようやく進歩が見えてきた感がある。

だが、10*10の短絡が無い盤面を短絡チェックしようとすると
無いと判明するまで6分30秒。2.4Ghzでこれではまだまだっす。

>19 トポロジーというやつですな。

21 :名無しさん@お腹いっぱい。:04/08/17 21:07 ID:bMR+h5U6
とりあえず慣れるためにボンバーパズル4×4を作成。
問題自動作成と最低限の機能を持ったものが3時間ほどで完成ヽ(´ー`)ノ

ちょっと慣れたからそろそろ解答プログラム作りに入る予定。
>>4-8にないものを作ろうと思案中。
でも出てないやつって難しいんだろうか・・・_| ̄|○

22 :名無しさん@お腹いっぱい。:04/08/17 21:13 ID:7PtaY1rK
とりあえずプログラムならこの辺も押さえておかんと。特に最初の。

ペントミノ詰・数独・カックロ・四角に切れ・ひとりにしてくれ・美術館・橋かけ
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 :名無しさん@お腹いっぱい。:04/08/17 22:50 ID:bMR+h5U6
>>22
サンクス!
なんか難しそうだけどよく読んで勉強するよ。


24 :名無しさん@お腹いっぱい。:04/08/18 21:24 ID:GTdGmhp7
なんとなく好きなぬりかべにすることに決定。
とりあえず初期段階の1の四方を黒にするのは成功。
ifの入れ子でエラーだしまくったよ・・・・_| ̄|○

25 :名無しさん@お腹いっぱい。:04/08/18 21:32 ID:GTdGmhp7
そして今caseに気づいた自分_| ̄|○


26 :名無しさん@お腹いっぱい。:04/08/18 22:05 ID:0T52XOXR
…1の四方なんてどうでもよいかと。
あと意外とぬりかべは面倒なので注意。

とりあえずその程度の腕だときついんじゃないかなあと思った。
ネタがかぶってもいいので簡単なパズルを練習に作ってみるのがよいかと。

27 :名無しさん@お腹いっぱい。:04/08/18 23:59 ID:GTdGmhp7
やっぱそうか(´・ω・`)
ってことで見た感じ一番スタンダードな数独をやってる。
とりあえず順調にいってる予感。

28 :1:04/08/19 00:59 ID:sPkvX8JF
今日はエディタの進行。数字を置いたりズラしたりできるように。

高速解答の順序もなんとなくやりかたをつかめ始めた気がする。
基本として、枝狩りの時は初期の枝を重視すべし、だな。
やや時間がかかってもいいから、良くあるありえないパターンは
先にはじいておいた方が、大きな面が速く解ける。

ところで、ペントミノなんかの敷き詰め問題の解き方が
どうしても想像つかんのだが。

29 :名無しさん@お腹いっぱい。:04/08/19 08:52 ID:33bkZUEr
>>28
ペントミノなら藤原氏のところにプログラムがあるよ。
左上から順に置けるところにピースを置いていくだけで、
今の計算機なら数秒で前階が出る。

30 :名無しさん@お腹いっぱい。:04/08/19 18:26 ID:BCERUg56
漏れはパズルを甘く見すぎてたようだ_| ̄|○
けっこう難しいな・・・・・
とりあえずじっくりいくか・・・

31 :1:04/08/19 23:50 ID:JI6hxVk+
>>29
なぜそんなやりかたでいいのか?という理由がわからんのですよ。
とてもいいかげんそうで穴があるように見えてしまう。
でも解けるらしい。なんで?

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

33 :1:04/08/20 12:25 ID:B31IcJ3d
>32
サンクス。やっと感覚的に理解できたよ。
再帰はわかってたけど、それをどう応用するのかがわからんかった。

パズル解答のプログラミングって、再帰は重要だよな。
初心者はまず、でこぼこのマス目を塗りつぶせるようなプログラムを作るべしと思う。


34 :1:04/08/20 23:38 ID:7KMUAawE
今日のナンリンソルバー成果ー。ファイルのロード&セーブ機能をつけた。
これでニコリのいろんな面を確かめられる。
今までテキストのコピペでやりくりしてたから楽になるぜ。

高速化も実行。チェックスピードは遅くなったものの全体的な解析力は向上。
10*10の全短絡解析を数秒〜11分で。数字が少ないと一気に長くなるな。
あと、物は試しに11*11の面をチェックしてみたら・・・1時間近くかかったよ_| ̄|○

これまで色々ブレイクスルーな方法で時間短縮してきたけど
もう一皮向けないとダメってことか。厳しいな。

35 :□7×7=4□□:04/08/21 23:16 ID:8XTY9xwt
ソースや理論をageて皆でたたき台にすればいいんだがな。
ペンシルパズルはオープンソースモデルが向いているだろう。

36 :1:04/08/22 12:01 ID:iRgypLga
新たなるブレイクスルー発見。
10*10の短絡チェックを多くても2分以内で解析できるように。
11*11も3分程度で完了。でも15*15までにはまだまだ。

そろそろ遅くなってきたから、計算そのものの高速チューニングを検討してみる。

37 :進可 ◆Sinka1my5k :04/08/22 12:23 ID:iRgypLga
そろそろハンドルつけます。あと、解析方法も晒してなかったから解説。

数字同士を繋げている線でなく、線が通過していない壁に注目しました。
ラインが通っているマスは上下左右のうち、2方がライン、2方が壁になります。
ある一つのマスがあるとして、その上と左を調べます。
上と左の壁数が
 2つの場合、右と下は壁は0です。
 1つの場合は、右か下どちらか一つが壁です。
 0の場合は、右と下は両方とも壁です。
数字の入っているマスの場合は1方がラインで、残り三方は壁です。そして
上と左の壁数が
 2つの場合は、右か下どちらか一つが壁です。
 1つの場合は、右と下は両方とも壁です。
 0の場合はありえません。

これを、左上から右に向けて1マスずつ壁を置いていき
ありえない状態になったら前に戻って別のパターンを調べます。(どちらかが壁の部分での分岐)
矛盾なく最後まで全部埋まったら同じ数字同士が繋がっているかチェック。
違う数字が繋がっていたらまた前に戻って別パターンを調べます。
これが基本的なやりかたです。

38 :進可 ◆Sinka1my5k :04/08/22 12:36 ID:iRgypLga
ラインをくねらせる方法に比べると一次元的にチェックができるので
早く解析できるのですが、それでも時間がかかるので途中で色々なチェックを入れて
解析スピードを上げています。

例1:
→↓
←←
のようにコの字型にラインが曲がるのはありえないので
壁がこういう状態になったら戻ってやり直し。

例2:数字マスの壁を決定する時、上か左が開いていたら
その時点で繋がっている先の数字を調べてダメならやり直す。

などなどです。

39 :□7×7=4□□:04/08/22 15:50 ID:dg606h3B
>>37
ナンリンソルバーとはすごいね
ところで、そのプログラムって、
すべてのマス目を線が通る解を全て出力する
もんと思っていい?

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

41 :□7×7=4□□:04/08/22 17:48 ID:dg606h3B
>>40
空白のマス目全部を線が通る解を求めるなら、
例えば、盤面の隅なんかは線の通り方がかなり限定されるから
探索はある程度速いと思うけど、
短絡解だと限定できないから膨大な時間かからない?

自分は、短絡解まで出力するソルバーを、昔作ろうとして挫折したんだけどさw

42 :□7×7=4□□:04/08/22 18:22 ID:JJqe7PwO
>>40
計算時間が一気に増えるってのは、その状況で壁数0としたときに矛盾(既にどうやってもつなぐことができない)
していることを判定できていないから、じゃないかな。

例えば
http://pc5.2ch.net/test/read.cgi/gamedev/1088809456/67
この左上で0を入れたときとか。それがさらに複雑になったものとか。

結果、後になって(それも相当に分岐して)から矛盾に気づく、と。

43 :□7×7=4□□:04/08/22 18:36 ID:dg606h3B
>>42
ありがとう
そっちのリンク先読ませてもらった。
短絡解ありの問題は時間かかるけど、
解がユニークな問題は 10×10 くらいまではかなり速く解けるんだ。
いや、それにしてもすごいわ

44 :進可 ◆Sinka1my5k :04/08/22 19:56 ID:LpwLr/yh
おおぅ、元スレばれたか。今ではもっと速くなってるよ。日々これ進化。
短絡解を探さないなら15*15でも即答だ。
短絡解チェックありでも10*10なら最大30秒に。

短絡解チェックありで15*15だと30分以上かかるからまだまだだけどな。

45 :□7×7=4□□:04/08/22 23:02 ID:aduJYRKA
http://www8.plala.or.jp/ara3/puz/ac/1209.gif
これで短絡解も調べてどれくらいですか?

46 :進可 ◆Sinka1my5k :04/08/23 00:25 ID:VFpFcLPL
2分14秒。そこのはちょうどチェックに使ってたところ。
12*12は、6番で12分13秒かかった以外は多くても4分ってとこだった。

そろそろスピードアップ方法が煮詰まってきた感じ。
今日はこれまで。おやすみ〜。

47 :進可 ◆Sinka1my5k :04/08/23 18:59 ID:5ZbVAss3
ダウトだ。短絡解を見つけられない場合が発生。
二個ある同じ数字を区別して無かったのでチェックのスルーが発生した。
今から組みなおします。

ところで勘違いされないように書いておくけど、短絡解チェックの場合に時間がかかるのは
短絡の解答が見つかるまでに時間がかかるという理由以外に。

 短絡解が無い場合は、最後まで全部チェックしきらなくてはいけない

からという理由があったりします。全部チェックして、これは短絡解の無い正当な面ですよと
証明できなくちゃいけないからなぁ。

48 :進可 ◆Sinka1my5k :04/08/23 20:43 ID:5ZbVAss3
短絡解の原因発見。数字の区別じゃなかった。
しかも原因取り除いたらなぜか>45のが1分16秒に早まったよ。

ま、結果オーライw

49 :□7×7=4□□:04/08/24 01:14 ID:2XGbwLWd
何かアルゴリズムの肝的な部分を、ソース引用最小限で
お話してくれ

50 :進可 ◆Sinka1my5k :04/08/24 12:50 ID:TVfLuhDN
今週は夜勤なので昼にカキコ。
肝ったってどこが肝なのかいまいちわからんので概略から。

1マスの情報は右壁の有無と下壁の有無を01で持っています。
上の壁と左の壁は隣のマスの情報からもらいます。
上と左の壁情報から右と下の壁を決めます。やり方は上の通り。

□□□□ →1 それを一番上の左端から右へ向かって決定していき
□□□□ →2 一行埋まったら一つ下の行の左端から繰り返します。
□□□□ →3 パターンが合わなかったら分岐のあるところまで戻ってやり直し。
□□□□ →4 右下まで埋めきったら数字の繋がりをチェック。

51 :進可 ◆Sinka1my5k :04/08/24 13:00 ID:TVfLuhDN
で、書いてて思ったけど一番の肝は時間短縮のダメ出しかな?
いかにしてありえないパターンを排除して短縮させるかってとこ。

最初に加えたのはコの字の禁止。上に書いたように
→↓
←←
となるパターンは右上と右下で壁がカタカナのコの形になって
線を引く時にはありえない。これを上下左右の向きそれぞれにチェック。
壁が _| の形に決まったら上のマスと左のマスを調べて |__| になってたり
 ̄|
_| になってたらNGで戻ります。 ̄| では左マスで | ̄ ̄| を調べ、|_では上マスの

| ̄
|_ を調べます。

52 :進可 ◆Sinka1my5k :04/08/24 13:11 ID:TVfLuhDN
次に加えたのが途中でのチェック。数字のあるマスで上か左が開いていたら
塗りつぶしプログラムの要領で先端を調べて違う数字と繋がっていたらNG。
ただ、検索範囲外まで調べてはいけないので下図の□から出た場合は
数字不明として仮にOKとしておきます。
□□□□
□□3

ここまで加えたチェックでも、短絡を探さないなら15*15で即答できます。
でも、壁マスあり条件の短絡を探すとなると7*7程度が限界です。

53 :進可 ◆Sinka1my5k :04/08/24 13:19 ID:TVfLuhDN
そこで数字先をチェックする時に、ありえないパターンをNGとすることで
時間短縮することにしてみました。

例えば
4321
5 910
678
のようにラインが回る場合はダメなので、壁の向こうにすでに通った跡があればNGです。

12
■3
54 のように壁越しの無駄な遠回りもNGなので、壁マスの向こうもチェックします。

このNGチェックを数字が書かれて無いマスにも適用し、上か左が開いていたら
調べるようにさせたところかなりの時間短縮ができました。


54 :進可 ◆Sinka1my5k :04/08/24 13:23 ID:TVfLuhDN
そして壁が _| の状態なら上と左の先にある数字もチェックし
違う数字同士がむすばれていたらNG。
続いて壁が _| の状態で、上を調べていったら左にたどり着くような
空ループになった状態もNGとしました。

このせいで探索回数の数字の伸びは遅くなったものの
より短い時間で解答を得ることができました。

55 :進可 ◆Sinka1my5k :04/08/24 13:44 ID:TVfLuhDN
ところがまだまだ解析は遅い。なぜだろうと解析中の盤面を観察していると
無駄なチェックが多いのを発見。

1 □□■ 例えばこの盤面で1の先が右端の下から出るパターンは数通りあります。
■■□■ でも上がどんなパターンでも、下の出口は同じです。1が右下から出るパターンは
■■□□ 一回チェックしてNGが出れば、後はどんなパターンでもNG確定です。
      ↓
これはいくらなんでも無駄なので、マスを改行する時に下の壁のパターン&壁が無い場合の
行き着く先の数字を調べて記憶し、前と同じパターンが出てきたらNGとします。
上の例なら最下段の改行で0001と記憶しておき、NGで戻ってきて上のパターンを変え、
再度改行する時に、また同じ0001が出たら下を調べるまでもなくNGです。

あまり記憶数を増やすと逆にそれを調べるのに遅くなるので、500パターン程度の記憶にして
試したところ、劇的に速度が向上しました。これで10*10の探索が30秒以内に。

とまぁ、とりあえず入れてるチェックはこんなとこです。
ですが、15*15全チェックだと2時間やってもまだ序盤なので、もっと他にいい方法が無いか研究中。
今日はこんなとこでまた。

56 :□7×7=4□□:04/08/24 20:30 ID:2XGbwLWd
シンプルなアルゴリズムでスパっと、という訳には行かないなあ

57 :□7×7=4□□:04/08/25 09:22 ID:uUYwj/rg
ニコリなんかの数理系のパズルでナンリンだけは、
現実的な時間で、複数解チェックのできるプログラムがないと思う。

58 :□7×7=4□□:04/08/25 14:12 ID:yxCUwYJW
それができると、PCBとかLSIとかのパターン作成に
応用が効くのに
あっちも力任せの世界

59 :□7×7=4□□:04/08/26 00:25 ID:LrHJtrvz
もし効率的にできないとしても、確率的なアルゴリズムだとか、
局所的に短絡がないことを示すとか、いろんなアプローチがあると思う。

60 :進可 ◆Sinka1my5k :04/08/26 08:36 ID:6fof0ZUX
>58
逆にA〜E同士を繋ぐ線の距離と曲げ回数を同じにしろ
っていうパズルはどうだろうと前向きに考えたりして。

あ〜時間縮まんねぇ。もう一度ざっぱり組みなおしてみよう。
今度は子プロセスの超入れ子構造無しでチャレンジ。


61 :進可 ◆Sinka1my5k :04/08/26 19:12 ID:eIVv2S6o
何が大変って、普通に解けるけど短絡解もある面、というのを探すのが大変。
うっかりではできちゃうけど、作ろうと思って作れるもんじゃないからなぁ。
過去のニコリさばくりまくっちゃったよ。

62 :□7×7=4□□:04/08/27 00:16 ID:qV5z7eww
めちゃくちゃ遠回りする経路をいっぱい盛り込めば簡単に短絡するよ。
あと、チェッカは稠密解がなくてもいいなら適当に数字を一個減らせば別解の山。

63 :進可 ◆Sinka1my5k :04/08/27 15:02 ID:CVBdA6dk
なるほど、数を減らして短絡解ってのはやってたけど遠回りはやってなかった。
考えてみれば普通に解けるかどうかだけは即チェックできるんだから
数字をちょっとずつ移動させながらチェックしていけばいいんだな。サンクス。

あと、昨日思いついたんだけど、2方向だけ決まっている状態だと、残り二方向は
まだ壁不確定な時があるけど、三方向決まっていれば残り一方向は絶対確定なんだよな。
つまり、壁を確定させるのを二行目からやっていけば、一番上の行は確定されるんだよな。

□□□□ これでAを仮決定させる、上のマスは必ず確定。これを右へ伸ばしていく。
A.□□□ 仮の状態は2から3に増えるけど、仮定で進めていく行は半分になる。

10*10ならマス100。今までの一行2択方式で考えると最下段は自動決定として
2^90なので、約1.2*10^27通り。ゼロが27個つく。
この2行3択方式で考えると、3^50で約7.2*10^23。ゼロが23個。
超大雑把に見積もっても1000倍の差があるな。
15*15なら1.6*10^63と、1.3*10^50でゼロが13個分の差。

1から組みなおしが必要だから時間がかかるけどやってみる価値はあるかも。

64 :□7×7=4□□:04/08/27 16:36 ID:qV5z7eww
ます目の決定の順序を動的に変化させると結構速くなりますよ。

65 :□7×7=4□□:04/08/28 00:13 ID:rAS6LKU5
└┘ 無条件で無駄。
└─┘└──┘ 間に初期配置の数字がなければ無駄。
間が3以上の└…┘は調べる場所が広くて少し大変。
落としどころは└──┘くらいかなあ。

66 :進可 ◆Sinka1my5k :04/08/29 01:50 ID:06INVbNq
動的変化はどっちを先に埋めれば速くなるかの把握が・・・
斜めに埋めていくような探索も考えたけど、どう考えても逆に遅くなるしなぁ。
└─┘└──┘ のチェックは
□□□□ の1の先をチェックする時の帰りに、壁向こうに通った番号が無いかを
□■■□ 入れ子構造でチェックしているので、壁で直線ショートカットできる
□■■1 パターンは全部チェックしてますです。

今日は子プロセスの超入れ子構造無しで1から組み立ててみたけど
逆に5%ほど遅くなっちゃったよ(´・ω・`)ショボーン

今度は2段三方向での方式にチャレンジしてみる。

67 :進可 ◆Sinka1my5k :04/08/29 12:44 ID:06INVbNq
ふと思い直し、子プロ無しでできるようになったクイックバック方式を
試したところ、>>45のが51秒に。

1 □■■ やり方は、例えば左の図で3をチェックしてNG判定した時に戻る場合は
■□■■ 一度左に戻って、さらに改行して戻って右端につき、さらに左へとなりますが
■3     この時、途中で分岐できる部分があったら、その分岐から再度進み始めます。

分岐部分で形を変え、また3の位置に進んでも、3での繋がりは同じなので結局NGです。
そこで、こういう場合には3の一つ上の場所まで無条件でバックするようにしてやれば
余計な探索を減らすことができます。このおかげで探索時間が大幅に減らせるように。
もう無理かと思ってたけど、まだまだ縮められるようです。

68 :□7×7=4□□:04/08/29 13:26 ID:dRWnxd/W
用語が不正確でわかりにくいです。
もう少し詳しく説明して頂けるとありがたい。

69 :進可 ◆Sinka1my5k :04/08/29 16:19 ID:06INVbNq
ズレ無しで枠線&数字を描くのはちょっと時間かかるんでこれでもやってお待ちくだされ。
ttp://gamdev.org/up/img/1120.lzh
マウスで1から数字を置いて実行させるだけ。置いた数字は移動もできます。

70 :□7×7=4□□:04/08/29 17:49 ID:dRWnxd/W
添付されていた例題が気になったので。
......1............6
.2..........3.......
....................
..........6......5..
...7................
......5.4......9....
..1................2
.....9....8.........
.3................7.
.......4.....8......


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

72 :進可 ◆Sinka1my5k :04/09/02 00:12 ID:y5lJ/34E
ダメです、2段三方向、まったく変わりません。考えてみれば


1 の順でマスを決定させるのって、上下を入れ換えてもパターン数同じじゃないか。

さらには、横に12と並べるのとも同じじゃないか。ぐはぁ、無駄だったぁ!

発展させて考えると、短絡解探索の全検索は、マスの決定順序をどう変えても
パターン数は変わらないということになるな。途中チェックでなるべく速くダメパターンを消せるか?
のほうが重要だということになる。ダメパターンのチェックがしやすいような順番ならOK
ということにもなるけど、今のところ今の一列ごとに改行方法が一番早そうだし。

73 :進可 ◆Sinka1my5k :04/09/02 00:15 ID:y5lJ/34E
>71
はいそうです。テキストだけ見るとちょっと驚くと思います。
でも、1〜99の数字を使えるようにするための処置ですんで。

74 :□7×7=4□□:04/09/02 18:48 ID:OvqmM4Sp
探索の順序について。
例えば、
+++12345+
+++++++++
+++++++++
となってるとすると、
+++12345+
++++234++
+++++3+++
と決まります。
順番に探索するより早く矛盾を導ける可能性があります。

75 :進可 ◆Sinka1my5k :04/09/04 00:11 ID:0KrlLWxi
クイックバック方式の説明。
右から左端へ順々に決めて改行していき、3の部分まで決めてこうなった場合。
┼─┼─┼─┼
│1 │2 │  │
┼┃┼┃┼─┼  一度戻ってやり直すのですが、この場合、2の下にある分岐から
│┃│┗━┓│  再度やり直すことになります。
┼┃┼─┼┃┼
│3 │
┼─┼

┼─┼─┼─┼  そうすると◎の所がこう変化してまた前進することになり
│1 │2 │  │  1と3の関係は変わらないので無駄な探索になります。
┼┃┼┃┼─┼
│┃│◎│
┼  ┼┃┼  ┼
│3 │
┼─┼

┼─┼─┼─┼ なので、探索時につけた番号を記憶しておき
│1f│2 │  │ その番号のマスがでるまで何があろうと
┼┃┼┃┼─┼ ひたすらバックするというのがクイックバック方式です。
│ f│┗━┓│
┼┃┼─┼┃┼
│3f│
┼─┼

76 :進可 ◆Sinka1my5k :04/09/04 00:15 ID:0KrlLWxi
┼─┼─┼─┼ この場合、スタート地点以外の、fがついたところまでバックするので
│1f│2 │  │ 3の上のマスまで戻り、余計な探索を減らせることになります。
┼┃┼─┼─┼ 
│┗━  │  │
┼  ┼─┼─┼ ちょっとわかりにくい例図ですいません。
│3f│
┼─┼

77 :進可 ◆Sinka1my5k :04/09/04 00:27 ID:0KrlLWxi
そして今日の新たな進歩。>>55のパターンチェックを廃止しました。
一回チェックするごとに500回ほどループが入り、非常に遅くなるので撤去。
変わりに 複数ありえるパターンの場合には最後のパターン以外は却下に

1 ■■■ 例えば>55にあったパターンなら、一番初めに調べる配置はこうで
□■■■ 
□□□□ 

1 □□□ 一番最後に調べる配置はこうなります。これを利用して
■■■□ 
■■■□

□■ 盤面に、この形が出るようなパターンはNGとしました。 
□□ そうすれば上の場合なら一番最後のパターン以外はNGです。

□□ そして右上から左下へ伸びる場合も考慮し、このパターンもNGに
□■

このおかげで、>45のが8秒875にまで短縮しました。(ペン4の2.4Ghz)
なんだか目標の15*15の短絡チェックにだいぶ近づいてきた気がします。

78 :進可 ◆Sinka1my5k :04/09/04 00:37 ID:0KrlLWxi
>75
助言サンクス。でも、ナンバーリンクの場合そういう類の配置のパターンが出てくる頻度は
かなり低いのであまり有効ではないかと。でも、ぬりかべならかなり効果のありそうな方法だ。


79 :進可 ◆Sinka1my5k :04/09/04 00:38 ID:0KrlLWxi
番号違った>74氏すまぬ。

80 :進可 ◆Sinka1my5k :04/09/05 15:12 ID:Fk/tFxJI
>77から微妙に進歩。
「最後のパターン以外はNG」なのを「最初のパターン以外はNG」に。これで少し短くなった。

そして、この最初パターン限定方式を追加したことにより、>53の遠回りパターンが
2 1
3 ■ に類似した状態にしか、ほとんどありえなくなったので
4 5  壁越しチェックは上下方向のみに。しかも上から調べれるのと下から調べるのは
    同じだというのに気がついたので、上方向のみのチェックにして更に短縮。

これで>45が6秒625に。

81 :進可 ◆Sinka1my5k :04/09/06 18:20 ID:89RaDenK
一度詳しくホムペで絵つきでがっつり解説した方がいいんだろうけど
その労力を短縮につぎ込んだ方が効率がいいだろうしなぁ、と思ってしまう。
目標は15*15の短絡なしチェックを1時間以内に、だから
そこまで完成したらプロジェクトX風に解説してみたいねw

あれからの進歩。上と左の先端の変な繋がりチェックを_|のマス目のみにした。
右と下のみに進む繋がりは記憶しておいてすぐチェックできるように。
その他細かくIF文の数を減らしたりバグを取ったり。

これで>45が04.391に。>77の頃から見ると半分以下になったな。

それでも15*15は手に負えないよ。単純に考えるとマス目が10個増えると
2の10乗で1024倍時間が増える。約1000倍としたら20個で約1000000倍。
12*12から15*15はマスが111個増えるんだよね…

82 :進可 ◆Sinka1my5k :04/09/06 19:18 ID:89RaDenK
こっちに書くの忘れてた。今回の成果。
ttp://gamdev.org/up/img/1180.lzh

83 :進可 ◆Sinka1my5k :04/09/08 18:01 ID:HqKmR/V6
今日の成果。目標に届いたかもしれない。
今、古いニコリひっくり返して入力してチェックしてるけど
一番時間がかかった面で30分。あとは数分といった程度で確認終了できるようになった。

今回はロジックではなく、休憩のさせかたを変更。
これまでのは一回探索するごとにほんのちょっぴり休み(sleep(0))を入れていたんだが
それを5000回に一回しっかり休ませる(sleep(1))ようにしたら、劇的に速く&CPU負荷が減った。

今日の成果と例の>45の履歴を確認してみる。

8/23 2分14秒
8/23 1分16秒
8/29 51秒
9/04 8秒875
9/05 6秒625
9/06 4秒391
9/08 2秒046 *今回

なんつーか自分で言うのもなんだけどすげぇ。最初の遅さがもう何年も前のようだ。
ただ、5000回固定だと遅いCPUには高負荷になってしまうので、使う側で指定できるようにします。


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

85 :□7×7=4□□:04/09/08 19:06 ID:DKXRZSoW
あ、一番かかったってのは15x15ですか。

86 :進可 ◆Sinka1my5k :04/09/08 19:28 ID:HqKmR/V6
出社前に気がついてよかった。>85 その通りです。
15*15が最大30分、通常数分です。
ちなみにCPU100%でぶん回すとさらに時間が短くなります。

usleepは帰ってから調べてみます。サンクス。



87 :□7×7=4□□:04/09/10 00:59 ID:fQj+XFYI
ベンチマーク問題。
...............
.......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 :進可 ◆Sinka1my5k :04/09/10 19:52:10 ID:3WNg0I1N
usleepを調べてみたり試してみたりしましたが、うちのDELでは扱えないようでした。

それでもめげずにぅぉりゃっ!更に高速化&便利に!
ttp://www.interq.or.jp/moonstone/person/NLsolv05.lzh

テキスト読込機能を付けました。コピー&ペーストで>87のような面が読み込めます。
オプション機能を付けました。探索何回ごとに表示させるか指定できます。
コ・マ・オ・ク・リ・モ・デ・キ・マ・ス・ヨ
シャア専用モードをつけましたw 通常の約3倍で探索します。CPUの発熱に注意。


89 :□7×7=4□□:04/09/12 12:13:27 ID:l3AvbC5g
ナンバーリンクの解法プログラム、
↓の本にも載っているみたいだけど、これはどうなん?

ttp://www.pro.or.jp/~fuji/computerbooks/algorithm/nanopico.bit.html

90 :進可 ◆Sinka1my5k :04/09/12 20:18:19 ID:tgDw93+v
いや、どうなんって言われても。その本、見たこと無いです(^^;
発売が十年前か。手に入れるのは厳しいな・・・


91 :□7×7=4□□:04/09/12 20:24:24 ID:9RQYBdkt
アマゾンで調べたけど、2〜3日で発送OKっぽいぞ。

92 :進可 ◆Sinka1my5k :04/09/12 21:16:44 ID:tgDw93+v
仕事しながらふと考えてた。数字を入れる場所を数箇所指定して
後はその場所に総当りで数字を入れて、短絡無しの唯一解が出る面だけを
抽出するソフトはどうだろうか?と。でも、しばらくしてから自己否定。
そんなソフトを作ったら、ソフトを持ってる人が優遇されすぎる。
配置が綺麗なだけの味気ない面ばかりが増えそうだ。

っていうより、それはナンバーリンクの熱的な死ではないか?

まぁ考えすぎっちゃ考えすぎだってのは判ってるけどね。

どっちにしろ今は作るのは止めときます。
半分は自分のため、もう半分はニコリのために作ったんだから
必要なのは短絡解の判定ができるソルバー機能のみでよし。

93 :進可 ◆Sinka1my5k :04/09/12 21:17:33 ID:tgDw93+v
>91
ぅぉ、チェックしてみます。

94 :□7×7=4□□:04/09/13 02:21:27 ID:IYpZiBIP
ところで今は左上から一方向にサーチしてるみたいだけど、これ

   1   2
 ■→  ←■
3↓      ↓4

5↑      ↑6
 ■→  ←■
   7   8

こういう風に四隅二方向から、12345678…の順で1つずつサーチ
したらどうだろう?
もしくは1485の四隅一方向からとか、18の二方向はさみうちとか。

95 :進可 ◆Sinka1my5k :04/09/13 23:39:10 ID:ZUNclhZM
今日は酔ってるので一人でこんなの作って笑ってたりする。
1+++++++++
++++++++++
+++4++++++
++++++++++
++++++++++
++++1+++++
++++++++++
++++++++++
+24+++++++
+++++32++3
設置数最少設定。しかも短絡なし。でも目で解けそうだ。

>94 自分も色々考えてみたけど、古い決定部分がいつまでも表に出ていると効率悪いみたい。
ぐるーっと回って、などのやり方は、1の次の段で失敗がわかった時に
同じように、またぐるーっと手を戻さないといけないし。
なるべく表面積を少なくする=仮決定部分がすぐ埋まる=失敗した時にすぐ判明、ってことかな?


96 :□7×7=4□□:04/09/14 23:44:01 ID:7zIk+Gg8
>>95
「このまま進めたら破綻」ってのを極力早期に発見できないかな、と。
<多方向から探索



97 :□7×7=4□□:04/09/15 07:43:03 ID:fQdZ8MkV
このままでは漏れの人生破綻

98 :□7×7=4□□:04/09/15 18:04:50 ID:jOXkB1zj
短絡ありのテスト問題。
...............
.....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 :進可 ◆Sinka1my5k :04/09/16 06:05:13 ID:rA5uQ9yV
手怪我した。しばらく進行遅れる。タイプし難い。
>96
うん、俺もいかにして「このまま進めたら破綻」を速めにできるか考えたけど
ばらさないでまとめた方が良いみたいなんだよね。
例えば四隅の簡易版として上下2分割で上下交互に進めていくとした場合
下で破綻が出たら上もついでに戻らないといけないようになるし。
だったら探索をまとめて中央付近を速く埋めた方が破綻が少なくてすむ。
線の重要度は真ん中が高い。真ん中が決まらんと相手番号が未定のケースが増えるし。

100 :進可 ◆Sinka1my5k :04/09/16 06:06:56 ID:rA5uQ9yV
ついでに数が超少ない15*15ドゾー。短絡チェックで短絡無し判明に9分です。

+++++++++++++++
++++++++++++25+
++++++++++++3++
+++4+++++++1+++
++++7++++++++++
+++++++++++++++
+++++++++++++++
2++++++++++++++
+++6+++++++++4+
+++++++++++++++
++++++++++++++6
+++++++++++5+++
++++++++++37+++
++++++1++++++++
+++++++++++++++


101 :進可 ◆Sinka1my5k :04/09/16 23:23:34 ID:727dE1V7
正式に発表&ページを作ったよ。
ttp://www.interq.or.jp/moonstone/person/numlink/index.html


102 :□7×7=4□□:04/09/17 22:54:55 ID:+xhT4xyD
数字が少ないのがんばってみたけど、8個で限界だった。
---------------
-3-------------
--7---------5--
------------4--
-------2-------
-------8-----1-
-------6-----2-
---------------
---------------
---------------
-----4---------
---1-----3-5---
--------67-----
--------8------
---------------
8.15 sec.

探索の順序を上下左右に振るのはよくないかもしれないけど、
初めに盤面を見てやりやすそうな方向を決めるというのは有効。
上下左右を反転させるだけで10倍くらい計算量が変わることも。

103 :□7×7=4□□:04/09/18 00:46:56 ID:Nhx/UDJN
あ、いけた。
---------------
-3-------------
--7---------5--
------------4--
---------------
------6------1-
-------------2-
---------------
---------------
---------------
-----4---------
---1-----3-5---
--------27-----
--------6------
---------------
9.55 sec.

104 :□7×7=4□□:04/09/18 19:30:51 ID:cqU95J92
今日発売のCマガを見れ

105 :□7×7=4□□:04/09/18 19:34:43 ID:VjnSR19P
こういうのはbitでよくやってたな

106 :□7×7=4□□:04/09/25 01:34:29 ID:q72DXNuT
面白そうなスレハケーン。
昔VBで数独のソルバー作ったけど、あと一歩で完成ってとこでやめちゃったな。

このスレで、いろんな人で同じパズルのソルバー作って、
処理の早さを競うのも楽しそうだ。

とりあえず、ナンバーリンクってどんなんだったか思い出さないと…。

107 :進可 ◆Sinka1my5k :04/09/26 13:59:51 ID:J1N7yhQF
>処理の早さを競う

まずは人が少ないのをなんとかしないとなぁ。

108 :□7×7=4□□:04/09/26 15:40:03 ID:wDsq1IAb
ム板・ゲ製作技術から連れてくるのがいいんだろうなぁ。
まだパズル板の知名度自体低いだろうし(俺おととい知った)、
ム板・ゲ製作技術でウザがられない程度に宣伝するしか。

ちなみにム板で「パズル」で検索ヒットするスレなし。
ゲ製作技術で検索したら

思考型パズルでも作ってみる(21)
http://pc5.2ch.net/test/read.cgi/gamedev/1088756216/
最終書き込みが7/8で廃墟。

でもう一個が
【作る】倉庫番パズルの自動プログラム 【解く】
http://pc5.2ch.net/test/read.cgi/gamedev/1088809456/
最終…って、こっちが先だったんですか、進可さん。



109 :□7×7=4□□:04/09/26 15:51:40 ID:7fgjOi3S
人がいないのはナンリンが難しいからだと思う

110 :□7×7=4□□:04/09/26 15:56:07 ID:wDsq1IAb
じゃーもっと簡単なやつ…。
お絵かきロジックあたりが簡単そうかな?
数独も、解くために、とある思考が必要…でない問題解くまでなら簡単なんだけど。

ナンリンはナンリンで、平行してればいいだろうし。
人が増えてきたら、ナンリンだけ独立スレたてればよろし。

111 :進可 ◆Sinka1my5k :04/09/26 17:38:41 ID:yRvTzO0c
>108
あいあい、そっちでやってる最中にパズル板ができたんで移りますた。

>109-110
いや別にナンリンにこだわらなくても。ナンリンは自分では一段落したし。
個々で思い思いに違うパズルで作ったりアイデア出したりでいいんじゃないかな?


112 :進可 ◆Sinka1my5k :04/09/26 17:46:19 ID:yRvTzO0c
あと、Cマガ確認。内容は遺伝子的なものによる解答探索だった。
でもこれはあまりパズルを解くのに向いてない感じ。

遺伝子式は「探しつくせない組み合わせの中から一番効果の高いパターンを見つける」だけど
パズルの場合「全ての組み合わせの中から正しいパターンを見つける」だし。
特に、「全パターン中、正しい答えが一つだけなのを確認する」場合に向いてない。

遺伝子式のやり方に向いているのは、ニコリで言うと「スケルトンコンテスト」が最適だろうな。


113 :□7×7=4□□:04/09/26 17:54:58 ID:M1BPF0z6
そこで意表をついて知恵の輪

114 :□7×7=4□□:04/09/26 17:59:18 ID:Qw9eW/G1
104のいう今月のCマガってのは最後から数ページのところにある電脳クラブのことでは。

115 :□7×7=4□□:04/09/26 18:23:08 ID:7fgjOi3S
実は今一番興味を持ってるのが、
GAによるスケルトンコンテストだったりする
応募はしなくても、人間のトップを破れるのか試してみたい

116 :□7×7=4□□:04/09/26 18:34:00 ID:wDsq1IAb
スケルトンコンテストかぁ、俺も興味あるな。
もちろん、作っても応募しないけど。

ところで、速さを競うとしたら同じ言語で作らないと不公平だよな。
俺は多分、C(コンソール)でアルゴリズム固めてから、
本気で公開するならC(windows)にするだろうな。
まあ、それは本当に速さを競うことになったとき考えればいいか。

117 :□7×7=4□□:04/09/26 19:10:36 ID:M1BPF0z6
スケコンいいねえ。
表示された盤面を見て( д ) ゚ ゚ってことになるのか、
それともスケコン上位陣はやっぱり凄いという結論が出るのか。

118 :□7×7=4□□:04/09/26 19:35:38 ID:7fgjOi3S
速さだったらCPUの速度でも変わってくるし
何か試行錯誤の回数をカウントして、それを指標にするのがいいと思う

119 :□7×7=4□□:04/09/26 19:51:27 ID:wDsq1IAb
CPUに関しては、作ったものはそれぞれみんなどっかにUPして、
落として全部自分のところで実行すればOK。
人が多いほど、いろんな環境での結果が見れて良い。
嘘報告しないでね。

120 :進可 ◆Sinka1my5k :04/09/26 21:08:05 ID:yRvTzO0c
>114
( д ) ゚ ゚

121 :□7×7=4□□:04/09/26 21:54:15 ID:WtGZ0CEo
漏れも遺伝子アルゴリズムでスケコンやりたいって思ってたけど、
着手する元気がないんだよねー…。

122 :104:04/09/26 23:07:57 ID:B2NuyMeb
>>114
はい、そういうことです。見た目が一見違うだけでまんまナンバーリンクなもので。

速度勝負は

・GCCかG++でコンパイルできること。
・標準入出力のみ使うこと。

って条件でソースうpするようにすればいいんじゃないかな?
GCCならどんなプラットフォームにもあるし、profileでCPU時間確認もできるし。
試行錯誤カウントはカウントする場所でもめそうな気がする。

123 :□7×7=4□□:04/09/27 01:43:21 ID:AZOHiQw2
それって、Cできない人が参加できなくて可愛そう。

…とはいえ、どれかに統一する必要があるなら、Cがいいだろうな。
使える人は多いだろうし、フリーでコンパイラあるし。
俺も個人的にはCがいい。

124 :□7×7=4□□:04/09/27 01:44:49 ID:AZOHiQw2
あ、書き忘れ。
ソースうpじゃなくてexeでいいでしょ。
速さを競ってるんだから、ソース見られちゃまずいわけで。

125 :□7×7=4□□:04/09/27 01:53:41 ID:FAVJMplI
環境が限定されるのはあまり好ましくないなあ。
どうせ人少なそうだし、言語とか実行環境に制限を加えなくてもいいかと。

実行速度だけじゃなくて、行数とか開発速度とか、そういう点も見てみたい。

126 :□7×7=4□□:04/09/27 01:56:58 ID:AZOHiQw2
実行速度も、行数も、開発速度も言語に依存するからなぁ。
速度はCが有利だし、
行数と開発速度ならVBが有利かな。
言語の壁を越えて、プログラムを競うってのは難しいね。

127 :□7×7=4□□:04/09/27 01:58:54 ID:FAVJMplI
速度は、DelphiとかOCamlとかならCとそう変わらなくない?


128 :□7×7=4□□:04/09/27 02:11:55 ID:hP7/jwJA
ソースを見られるとまずいという弊害が発生するくらいなら
速度なんか競わなくていい

129 :□7×7=4□□:04/09/27 02:28:08 ID:AZOHiQw2
Delphiとかあまり知らないんだよな…
競うのも、結局人が増えなきゃ無理な話か。

もともとの趣向どおり、好きなものを好きなように作って、
偶然同じものを同じ言語で作ってる人がいて、
両者が競ってみようか、って言ったらそのときやればいいのかな。

130 :□7×7=4□□:04/09/27 12:27:00 ID:XYrWe4jW
2ちゃんでexeだとウィルスとかあるとやだしなー。
同じCでもコンパイラで変わっちゃうし。

たかがパズルで公開の弊害どうこうってのもどうかと。
どうせすでにWEBにけっこう存在するんだし。
勝負するなら締切日をきめてそれにあわせてうpすればいい。

131 :□7×7=4□□:04/09/27 23:06:54 ID:AZOHiQw2
締め切り制か、まぁたしかにexeは怖いからねぇ、それが妥当な線か。

今日Cマガ買って来ちゃったよ。
俺パズラー出身だからアルコネと呼んでいるのだが、ナンリンてあれか。
Cマガのは、線が通らないところがあってもよい、ってところがアルコネと違う。

遺伝的〜は確かにスケコンに向いてそうとは思うが、
どの状態とどの状態が、隣接する要素なのかとかしっかり考えないといけないな。


132 :進可 ◆Sinka1my5k :04/09/27 23:44:24 ID:Zw4gUmi/
結局Cマガ買っちゃったよ。俺、DELPHIなのに。

なんかスケコンでいつの間にかどんどん話が進んでるぞ。
ところでよ、スケコンで発表すべき一番重要なものは『答え』ではないのか?



133 :□7×7=4□□:04/09/27 23:58:18 ID:FAVJMplI
そうですね。最適化問題ならソース云々は関係なくて
最適解(近似解)を一つ示せばそれでいいし。

134 :□7×7=4□□:04/09/28 00:00:27 ID:c+cfD1Pe
1.いかによりより答えを出せるか。
2.いかに早く出せるか。

だな。あとは保守性とかもあるけど。
とりあえずスケコンやるなら、とにかく1だけ考えて作ればいいんでない?
それだけで大変そうだし。

GAとかIAとかやると大変だし、ランダムサーチ→山登りくらいで十分かな、と思う。
でもせっかくだからIAでやれば勉強にはなるんだよなぁ。

135 :□7×7=4□□:04/09/28 00:08:05 ID:dUgtREzb
前に何かの論文で見た、いろんな形の複数の四角形を
大きな四角形の中に無駄なく配置する問題のGA的解決
たしか、LSIのフロアープランに使うんだったかな

遺伝子としては、配置する順番だけを情報として持っていて、
ある程度賢い配置アルゴリズムが、与えられた四角を
現状の配置に対して、できるだけ下へ、できるだけ左へ、というような
基本方針で一意に配置場所が決まる方法で配置する

で、遺伝子の交配は順序情報をスワップするんだったか
切り取って後ろに付けるんだったか、そんな感じの単純なの
本来はここらへんが一番肝なんだろうけど

それと似たアプローチでスケコンが解けないかなと構想中
っていうか、とりあえず解いて答えを出力してみせるところまでは
すぐに作れる筈

136 :□7×7=4□□:04/09/29 09:37:40 ID:7uZo8eAr
フロアプランで脱線。
http://www.geocities.co.jp/Berkeley-Labo/6317/seqsqr.htm
これの隙間を埋めるのも面白そうだ。

137 :□7×7=4□□:04/09/29 22:31:29 ID:grgLYnlZ
よく考えたら、GAやIAでスケコンできるわけないや。
スケコンの性質上、「子供を作る」ということができない。まったく思いつかない。

ちょっとじっくり考えて見たけど、
しらみつぶし的なアルゴリズムしか思いつかなかった。
それでもいいから作ってみようかな…。

138 :進可 ◆Sinka1my5k :04/09/29 23:55:50 ID:z4v4NA9V
>137 スケコンの性質上、「子供を作る」ということができない。

マスという細胞壁の中に、単語が入ってきてランダムに今までの単語と繋がったり
字数/ポイントで効率が低いのが出て行ったりするのを想像した。

で、中身が詰まっててポイントの高いのが分裂したり
中身が詰まってる割りにポイントの低いのが死んだりしてるような
原始の海みたいな光景を想像した。


139 :□7×7=4□□:04/09/30 00:11:19 ID:L/LTDnsB
>>137
いや、いけるんじゃない?
一つの盤面から他の盤面に過渡できるように、
その中間に生じる不正な盤面を許容すれば。

たとえば、盤面の表現方法として、各ワードについての
「何行目/何列目の何マス目から入っているか(または不使用か)」
という情報を持つことで盤面を表現したとして、
混血の仕方を、各ワードの位置情報を両親のそれぞれどちらか一方から引継ぐ
ことによって実現したとすると、
その結果生じる子は多くの場合適正な盤面とはならないわけだけど、
それもアリ、ただしその不正さに応じて評価関数の減点対象、ということにすれば。



140 :□7×7=4□□:04/09/30 00:14:34 ID:DT1O8cMJ
>>135 の案も考慮してくれ

141 :□7×7=4□□:04/09/30 00:23:22 ID:L/LTDnsB
>>140
多分、漏れが聞きかじってる遺伝的アルゴリズムは、その
「スワップする」ってやつだと思うんだよね。
で、>>139がそのスワップではないかと。

142 :□7×7=4□□:04/09/30 00:53:59 ID:Guxgb0vP
>>139
うーん、いまいちイメージが湧かない、というよりは
先が見えない。

それで交配すると、ほとんどの子は親より低い点数(不当なための減点)になり、
あっという間に淘汰されてしまわないだろうか。
仮に評価の高い子ができたところで、
最終的にはそれを不正じゃない状態にしなきゃならないわけだが、
そうやって交配してできた状態を、正当な状態にもっていけるもんだろうか。
もっていけたとしても、持っていく間に盤面の状態はかなり変わってしまい、
評価が下がらないだろうか。

「だろうか」ばっかりで、やってみなきゃわからないけどね。

143 :□7×7=4□□:04/09/30 01:07:33 ID:oVjmfYlM
>>110
お絵かきロジックは多重背理が必要なのもあるのでその点留意。
ま、確定しなきゃ再帰処理かけりゃいいだけなんだけども。
多色問題になると難度が格段にうpするようなので、手応えも上がるかも。

>>115
人間のトップは十分に破る余地があると聞いた記憶がある。

>>124
むしろこのスレでソースもアルゴリズムも公開しまくって情報交換しつつ
切磋琢磨する方がいいんじゃないか?

144 :□7×7=4□□:04/09/30 01:19:10 ID:oVjmfYlM
で、スケコンとGAについて。

スケコンは、全体が一繋がりでないといけない。
つまり、登場する単語は必ず他の単語と交わることになる。

で、単語と単語は必ず縦と横に一点で交わる。つまり、
「交わる単語はどれか」
「自分の何文字目が交わるか」
「相手の何文字目と交わるか」
この3つが判明すれば、二単語の位置関係は一意に定まるわけだ。
(厳密には縦横交換した二通りになるけども)

145 :□7×7=4□□:04/09/30 01:39:32 ID:oVjmfYlM
これを踏まえてとりあえずコーディングしてみるなら、

(交わる単語の番号)(自分の何文字目か)(相手の何文字目か)

のセットを1単位として、単語の数だけ並べてみてはどうだろ。
登場しない単語については、(交わる単語の番号)を0にでもすればいい。

この遺伝子情報をもとにスケルトンを組み立てれば、全ての単語の位置
関係が、一意に定まることになる。

この表現ならば交叉や突然変異も、比較的簡単に行えるはず。
このままじゃ致死遺伝子(文字同士の衝突など)の発生率は高いけどね。
そこをどう防いでいくかは今後の課題ってことで。

146 :□7×7=4□□:04/09/30 01:42:39 ID:2IGUYa9o
単語二つが十字に組んでいる部品や、もっと複雑に組んでいる部品同士が交雑するというのは?

147 :□7×7=4□□:04/09/30 02:12:18 ID:L/LTDnsB
>>145
それ良案っぽいね。
どうせ、各ワードに対して、それと交われるワード(及び位置)
なんて、百とかせいぜい二百くらいしか無いんだから、
それをあらかじめ全部調べて付番しておくこともできるかと。

変な物ばかりできないためには、>>146の案を取り入れて
「交わっているワード同士は行動をともにする傾向をもつ」
とかにすればいいのかも。

148 : ◆mjGBW.jPnM :04/09/30 10:25:35 ID:wjlDrJHi
22の後者ところの人です。ROMでした。どうぞよろしく。

つまり遺伝子は交点中心に考える、ということか。うまい案だな。
>>145の交差位置情報は「交差可能な文字のうち何番目」の方が死ににくくなっていいかも。

「単語番号1:単語番号2:単語番号1の、2と交差可能な文字のうちの何番目か:単語番号2の、1と交差可能な文字のうちの何番目か:」
を全通りリストにして並べて、その交差があるかないかの01をランダムに決めてしまえばよいのか。
これなら盤面も(縦横の入れ替えはあるけど)遺伝子で一意に決まるのでは?

スケコンは40単語だし、実際の可能な交差を考えれば、
問題によってはカナなので交差が少なければ1000通りもないかも。

149 :□7×7=4□□:04/09/30 11:04:15 ID:L/LTDnsB
>>148
適正な盤面とは限らないけど、一意に決まることは確かだよね。

盤面の評価(広さとか、正当性とか)に手間がかかりそう、というのが
交点中心のアプローチの難点、なのかなあ?

150 :□7×7=4□□:04/10/02 16:56:30 ID:2IK9AgUy
>>149
いや、意外とそんなに手間はかからない。多分。

詳細はまたのちほど。

151 :□7×7=4□□:04/10/03 01:14:14 ID:fGxgMTUA
たとえば、単語が以下の3つだったとする。
イツテヨシ オマエモナ キモイヨー

交点に付番してその交点で交わるか否かでコーディングすると
1. [イ]ツテヨシ と キモ[イ]ヨー で
 0 : 交差しない
 1 : 交差する  (以下同様)
2. イッテ[ヨ]シ と キモイ[ヨ]ー で…

3. オマエ[モ]ナ と キ[モ]イヨー で…

この3ビットのオンオフになるが、このうち 1 ビット目 と 2 ビット目が
同時にオンになると(110, 111)、当然ながら致死遺伝子となってしまう。

152 :□7×7=4□□:04/10/03 01:17:04 ID:fGxgMTUA
そこで単語の交わりに付番して、遺伝情報で交差位置を示すとどうだろう。

1. イッテヨシ と キモイヨー は
 0 : 交差しない
 1 : [イ]ツテヨシ と キモ[イ]ヨー で 交差
 2 : イッテ[ヨ]シ と キモイ[ヨ]ー で 交差

2. オマエモナ と キモイヨー は
 0 : 交差しない
 1 : オマエ[モ]ナ と キ[モ]イヨー で 交差

「21」だったら下のようになるわけだな。

  オ  イ
  マ  ツ
  エ  テ
キモイ.ヨー
  ナ  シ

153 :□7×7=4□□:04/10/03 08:01:11 ID:JD8JZncH
>>151
致死にしないで、どちらか一方だけが発現するように両方のタイプを計算させればよいのではなかろうか。

154 :□7×7=4□□:04/10/03 09:32:53 ID:fGxgMTUA
>>153
>>152みたいにすれば、片方だけを発現させるような処理が不要になる。

>>151だと
 101 011
を交叉させるときに
 1|01 0|11
で一点交叉させると
 110 001
明らかな致死遺伝子が発生する。

>>152の方法だったら
 10  21
 1|0 2|1
 11  20
明らかな致死遺伝子の発生は抑制できるし、交差位置の交換もスムーズに行える。

155 :□7×7=4□□:04/10/03 09:42:43 ID:fGxgMTUA
ところでスケコンって

   キ
イチゴ
  ヨウキ
  ウ

みたいに2×2のカタマリが出来るのはセーフだったっけ?

156 :□7×7=4□□:04/10/03 09:43:00 ID:1iJ9pfCR
>>151,153のデータ例の時、突然変異は
ge_num[] = {3, 2}
i = rand() % 2;
gene[i] = rand() % ge_num[i];
みたいにすればいいのかな?

157 :156:04/10/03 09:44:16 ID:1iJ9pfCR
アンカー訂正
誤)>>151,153
正)>>152,154

158 :□7×7=4□□:04/10/03 13:14:56 ID:hr5fxi/a
>155
問題ないはず。過去に何度か見た覚えがあるし、ルールにも引っかかってない。

159 :□7×7=4□□:04/10/03 14:30:36 ID:QzQXbx5l
>>158
OKなのだけど、それを考慮に入れ始めると盤面の不正性の検討が
ややこしくなる気がするんだよね。
だから、「隣り同士の行/列に言葉が入る時は、必ずズレて入るようにする」
というつもりでやった方がいいのかもしれないって漏れは思う。

160 :□7×7=4□□:04/10/03 14:47:24 ID:xDvfkawO
そう?
統一的に簡単な方法でチェックできる筈だけど

161 : ◆fFfm.OLAKE :04/10/03 15:47:49 ID:Ae5E6zE2
波及効果のハタンチェックプログラムって作れませんかね?

作者側が解答として想定した盤面(数字のみ)を入力して、
その盤面がルール2を満たしているかどうかを調べる、みたいなの。

このスレの優秀な頭脳さんにぜひお願いしたいです。

162 :□7×7=4□□:04/10/03 17:26:48 ID:xDvfkawO
ソルバーでいいんじゃないのかな
作成途中にリアルタイムでチェックしたいとか、そういうのかな

163 : ◆MfK.LMS3eY :04/10/03 18:20:35 ID:pqL5funY
>>161
やっぱ漏れだけじゃなかったのね、そういうの欲しかったの。

つー訳でExcelに入力してチェックするためのマクロ、既に作ってあります。
左上から1文字ずつ見て回るという芸のないマクロですが、
そんなんでよかったらご提供申し上げます。
ファイルそのままどこかにうpするか、マクロだけテキストでここに書き込むか、
そういう経験のない文系の漏れなので、ご意見をいただきたいと。

あ、そーそー。
実は、Mac版Excelでしか動作確認してないけど、大丈夫だよね、きっと。


164 :□7×7=4□□:04/10/03 21:25:23 ID:gMV9GNsP
>>156
遺伝子表現は>>152ってことでOK?
そのままだと、2単語の交差パターンが多ければ多いほど「交差なし」が
選択される可能性が下がってしまうので、確率の調整は必要かも。

たとえば、必ず半分の確率で「交差なし」を選択させるとか。
gene[i] = (rand() % 2 == 1)? 0 : rand() % (ge_num[i] - 1) + 1

>>158
そうか、dクス。
盤面に単語を全部埋めたあとにも、再度妥当性のチェックが必要になるな。
(2×2のブロックが不可なら、単語一つ埋めるたびのチェックだけで十分なはず)

>>163
ファイルを圧縮して流れにくいとこにうp、ってのが無難じゃないかと。
もしくはどっか無料のレン鯖借りるとか。

165 :□7×7=4□□:04/10/03 22:14:16 ID:xDvfkawO
とりあえず寿命数日のアップローダを使って、
誰かが拾ってgeocitiesあたりにサイトを立てて保管すればいい

166 :□7×7=4□□:04/10/03 22:14:28 ID:bZrT5H8I
このスレ専用のあぷろだでも欲しいとこだね。

167 :156=157:04/10/03 23:39:13 ID:Motzdxt+
>>164
dクス。
GAはここで初めて知ったもんで(という言葉は言い訳にもならんが)その辺の考慮ができんかったとです。

>>All
これもゲームといえばゲームだしアプロダはこれ使っていいんじゃない?
http://gamdev.org/up/

168 :□7×7=4□□:04/10/04 00:01:31 ID:8gLZKyMU
>>167
そこいいね。
そんなに頻繁にうpがあるわけじゃないだろうし、
ちょうどよさそう。

169 : ◆fFfm.OLAKE :04/10/04 00:19:14 ID:aI2CqbK5
>>162
「解く」までのチェックはいらないんですの。
波及効果作りでいちばんきついのが、ルール2の矛盾がないかどうか
盤面見渡して調べる作業なんですが、要はそれさえできればじゅうぶん、ってことで。

ひとりにしてくれの余計な数字埋めプログラムがありがたいのと同じような感じ?

170 :□7×7=4□□:04/10/04 00:29:01 ID:Quzmg33X
>>162
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1064150088&res=236
こんなんでどう?簡略化しまくったけど。

171 :□7×7=4□□:04/10/04 00:41:02 ID:7A19CjOT
javascriptか何かで動いてて、
違反する数字をマスに書いた瞬間に
音が鳴る、みたいなのがいいのかな

172 :□7×7=4□□:04/10/04 00:52:19 ID:8gLZKyMU
いっそ波及効果エディタ、として作ったほうがよさげ

173 :□7×7=4□□:04/10/04 05:50:05 ID:No17V/PN
へやわけでならそういうの見たことがあるけどな。
波及効果ってコンピュータには扱いやすそう。分断禁とか無いし。

174 :□7×7=4□□:04/10/04 13:18:49 ID:YnpRPZ3V
波及効果は部屋の形の入力が面倒そうだね。
数字のチェックだけなら簡単なのだけど。

175 :□7×7=4□□:04/10/04 21:48:39 ID:No17V/PN
>>174
どうかな。
へやわけの部屋に比べて確かに自由度が高いから、
人の入力操作は若干面倒になるだろうけど、
コンピュータの方としては大差ないんじゃないかな。
部屋の壁を何回またぐか、とか数える必要もないし。



176 :□7×7=4□□:04/10/04 21:59:49 ID:jm36IUas
>>175
その「人間側が面倒臭い」ってことが言いたいんだと思うけど…

人が扱うのに適した上手いテキストデータの形式が思い浮かばない
チェックするだけなら数字だけですむけど、清書用に使うためには部屋の情報も欲しいしね

177 :□7×7=4□□:04/10/04 23:00:07 ID:No17V/PN
>>176
そのようなエディタができたら、テキストデータの形式とかは不要になるんじゃない?
エディタ上で入力して、データはそのエディタの形式で持っていればいいんだから。

178 :163 ◆MfK.LMS3eY :04/10/04 23:02:58 ID:PuczEivm
>167 thx!
とりあえず、うpしてみました。
ttp://gamdev.org/up/img/1481.lzh

一応、職場のWinで動作確認&ウィルスチェックは済ませてあります。
使える人は使ってみてやってください。


179 :□7×7=4□□:04/10/04 23:05:40 ID:jm36IUas
>>177
まぁそうなんですけどね
出来ることならあまりエディタに依存させたくないのよ

180 :□7×7=4□□:04/10/04 23:19:40 ID:7A19CjOT
壁の位置情報と数字だけでいいんでしょ
例えば、各マスに左と上の壁の有無と中の数字の情報を持たせるとか

181 :□7×7=4□□:04/10/04 23:26:47 ID:No17V/PN
>>180
ある程度のチェック機能とかつけるんだったら、たとえば
各ブロックに「ブロック番号」みたいなものを与えて、各マスに
自分のブロックの番号を持たせるとかの方が扱いやすそうかな?

問題を作成・表示するためだけのツールだったら
そういう形の方が簡単になるだろうけどね。

182 :□7×7=4□□:04/10/05 00:08:10 ID:CcqAsIcI
内部データではそうすればいいと思うけど、
入出力用のテキストデータには要らない

183 : ◆fFfm.OLAKE :04/10/05 00:51:35 ID:jzVf9hFr
>>178
さっそく使ってみました。便利!
まことに感謝感激でございます。

184 :□7×7=4□□:04/10/05 01:02:44 ID:t+GcaMhr
>>182
あーテキストファイルで入出力するの? GUIじゃなくて?
なんかこう、盤面をマウスとかで操作して入力するようなものを想像してた。

185 :□7×7=4□□:04/10/05 01:13:43 ID:CcqAsIcI
最悪、テキストでINとOUTを作った方が使いやすい
GUIで操作して、結果はテキストに吐き出す感じ

データの規格さえ合わせれば、そのデータを他のツールに
読ませたり、テキスト処理で加工したりできる

186 :□7×7=4□□:04/10/05 01:36:53 ID:t+GcaMhr
>>185
いや、たぶん言いたいことは分かるんだけど。
でもそのテキストに出力ってのは、もうそのままニコリに郵送できるみたいな
整形された盤面を出力すればいいんじゃないかな?

データの規格を合わせればって話は、内部で扱うデータ形式を
そのまま書き出したようなものでもいいって思うし。

187 :□7×7=4□□:04/10/05 02:09:51 ID:CcqAsIcI
まあ、思想みたいなもんだから
windowsとmacとunixと、どれが一番優れてるかみたいな話

188 :□7×7=4□□:04/10/05 17:24:31 ID:V+8XAUeD
波及効果のテキストデータの形式のたたき台として。

上段は部屋の分割。同じ文字を使っていても、縦横で接していない場合は違う部屋。
下段は数字の位置。 '-' は白マス。
上段と下段の間は1行以上あける。

チェックツールの入力として使う場合には数字をすべて入れた形で入力すればよいかと。

例)

abaa
bbaa
aabb
aabb

----
--2-
---4
2---

189 :□7×7=4□□:04/10/05 17:29:19 ID:FfO/yALo
>>188
やっぱその形に落ち着くわな
テキスト打ち込むときに四色問題としても楽しめる特典付き

190 :進可 ◆Sinka1my5k :04/10/05 18:28:11 ID:Ppoo2ciE
なんか急にスレの進みがよくなってきたね。

新しく解答支援ツールページみつけたので紹介。たぶん初出だと思う。
ttp://homepage2.nifty.com/lonelyperzoo/
ナンプレ、ぬりかべ、美術館、ましゅ など。

>169 を読んで納得。確かにチェックが一番しんどそうだし
入力は、数字打ってリターン、数字打ってリターンだけにすれば単純作業の分、早いよな。
数字も大体1〜6程度だし。

データー形式としては188がかなりいいと思う。
ただ、パソで処理するなら違う部屋は必ず違う英字にした方がいい。
入力はそれでよしとして、内部で清書するってパターンもありだけど。

191 :□7×7=4□□:04/10/05 19:21:01 ID:CcqAsIcI
波及効果ジャイアントで部屋数が26を越えた場合

192 :188:04/10/05 20:56:38 ID:V+8XAUeD
>>191
大文字を使えばいい。なんておもったんだけど、
実際数えてみたら、10×10でも部屋数は26を越えて、
ジャイアントでは100オーバーするのでダメ。
この分だとスーパージャイアントの部屋数は256を軽く越えそうですよ。
波及効果の部屋数は多いですね。ちょっと意外。


>>188
数字の10以上対策を考えていなかったことに気がつきました。
10以上の数字に対してはアルファベットで入力させるという案を出しておきます。
あまりないとおもわれるので、対応だけできればいいと思うんだけど、
これはどこかで上限を決めないといけない話。

個人的には大文字、小文字の使い分けはしたくないのですが、使い分けて61まで対応。
35もあれば足りるとは思っているけど、一応。

例)

a=10,b=11,...,z=35,A=36,B=37,...,Z=61

193 :□7×7=4□□:04/10/05 21:29:27 ID:QBgUjekG
189 が言うように同じ色を使い回せばいい。
どうしても色塗り分けが面倒なら、10進でスペース区切りにすれば上限など気にする必要なし。

もともとテキスト形式が欲しいのって単に保存しておくのに便利だからでしょ。
入力は使いやすいGUIを作って、出力でいくつかの形式を選べるようにしておけばいいかと。

194 :□7×7=4□□:04/10/05 21:53:02 ID:CcqAsIcI
どうせ入力はGUIなんだから、データの視認性は
高くなくていいけどね

195 :□7×7=4□□:04/10/06 00:03:45 ID:gNsc5RvD
えっ、手打ち想定してたの俺だけ?

プログラムでやるなら、ぬりわけのアルゴリズムが気になる。
適当にやっても多くて6色ぐらいで収まりそうだけど、
確実にN色以下に塗り分ける簡単な仕組みってあるかな?
Nは4じゃなくて5でも6でもいいんだけど。

196 : ◆MfK.LMS3eY :04/10/06 07:43:48 ID:G07XEIur
>183
喜んで貰えてなによりです。
そして、もし感謝していただけるなら、
漏れの分のノルマ、持ってきやがれぇ( ・∀・)つ●ドゾー


197 :□7×7=4□□:04/10/06 20:32:41 ID:a9j4tXHN
>>178=183
遅ればせながら使わせていただきました。
作りながらの途中確認がとてもラクだった。
ありがとう。

198 : ◆fFfm.OLAKE :04/10/06 23:57:53 ID:Aoa4xmjV
178と183は別人なのだが!

199 :197:04/10/07 00:07:54 ID:224Ch0Ni
178=196 or2

200 : ◆fFfm.OLAKE :04/10/07 00:09:14 ID:JRCLND0o
197さんはおしりが大きいですね!

201 :□7×7=4□□:04/10/07 01:42:46 ID:IWIY5PjT
>>195
四色問題?

そんなにアルゴリズムに凝らなくても大丈夫だと思うよ。

202 :マジレスマニア ◆KMAjireS2U :04/10/07 02:04:21 ID:r/h5hX0q
いままで名無しだったけどモノを作り始めたのでコテにします。

みんながスケコンの遺伝子について話あうさなか、
(と言っても、話は既に波及効果に移っているようですが)
遺伝子情報なんて考えず、しらみつぶし法で
とりあえず1つの解にたどり着くのができました。

2つめ以降の解を探しにいくところは作ってる最中だけど、
既に仕様は頭の中で固まってます。
全ての解を巡回してくれるはず。
問題はどんだけ時間かかるか…。

203 :□7×7=4□□:04/10/08 01:07:19 ID:SmCYjtpD
【IT】パズラーに福音?Webを使った多言語クロスワードパズル解答プログラム
http://news16.2ch.net/test/read.cgi/scienceplus/1097156523/l50

204 :□7×7=4□□:04/10/09 20:37:52 ID:B2U57s9O
http://www.slis.tsukuba.ac.jp/school/lecture/sotsuron/H13/13000090.pdf
とりあえず貼ってみる

205 :進可 ◆Sinka1my5k :04/10/09 21:08:49 ID:asdz3vb9
フォーマットの確立。どうせなら、線を引くのや黒マスを置くのや
壁を作るのやらを統合的にまとめられないかなぁ?

あと、スケコンやってみようとしたけど、まだ俺には難しすぎるようだ。

206 :□7×7=4□□:04/10/10 00:49:50 ID:8vyvH3+J
平均点を上回るだけじゃあなあ

207 :マジレスマニア ◆KMAjireS2U :04/10/10 02:27:26 ID:zbuthlUQ
いざ、ニコリの問題を入力してやってみたら、
まだまだ実装しなきゃならんことがいっぱい。
でも着実に完成に近づきつつあります。

>>204
やはり全ての解を探索するのは時間がかかりすぎるようですね。
まぁ、とりあえず完成してから考えよう。

208 :□7×7=4□□:04/10/10 02:34:12 ID:8vyvH3+J
時間かかるというか、無理でしょう
40の候補から組むべき26個選ぶだけで、2.3E10ある

209 :□7×7=4□□:04/10/10 03:00:22 ID:+oIHUSY6
6色で確実に塗り分ける方法

全ての部屋の中から隣接する部屋の数が5以下の部屋を全て取り除く。
この部屋は回りの部屋全てが違う色だったとしても残りの色で塗れば良い
「その部屋を取り除いた状態で」隣接する部屋の数が5以下の部屋を全て取り除く。
このようにすれば全ての部屋が無くなるので取り除いたのと逆の順に塗っていけば良い



210 :□7×7=4□□:04/10/10 03:39:34 ID:jz1r/jzJ
>>209
「途中で6以上の部屋ばかりになってしまい、操作が続けられなくなる」という
状況が生じないというのは…、漏れはすぐには分からないんだけど、そうなん?

211 :209:04/10/10 04:01:32 ID:+oIHUSY6
全ての部屋が6、という状況を想像してみるとわかりやすい。
これは正6角形を敷き詰めた状態(もしくはレンガを積み上げた状態)だが、
6を維持するためには無限平面にする必要がある。
波及効果の問題は当然有限平面なので淵に(とは限らないが)5以下の部屋は必ず発生する

212 :□7×7=4□□:04/10/10 04:21:22 ID:jz1r/jzJ
そっか、グラフで言ったら平面グラフになってないといけないんだ。とんくす。

213 :□7×7=4□□:04/10/10 11:04:18 ID:3wbgtNqD
ܷܵܶ

WindowsXPは行間が空いて、目に優しいなあ!

214 :□7×7=4□□:04/10/10 22:43:58 ID:B8wtK5ds
NGワード推奨

&#179
&#18

を小文字にしたもの。IEの表示に悪さをし、行間を一行空けさせる。

215 :□7×7=4□□:04/10/10 23:55:01 ID:1cZZT5pz
>>213

216 :□7×7=4□□:04/10/11 00:57:04 ID:2P9eSKUU
GAのスケルトンへの応用例は実際に過去に存在しています。
ttp://gorogoro.cis.ibaraki.ac.jp/web/html/sotsuron.html
の平成六年度参照

遺伝的アルゴリズム(北野宏明)という本にも軽く触れられていて、
(上の論文と関係あるのか知らん)
その中ではコンテストの第一位よりもさらに良い解が得られたと書かれています。

217 :マジレスマニア ◆KMAjireS2U :04/10/11 01:07:30 ID:+0jRnF9R
とりあえずスケコン完成。
ただし>>155のパターンは現れないので、もうちょっと改良が必要。

で、実行してみたわけですが、全然進まない。
およそ全体の4000分の1に相当する処理が、10分たっても終わらない。
仮に10分で終わったところで、1ヶ月流さないと終わらないことに…。

とりあえずこれを基盤として、ここから「点数が高くならなそうなパターン」の
枝切りとか、GAへの応用とかを考えてみます。


…と書き込んでいたら>>216、既にやった人がいるんですね。
いったん凍結して他のでも作ろうかな。

218 :進可 ◆Sinka1my5k :04/10/16 23:06:23 ID:Mt6fdrRy
>211
形自由な部屋が全てN個以上の他の部屋に接しているとして
そのNの最大値は幾つなのだろう?
3つまでは簡単にできるんだが

219 :□7×7=4□□:04/10/16 23:09:33 ID:fVNP9dOc
>>218
四色問題の結果を定理として認めるなら、三つが最大

220 :□7×7=4□□:04/10/17 00:15:46 ID:DafY98Vx
すべての部屋が他の4つの部屋と接している例

1111
2342
2432
1111

私も>>211で納得できているわけではないけど、
(6以上を実現するためにはハチノスにならんといけない理由がわからん、でもそれ以外が無理っぽい気はする)
211 を否定するためには有限平面で6の例を実現しないといけないわけで。

でも、5はいけそうだ。がんばる。

221 :□7×7=4□□:04/10/17 09:53:34 ID:MAeLBS2h
極大平面グラフにしたときに頂点数に対して辺が一番多くなる。
そのときにオイラーの定理 v - e + f = 2 と極大平面グラフで 2e = 3f から
e <= 3v - 6
平均次数 d = 2e / v <= 6
より次数 5 の頂点が存在する

222 :□7×7=4□□:04/10/17 10:57:16 ID:QZePDZVe
グラフ理論は下地なしに入れるもの?

223 :220:04/10/17 11:04:13 ID:DafY98Vx
出来た。

11111111
23322442
21443312
21334412
24422332
11111111

ここまでくると4色塗りわけも難しくなってきて楽しいかも。

最小部屋数、最小面積が気になってきたけど、どんなプログラムを組めばよいかわからん。
上記のは結構いい線いってると思うんだけど。

224 :進可 ◆Sinka1my5k :04/10/17 13:05:43 ID:egxzbayB
   ゚  ゚


  ( Д )

225 :209:04/10/18 18:49:53 ID:nemeoSOh
最小部屋数は当然12。正12面体を平面に展開しただけだが

1111111
1433223
1424413
2423313
2411443
2222222

接する国の数が全て6以上の地図が有限平面では不可能な証明は
正多面体が5種類しかない事の証明と同じで良い筈なのだが。

ところで、ここの書き込みを参考に自分でナンバーリンクソルバーを作ってみたのだが、
>>100の問題の短絡チェックは3秒で終わったぞ。
で、G16の2番を調べたら9分で終わったので4番を調べたのだが・・・
丸2日経っても終わらなかったorz


226 :220=223:04/10/19 00:10:39 ID:4NDAvdeX
>>225
なるほど、わかってきた。オイラーの多面体定理より

すべての部屋が接する部屋の数は2以上で、
部屋数 >= 12 / (6 - すべての部屋が接する部屋の数)

が求まるのか。

確かに5の最小部屋数は12で、6は不可能だ。
4の最小部屋数は6で、正6面体を平面に展開したものか。

220は8部屋……

227 :□7×7=4□□:04/10/19 00:46:32 ID:E7zI145R
>>226
正六面体をっていうことは、こういうことかね。

11111
12231
13131
13221
11111

でもこれは三色で塗り分け可能だよ。

228 :□7×7=4□□:04/10/19 00:56:44 ID:E7zI145R
これならいいのかな。

11113
14223
24113
22223

229 :□7×7=4□□:04/10/19 00:59:34 ID:E7zI145R
十面サイコロの形は4色必要な形だって思うんだよね。
(ttp://images.google.com/images?q=10%E9%9D%A2%E3%82%B5%E3%82%A4%E3%82%B3%E3%83%AD)
で、それを八面にしたのが>>220で、六面にしたのが>>228と。

230 :□7×7=4□□:04/10/19 01:06:07 ID:E7zI145R
ごめん、誰も塗り分けの話はしてなかったね。スマソ

231 :□7×7=4□□:04/10/19 01:52:20 ID:4NDAvdeX
>>228

3色でいけるよ!

11113
13223
23113
22223

10面サイコロの形は6n面の場合、3色、それ以外は4色になるのかな?


正多面体についてまとめてみた。

正4面体:4色
正6面体:3色
正8面体:2色
正12面体:4色
正20面体:3色

正20面体が3色であることがすぐにわからなかった自分は大馬鹿だと思いました。

232 :□7×7=4□□:04/10/19 02:36:29 ID:E7zI145R
>>231
あーうん、漏れもそのあと考えて気がついたんだけど、話題がそれてるって思って。

(2n)面サイコロについてもその通りって思うよ。

233 :□7×7=4□□:04/10/20 07:07:55 ID:D+jWoIBz
>>161- からの流れだけど、波及効果エディタ? みたいなやつ
リアルタイムでエラーチェックができる。
ttp://gr.vxx.jp/haky.html
個人サイトだけど。


234 :進可 ◆Sinka1my5k :04/10/23 19:14:12 ID:wvpGaeeO
>233
いいなぁ、こんなの作りたいなぁ。おみくじワロタ。

できれば人間っぽく解いていくようなの作ってみたい。
法則なんかを自分で見つけて上達していくようなAIがあればいいけど
さすがにそこまでは難しすぎるよなぁ。

235 :□7×7=4□□:04/10/23 19:39:18 ID:A+XsZTs8
許可する仮定のレベルとか使っていい手筋とかを設定すると、
そこまでは勝手に解いてくれる、とかにすると作るのが楽になりそう

236 : ◆.jC7ANgFY. :04/10/31 14:09:00 ID:EA+Cq5H/
私は美術館作成支援ツールをVisualBasic6.0で作ってみようかな。
VB6はマイナーかもしれないけど、

237 : ◆.jC7ANgFY. :04/11/03 00:21:20 ID:xjRQj9eU
まだ支援ツールとしてはまだまだだけど公開。参考までにどうぞ。
VB6持っててEXEは不安であればソースからどうぞ。

☆ビジュアル美術館β

VisualBasic6.0用ソースパック(使用した画像も同梱)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuSrc.lzh

WindowsEXE実行ファイル
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuEXE.lzh

238 :□7×7=4□□:04/11/03 21:30:21 ID:dzdLhqp5
>>237
よさげですね。
点対象に配置とか、漏れは(へやわけで)やろうと思って投げたけど、
やっぱあると便利ですね。

ところで、三つあるモードは統合できるのでは?

239 : ◆.jC7ANgFY. :04/11/03 23:57:40 ID:xjRQj9eU
>>238
当初はモード統合していましたが、ミスで勝手に盤面が崩れていくのが
ちょっと(Undoすればいいのだけど)使いにくいなぁと思い、普段作る
順番どおりにやってみました。今は○を置くと上下左右に×を打つ機能
しかありませんが、今後は中級問題まではサクサク作れるぐらいの
問題を解くプログラム(理詰め型)を搭載しようと思っています。
もっと便利なものをと考えてもなかなか案がでてこないもので、、、

240 : ◆.jC7ANgFY. :04/11/05 16:06:36 ID:7CmwjSc2
支援ツールとして十分なくらいのレベルになりました。
初級手筋(単純発生、単純否定、孤立、救出)と
中級手筋(斜めとび)を搭載しています。
慣れれば美術館を3分以内で作れます。
ちなみに私は運がよければ90秒で作れます。

☆ビジュアル美術館

VisualBasic6.0用ソースパック(使用した画像も同梱)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuSrc.lzh

WindowsEXE実行ファイル(高速化版)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuEXE.lzh

WindowsEXE実行ファイル(デバッグ)
ttp://nun.nu/fhdic.fbox.info/VisualBijutsuSafe.lzh

現在、私が使う上ではエラーは発生していませんが
エラーが発生するようでしたらデバッグで同じ作業をし
そのエラー内容と状況を伝えていただけると幸いです。

241 : ◆.jC7ANgFY. :04/11/05 19:51:57 ID:7CmwjSc2
色々反省点があるのでまた時間ができれば作り直そうと思います。

・盤面の管理方法がずさんだった
・盤面解析が異様に低速
・数字の点対称表現がなっていない

などなど。

242 :進可 ◆Sinka1my5k :04/11/06 17:44:20 ID:7cgDj8wr
グッジョブ! ちと操作がわかりづらいのが難点だけど良い感じ。取説キボンヌ。
現在が何モードかわからないのはちと辛いね。

243 : ◆.jC7ANgFY. :04/11/07 01:13:13 ID:2cVM9ojl
自動作成の方もつくろうかな。そこで質問なのですが、
"解き味の良い"美術館って具体的にいうとどういう物なんでしょう。
例えば、「連鎖が出る」とか「ある程度光が伸びる(4つぐらい)」とか
そんなもんなんでしょうかねぇ。

244 :□7×7=4□□:04/11/27 06:36:15 ID:PqMSgcgf
ふと思った。ナンリンソルバーの短絡チェックにバグが無いか調べたいのなら
自動生成プログラムを作って出来た盤面を180度逆向きにして解いてみれば良いじゃないか。
完全な問題として検出された盤面に短絡解が発見されたら短絡チェックのミス。

245 :□7×7=4□□:04/11/27 19:51:24 ID:NuuQcuVh
>>242
いつもお世話になっているナンリンソルバー、
15x15の趣向作を入力したら瞬殺されました_| ̄|○
0分0秒032ですって。

すげー

246 :□7×7=4□□:04/11/28 03:44:08 ID:XulpM55G
>244
短絡解発見時に答えが表示されるとして、
その答えが違う数字を結んだり途中断線があったりしたらバグありってこと?

247 :□7×7=4□□:04/11/28 08:05:46 ID:rAkz7xf9
短絡解の発見されなかった盤面を180度回して再度解かせて短絡解が発見された場合は
元の盤面で短絡解になり得るパターンを枝刈りで見落とした事になる。
このチェック方法はナンバーリンクの解答図として有り得ない解を出さなくなった上で
枝刈りが正常に行われているかのチェックに使える。。。かも。
高速化を考えると結構無茶な枝刈りをやらざるを得なくなるので
短絡解の見落としが無いかチェックする方法は結構重要になってくる。
短絡解のある盤面を片っ端から探して突っ込むだけでは限界があるんで。

248 :□7×7=4□□:04/11/28 17:22:34 ID:5FFWVvyz
なるほど、さらに発展させれば点対称線対称を全部入れて
同じ短絡あり面で8通りの短絡チェックができるな。
そしてどれか一つでも短絡無しと判断すれば
そのチェックはどこかで見落としがある、という訳か。

249 :□7×7=4□□:04/12/07 11:52:10 ID:HCAf40aS
GAの教科書にまんまスケコンの応用例があって、
ずいぶん昔にやってみたんだけど せいぜい平均賞どまりだった。

一方、語彙制限付き しりとりにGAつかったら きれいにのって
あっさり 最適解に到達。
試行ごとに収束する解が違っておもしろかった。

GAするときは問題解析を結構がんばらないときれいに収まらない印象。

250 :□7×7=4□□:04/12/07 13:22:18 ID:Emh+XjtI
そこが一番のキモなんだけど、論文を見てもよく判らない罠

251 :□7×7=4□□:04/12/14 02:16:31 ID:HTswYIBD
プログラムでスケコン平均超えるのって大変なんだな・・・
昔書いたプログラムをちょっと弄って101号のを解かせてみたのだが
平均6918、トップは7737なのに最高6817までしか出ない・・・


252 :□7×7=4□□:04/12/18 02:24:04 ID:wIbgghus
ルービックキューブをCUIベース(unixとか)で組もうと思います。
面の色のデータベースはどう定義するのがエッセンシャルでしょうか?
おそらく面(0-5)xX(0-2)xY(0-2)の3次元配列になると思います。
面の中の座標軸をどう定義すると数学的にきれいなんでしょう?

253 :□7×7=4□□:04/12/18 02:51:53 ID:z3wyA2Iw
ソルバー作るの?

254 :□7×7=4□□:04/12/18 14:26:02 ID:3iKGvcXz
実は3*3ルービックキューブは各面の中央は全く動かない。

255 :□7×7=4□□:04/12/20 01:53:00 ID:9ynjIymM
ソルバーといっても、単純にバラバラなルービックキューブを入力すると、
回し方を返してくれるというものにはしたくないと思います。
そういうものはたくさんあるんで。

今回の目標は「一般解を導き出すアルゴリズム」です。
メタ・ソルバーというのか、ソルバー・メーカーというのか、
とりあえず「ルール」を入力として、「ソルバー」を出力するというのが目標です。
コンピュータにルービックキューブを「揃えて」もらうのではなくて、
ルービックキューブの揃え方を教えてもらう*のです。
ということは出力として出てくるものはアルゴリズムです。
プログラムのような、「ここが赤で反対が青だったら右を回す」という
条件分岐を含む記述になります。これを綺麗に出すために面の定義を綺麗にしておきたいのです。

とりあえず展開図で面番号を
 4
3502
 1
と定義してこの展開図の左右をx軸-+,
上下をy軸-+とした3次元配列cube[面][X][Y]として
動くルービックキューブを作ってみました。
xy軸がすごく納得行かず不満です。

(*)一般解とはいうものの、3^3ルービックキューブを渡して
Optimal Solverが出てくるのを待つ、というのは難しすぎるので、
まずは部分的なゴールから。1面完成なんかがいいでしょう。
Optimalでなくてもいいです。


256 :□7×7=4□□:04/12/20 03:19:33 ID:3nOoXzUq
ルービックキューブの、全ての状態からの
6面完成までの手順の数って、10いくつとか、そんなんだったような
それを割り出すべし

257 :□7×7=4□□:04/12/21 22:59:14 ID:0JoUISFT
test

258 :□7×7=4□□:04/12/21 23:00:29 ID:0JoUISFT
スーパーマリオブラザーズの任意の面をクリアできるソルバーってないだろうか?
入力は画面、出力はキー操作と言うことで。

259 :□7×7=4□□:04/12/21 23:22:57 ID:0JoUISFT
探したら出てきた。
http://robots.engadget.com/entry/2116781701378779/
やっぱりmindstormか…
エミュでできるやつを探してたのに。すごいなこれ。解けるんだろうか?

260 :□7×7=4□□:04/12/24 17:00:35 ID:HqlGBaxt
何かブロックが山積みになっているなと思ったら、
mindstorm でコントローラを操作しようとしてるのね。

賢いというべきか、頭悪いというべきか・・・


261 :進可 ◆Sinka1my5k :04/12/24 22:30:00 ID:L/R8itia
Cマガのナンバーリンク、例の解き方がでてますなぁ。ニヤリ。

262 :□7×7=4□□:05/01/03 09:31:56 ID:6Ewxm8RY
000000000000000000000000000000
000400000000000000030000000000
000000000000000000000005000000
000000000100000000000000000000
000003000000000006000007000000
000000000000000000000000000000
000000000000000000000800000000
000000000800000009000000000000
000007000000000000000000000000
000000000000000000000000000000
001000000400000000001100000000
000000000000000010000000000000
000200000000000000000006000000
010000110000000000000000000000
050000000000000000000000090002

進可さんのプログラムでこれ解いたらPen4-2GHzで
109億7517万3926ステップ、2時間1分48秒319かかったぞ。
とある表出11個対称形の問題をプログラムで解きにくいように
少し改造したらこの問題になって、試しに全検索したら2時間かかった。
・・・多分逆から解けば10分切るけど

263 :進可 ◆Sinka1my5k :05/01/03 13:35:37 ID:9h5YaOaM
ぐは!2時間かよ。さすがに上に数字が少ない問題は時間がかかるな。
回転や反転で面探索を短くする方法も考えたけど、なんかそれは
「反転させたら負けかなっと思っている」ような気がしてやらなかった。

ちなみに、2chに面をうpする場合は、問題を入力してから
上のバーにあるファイル>テキストで表示させると
↓のような感じで出てきます。ここからテキストからの入力もできるんで
2chでのやりとりは、こっちのが使いやすいです。

+++++++++++++++
+4+++++++3+++++
+++++++++++5+++
++++1++++++++++
++3+++++6++7+++
+++++++++++++++
++++++++++8++++
++++8+++9++++++
++7++++++++++++
+++++++++++++++
+a++4+++++b++++
++++++++a++++++
+2+++++++++6+++
1++b+++++++++++
5+++++++++++9+2

検証ご苦労様でした。

264 :進可 ◆Sinka1my5k :05/01/03 13:39:59 ID:9h5YaOaM
上下逆から短絡あり探索やってみた。

5+++++++++++9+2
1++b+++++++++++
+2+++++++++6+++
++++++++a++++++
+a++4+++++b++++
+++++++++++++++
++7++++++++++++
++++8+++9++++++
++++++++++8++++
+++++++++++++++
++3+++++6++7+++
++++1++++++++++
+++++++++++5+++
+4+++++++3+++++
+++++++++++++++

10112215回探索 0分5秒157

5秒?・・・何、この差_| ̄|○

265 :□7×7=4□□:05/01/05 22:05:08 ID:AdgLusRn
>>263
いままでROMしていたけど、ちょっと自作プログラムを
走らせてみた。上から順に時計回りに問題を回転させ
ている。(ミラー処理はコーディングしてない)

00:04:01.9489695 探索ステップ 870413965
00:00:02.8998330 探索ステップ 11450820
00:00:00.2962195 探索ステップ 1097793
00:00:32.2099730 探索ステップ 125931282

基本的には進可さんのプログラムと同じ考え方。簡単
にコーディングするにはこのやり方しかないと思う。
初代は進可さんのと同じぐらいのスピードだったが
内部データの持ち方と枝狩りアルゴリズムの見直し
でコツコツとスピードアップしていった。仕事が忙しく
なったので中断中だけど、まだまだいけるはず。


266 :□7×7=4□□:05/01/05 22:47:34 ID:wf15pd8N
盤面の回転で大きく変わるのですね。
こういう問題は並列ソルバにすれば安定しますね。
4並列ソルバで>>265を解くと0.3秒*4+α=1.2秒+αの時間で解けることになりますね。
アルゴリズムの改良だけでもっと探索時間が減って、
回転に対して探索時間が安定するようになれば並列化はいらないかもしれません。
そういう意味で並列化は今の時点では後でもいいかもと思います。

#現在私は領域分割の観点から大きくバックトラックできないかと思考中。

267 :□7×7=4□□:05/01/05 23:27:06 ID:YUPY0Tq/
漏れが必ず左上から解き始めるようなものか?

268 :□7×7=4□□:05/01/05 23:29:01 ID:AdgLusRn
並列は私も考えてみましたが問題によってはここまで大きな差が
でないので汎用性はあまり高くないかもしれません。実は回転に
よる問題の計算量を前もって知ることができれば、一番コストが
低いものだけ計算すればよいのではないかと考えていたのですが、
計算量の予測が数値化できず断念した経験があります。

領域分割も検討中。いくつかの方法が考えられるが、単純に分割
するとメモリの使用量が爆発するので駄目。今考えているのは
ある程度まで解いた段階で分割領域のミニ探索を行う方法ですけど
プログラムの構造を大幅に変更する必要があるので躊躇してます。

269 :□7×7=4□□:05/01/06 09:13:38 ID:iLjCxfu1
経験的には数字の配置の重心だけでそこそこコストを量れますよ。
0.17/25274
0.84/130956
58.77/15888737
12.54/2743254

270 :□7×7=4□□:05/01/06 22:42:48 ID:dozYBlXS
重心ですか。なるほど。視覚的には理解していたのですが、計算させた
ことがなかったです。

確かに >>263 だと重心で判断できますね。問題は回転によって重心が
移動しない対称形のやつですね。このタイプも回転させると 10 倍以上
差が出る場合があります。ただ何もしないよりはよいので、試して見る
価値はありそうですね。


271 :進可 ◆Sinka1my5k :05/01/06 23:21:37 ID:mul3oUr3
散文的にカキコ。

並列計算かぁ、そこまでしっかりやるなら反転もありかも。

重心っていうのは探索の早い位置に数字が多いかどうか?って考えでいいのかな?
探索開始位置に数字が多いと速く解けるのが多いだろうし。

ほかの重みとしては、端に数字が多いと速く解けるっていうのも感覚的にあるな。

あと、対象形で速さに差が出るのは、同じ番号の距離があやしいと思う。
確定の早いパターンが探索開始位置に近いほど、解き易いから。

272 :□7×7=4□□:05/01/07 10:16:34 ID:4CgAmXKC
この進可さんの方法って整合性のチェック
>>37の「ありえない状態になったら」の部分)は
どういうタイミングで発動するのでしょうか?

-「壁あり」を割り当てて整合性チェック
- if(整合の場合){次の壁の割り当てルーチンへ}
- if(不整合、または残りの割り当てで矛盾が出てバックトラックした場合){
-- 「壁なし」を割り当てて整合性チェック
--- if(整合の場合){次の壁の割り当てルーチンへ}
--- if(不整合、または残りの割り当てで矛盾が出てバックトラックした場合){バックトラック}
-- 現在の割り当てルーチン終わり

と言う感じで合ってますか?

273 :272:05/01/07 10:17:53 ID:4CgAmXKC
なんかインデントがおかしかったけど許して

274 :272:05/01/07 10:36:46 ID:4CgAmXKC
あと現在の整合性チェック項目を教えてもらえませんか?
いまのところスレを読むと
基本チェック
・数字マスからもう一方の数字マスまでたどり着けるかのチェック(推測)
枝刈り用チェック
・コの字型枝刈り(>>51)
・遠回りチェック(>>53)
・部分閉空間の枝刈り(>>55)→廃止→>>77のように小規模化
これでいいでしょうか。言っていい範囲で教えてください。

あと>>75の話ですが、この場合1の下のマスと2の下のマスの間の壁を決定した時点で
1と3が短絡されてるのでバックトラックできそうなもんですが、
1の下のマスと2の下のマスの間の壁の割り当てのときにはこれは検出されないのでしょか?


275 :262:05/01/07 17:46:20 ID:pOSU3C66
自分のプログラムでも解いてみた・・・
面倒なので元の向きと上下逆のみ。
元の向き:3分59秒063、394431038 step
逆の向き:0分00秒370、621326 step

枝刈りのアイデアはまだまだあるのだが15x15で効果が出るかは謎・・・
最終的には25x25を現実的な時間(大体1週間ぐらい)で解ける事を目標に高速化しています
ただ、このサイズになると問題によって探索空間が4桁ぐらいは平気で変わるので
どの問題でも安定して解ける、というのは厳しそう。

最適な探索方向については、同じ数字同士を繋いだ線の重心で調べれば良いと思う。
あと、枝刈りの方法によって最適な値は異なるけど縦向き、横向きも考慮するとより良い結果になりそう



276 :進可 ◆Sinka1my5k :05/01/07 20:23:41 ID:K620/EdE
>272
だいたいそんな感じ。詳しくはここにあり。
ttp://www.interq.or.jp/moonstone/person/numlink/nl01.html
ttp://www.interq.or.jp/moonstone/person/numlink/nl02.html

>274 現在の整合性チェック項目
同じく上のnl01とnl02のhtmlに書いてあります。
ただし、壁向こうチェックは片方だけとか、微調整してたと思った。


277 :進可 ◆Sinka1my5k :05/01/07 20:27:56 ID:K620/EdE
>274 >75 の件

図の場合、1と3が結ばれるのが確定するのは、1の真下のマスが縦直線に決まった時。
2の真下へチェックが移る前に決まる。だから、チェックするなら1の真下の時。

だが、実際にプログラムしてみると、うまくいかなかった。逆に時間がかかってしまう。
理由は、全てのマスに対し、「下に伸びるならそこに数字があるか?」を一々チェックするのは手間だから。
そしてその手間に対し、下に数字のあるケースはとても少ない。
なぜなら、空白マスの数>>(越えられない壁)>>数字マスの数 だから。

チェック回数に対し、NGになる状況が少なすぎる探索は、逆に時間がかかるので効果的ではない。
という結論に達したので無しにしました。

278 :265:05/01/08 00:22:11 ID:0tECDbRn
>>275
2GHz のマシンでですか?速いですね。ステップ数の数え方はプログラムに
よって違いがあるので正確には比較できないが、元の向きを見る限り私の
よりも大幅に枝刈りをしているようです。時間ができたら私ももう少し
考えて見よう。今以上の枝刈りをするには相当慎重にやらないとバグって
しまうのが怖いですが。

私の目標はとあるところで見かけた 25x42 の問題ですが、現実的には
25x25 ぐらいでしょうね。

重心はいろいろと調べて見ると面白いでしょうね。こちらも今後の課題です。

279 :265:05/01/08 00:25:41 ID:0tECDbRn
>>277
> チェック回数に対し、NGになる状況が少なすぎる探索は、逆に時間がかかるので効果的ではない。

この点は同意しますが、下方向の先読みを行わずにできる枝刈りは限られ
ているので、なんとしてでも組み込みたい機能です。条件としては「パスが
数字につながっている」、「下に数字がある」、「パスの値と下の数字の値
が異なる」の 3 つだけですから、これをいかに効率的にチェックできるか
を追い求めれば必ずクリアできます。これができれば 2 行以上下の数字も
活用できるようになります。

280 :269:05/01/08 17:45:43 ID:Kr1eBw6z
全体の重心だけだと探索時間にあまり関係のない部分
(上から探索したときの下側)の影響があるので、
上半分、右半分、下半分、左半分に分けて、そこの重心を使っていたりします。
これだと対称形で扁平な数字配置のときにも少しは対処できます。

上下左右対称のときにはどういう指標がいいんだろう…

# 15x15 と 25x25 の間のサイズで手頃な問題集がないかなあ。

281 :262:05/01/08 20:42:40 ID:C2N/n1cF
無いのなら自分で作っちゃえ、と20x20の自動生成に挑戦してみたのだが・・・
解くチェックが遅いのと1箇所でも短絡していると駄目なので厳しそう。
15x15が自動生成出来る限界なのかなぁ?それでも条件を厳しく設定すると
1問2時間とか平気で掛かったりするけど

282 :□7×7=4□□:05/01/09 00:15:21 ID:A9HNKhVW
普通は数字はどれくらいあるの?
20x20とかで

283 :262:05/01/09 01:04:52 ID:32hlV0u4
対称形なら限界が12か14ぐらい、普通に作ったら18〜22程度・・・だと思う。>20x20

284 :262:05/01/09 11:53:24 ID:32hlV0u4
駄目だ・・・サイズを1つ落として18x18の14個対称形を自動生成してみたのだが1問のチェックに3時間超えそうな勢い。
15から18に上がっただけでここまで変わるのか・・・15なら今と同じ程度の縛りを入れた問題でも大体数分で解くのに

285 :262:05/01/09 11:58:08 ID:32hlV0u4
そしてよく見ると6が1個しかなくてかわりに15がある・・・解けるわけねぇorz

286 :進可 ◆Sinka1my5k :05/01/09 12:53:32 ID:0wqIm++q
何気に聞き流してしまったんだが、面の自動生成ってどうやってるの?

287 :262:05/01/09 14:55:53 ID:32hlV0u4
全ての数字が違う問題を角の定理を使って解かせる。
但し、線が繋がった時に両端の数字が一致しているかのチェックは行わない。
全部埋まったらペアになっている数字を対応付けて短絡チェックをすればOK
結構乱暴な方法だけどこの方法でも案外まともな問題を作ってくれるのが不思議

288 :262:05/01/09 23:48:14 ID:32hlV0u4
++++++++++++++++++
+1++++++++++++++++
++++++++2+++++++++
++++++3++++4++5+++
++++++++++++++++++
++6+++++++++++++1+
+++++++++++++7++++
+++++++7+++++++8+9
a++4+++++++3++++++
++++++b+++++++c++9
d+e+++++++8+++++++
++++b+++++++++++++
+c+++++++++++++2++
++++++++++++++++++
+++6++d++++e++++++
+++++++++a++++++++
++++++++++++++++5+
++++++++++++++++++

18x18で妥協したら何とか1問完成・・・
このサイズの問題を量産しても使い道が無いので多分もう作りません
15xと25xの中間のサイズの問題が欲しいのならナンバーリンク2のパート3(14x24)が良いんじゃないかと思いました。
長方形なので微妙ですが逆に正方形の問題では使えないような解き方が見つかるかも?


289 :□7×7=4□□:05/01/10 20:20:31 ID:hxP1KM6F
なんかスレ読んでると深い世界みたいだねー>なんりん
解くんじゃなくて問題作るのって結構みんなやるのかな。どこかに投稿したり?
唯一の解をもつというのは決まりなんでしょうか。
「角の定理」っていうのがキーワードみたいだけど、
googleっても内容はでてこなかったです。考えてみよう。

290 :262:05/01/11 21:04:28 ID:pPx9i6sQ
要は全てのマスに線が通って回り道をしない事を前提に解くだけ。
ただ、この方法で自動生成するには高速なソルバーが必要で、
しかも良問が出来る可能性はかなり低い。
場合によってはコンピュータが出した問題から選別する時間があれば
最初から1問作れるぐらいだったりもするのであまり実用的じゃないかも。
出てくる問題は少なくともナンバーリンクのルールで解く事が出来て短絡解の無い問題ではあるのだが。

291 :265:05/01/12 22:52:12 ID:aJMvFhta
>>288
重心とか考えるのが面倒だったので短絡なしで先に全パターン検索し
一番効率的なやつだけ解かしてみました。それでも 30 分かかりますね。
解いたパターンは右 90 度回転の左右反転です。

短絡なしは一瞬で終わるので下手に重心を考えずに 8 パターン分
なしで計算し、一番ステップ数が少ないのをありで解かせるのも
いいのかもしれません。


292 :□7×7=4□□:05/01/14 06:09:32 ID:80H/75ZF
こんなスレがあったんだ。知らんかった。

はるか昔にナンリンソルバーは作ったことがあるんだが、
証明できない定理(つーか仮定)を使ってたんで、完璧かどうかは
なんとも言えなかった。ただし当時(90年代半ばぐらいだったかな)でも
10x10は普通に解けてた。

ちなみにその仮定と言うのが
「完全解があるものに関西解がある場合、
 関西解のうち1つは、必ずすべての曲がり角の内側を
 ななめにたどったところに数字がある」というもの。

これの反例が見つかったことが無いんだが、誰か証明してくんね?

293 :gr:05/01/14 07:12:47 ID:Yxua5VgO
>>292
こんな感じで示せないかな?

線の引き方に余裕度(名称はなんでもいいけど)とかいうものを、

 ‐余裕度は常に 0 以上の整数。

 ‐「すべての曲がり角の内側をたどったところに数字がある」という条件を
  みたしているとき、余裕度は 0 になる。

 ‐その条件をみたしていないときは、引き方を変えることで、もっと小さな
  余裕度を持った引き方にすることができる。

とかいうふうになるように、うまく定義するんだわ。

具体的には、たとえばこんな感じかな。

まず、各白マス(線の通ってないマス)に対して、そのマスから盤面の外へ
「白マスまたは『曲がり角の内側』をなしてるマス」だけを通って出るときの
線をまたぐ回数(出方が多数あるときはその合計)を考える。
そして、盤面の全白マスに対するその値を合計したものを、余裕度とする。

これだと、上の三条件をたしかにみたしてる。
というのも、まず 1 個目は明らか、2 個目はその時外へ出る道が無いから、
3 個目は曲がり角をくぼませればよいから。

よって、仮説は証明された。
と思う。

294 :□7×7=4□□:05/01/14 07:20:52 ID:Yxua5VgO
あ、白マスはタテヨコに通って、「曲がり角の内側」はナナメに通るのです。

○────┐□□□
□□○○┐│○─┐
□□│□││□□│
○─┘□││□□│
○─┐□│└─○│
□□│ a.└──○│
□○┘□□□□○│
○──────┘○
○────○□□□

たとえば上図で a のマスは、上から右上に抜ける 2 と、右下の 1 とで、
合わせて 3 と数えるわけです。

295 :□7×7=4□□:05/01/14 22:06:22 ID:5g3pJjbh
>>292

??┐
?a1? a1が空白なら
a2??

??□
?└?という別解が存在する
a2??

aが空白でなく、数字でもないなら、

??┐
?┐?
a2??となっているはず。

a2に対してa1と同じ議論が生じる。

という数学的帰納法でも証明できますね


296 :□7×7=4□□:05/01/14 22:48:53 ID:Yxua5VgO
そうそう。
> 曲がり角をくぼませればよいから
ってのが、それのことね。

297 :262:05/01/15 02:31:04 ID:IYwv2zRK
反例?
1 □□□
□□2 □
□1 □□
□□□2

色々な引き方があるけどどうやって引いても
┌   このような位置関係のマスは発生する。
  □

298 :295:05/01/15 05:09:00 ID:eWLwN/40
別解がなければという仮定がいるんだと思う。

完全解とか短絡解とか関西解と稠密解とかいまいち分類が分からないんだけど
誰か解説してくれる?

299 :□7×7=4□□:05/01/15 06:08:31 ID:La7yrmQy
>>297
どうかな。「内側」の定義の問題になると思うのだけど。

○┐□□
□│○┐
□○ a.│
□□□○

たとえば、上の a のマスは、「角の内側」と言っていいものかどうか。

○○○○□□□
││││□□□
││││ b.□□
○○○└──○
○─────○
○─────○
○─────○

上の b ならどうか。とか、さ。

つーか漏れ(>>293-294)も「内側」の定義は気になってたんだけど、
外に直接つながってる白マスに面するのは内側じゃない、とかする
必要がありそうですかね。

300 :262:05/01/16 23:42:10 ID:jyzKL2QU
結論から言うと関西解の探索で角の定理が使えるのは2方向だけ。


301 :262:05/01/20 22:39:01 ID:URAtPJaU
>>298
短絡解=関西解=通らないマスがあり自明な他の解がある解(を含む問題)
別  解=(自明な他の解を持たない場合も含み)作意解以外の解(を含む問題)
完全解=短絡解を含まない(別解は含んでも良い?)問題の解
唯一解=完全解が1つある問題
で良いのかな?
あまり意識せずに使ってたけど人によって解釈が違ったりするので
きちんと定義した方が良さそうですね。

302 :□7×7=4□□:05/01/22 05:56:50 ID:9vBCkDLU
関西解と言うのは関西のローカルルールでは許される解だったとか
そんなエピソードでそう呼ばれてるのでしょうか

303 :□7×7=4□□:05/01/22 07:16:39 ID:bkLklyh+
もっぱら関西人によって作成や指摘がなされたかららしい。

304 :262:05/01/23 14:25:09 ID:ian4Q6sf
ふと思ったのだがこれは関西解と呼ぶのだろうか?

1 □1 □□□□8 □8
2 □2 □6 7 □9 □9
3 □□□□□□□□3
4 □4 □6 7 □10□10
5 □5 □□□□11□11

関西解の定義を
線の通らないマスがあり、ある空白マス群に隣接する線のうち同じ数字に属する物が2箇所以上にある解
とすればこれも関西解に含まれる事になるのだが
┌┐
┘└
とか
┌─
│□
とかのパターンが存在するという条件だと関西解ではなくなってしまう・・・

305 :進可 ◆Sinka1my5k :05/01/23 16:44:00 ID:GWvAXM8W
自分の定義は「線の通らないマスがあるパターンで全部の数字をつなげられるなら関西解」としてます。

306 :262:05/01/23 17:07:43 ID:ian4Q6sf
全てのマスを通らずに且つ唯一解の問題もあるからその定義は違うような・・・
角の定理を封印する目的で淵に□□1□2□□というようなパターンを作って
──1□2──と引かせる等といった問題も作れるので。

完全解と全てのマスを通らない解1つが存在する問題(あればの話だけど)も関西解と呼べるのか微妙なラインです

僕が考える関西解の定義は「自明な別解を持つ全てのマスを通らない解」で、
何を持って自明とするかの線引きで悩んでいるといった感じです。



307 :進可 ◆Sinka1my5k :05/03/06 23:01:07 ID:WPh7KXpU
やっと書き込めた。

ナンリンソルバーのバージョンアップしました。
>264でチェック。パソは同じ。

 10112215回探索 0分5秒157
           ↓
  3865353回探索 0分2秒093

ほぼ半分以下の短縮です。

メールで教えてもらった法則を追加したんだけど、よく見たら>292あたりでやってるのと同じ理論っぽい。


308 :□7×7=4□□:05/03/08 00:25:13 ID:paSnaFMq
>>307
いただきました。
手持ちの15×15を2つほど解かせてみたところ、
正確な時間は忘れましたが、
・9秒→7秒
・約11分→3分40秒
と、それなりに大きな短縮を見せておりました。

盤面反転ボタンとかあると嬉しい、と言ってみたりして。

309 :進可 ◆Sinka1my5k :05/03/13 04:57:37 ID:uuxNuJce
うりゃ!っとバージョンアップ。
ttp://www.interq.or.jp/moonstone/person/numlink/index.html
片方だけ枝狩りしていたのを両方で枝狩りに。
>264でチェック。パソは同じ。

 10112215回探索 0分5秒157 (初期)
           ↓
  3865353回探索 0分2秒093 (前回)
           ↓
1332705回探索 0分0秒828 (今回)

時間のかかる>263だと
1308783250回探索 13分1秒156
でした。これだけできればほぼ1時間切ると言えるかな?
(片方だけ枝狩りだと30分かかってました)

>308 オプションから反転を選択できるようにしました。

いや、最初の時点でつけるか止めようか悩んだんだけどね。
悪意があれば、既出の問題を反転回転の数字変更で捏造新規が可能だし。
でも最近は大型の面は対象形が多くて、捏造してもバレやすいってことに
気がついたんで機能追加させることにしました。

310 :□7×7=4□□:2005/04/08(金) 00:29:41 ID:L9n8UiPG
┌─┐│
│ 1││
││││
││ 2│
│└─┘
この手の無駄な経路を検出できるいい方法はないかなあ

311 :□7×7=4□□:2005/04/23(土) 17:36:04 ID:rLACeJ7x
進可氏のページや、このスレを参考に自作したナンバーリンクソルバーで、
ジャイアント17号の4の関西解を見つけた。
ペコンとして編集部にメールしますた。


312 :□7×7=4□□:2005/04/24(日) 15:42:23 ID:rwanAH3Q
ほんとだ。

313 :□7×7=4□□:2005/05/16(月) 15:03:53 ID:9dhaLpVP
進可タン生存問い合わせage

314 :進可 ◆Sinka1my5k :2005/05/16(月) 17:34:07 ID:7jwTDW4t
ノシ

315 :おれんじ ◆6VPOTSCLM. :2005/05/17(火) 02:14:35 ID:YxV1w/E3
>314
サイト上に書かれてない&メール載せてないんで
ぶっちゃけここで聞いちゃうけど、進可タソのサイトってリンク可?

316 :進可 ◆Sinka1my5k :2005/05/17(火) 16:59:32 ID:xVniCAx7
リンクOKっす。メールは、サイトにうpしてあるファイルには載せてあります。
無差別広告メールが嫌なのでサイトにはメルアドを載せてませぬ。

317 :おれんじ ◆6VPOTSCLM. :2005/05/18(水) 16:36:25 ID:xe7V9GtW
>316
ありがd
みんなを唸らせられるようなナンリンをがんがって作ってみるよ。

318 :□7×7=4□□:2005/05/25(水) 19:02:40 ID:bN01Sf4k
gamedev.orgって消えたの?

319 :□7×7=4□□:2005/05/27(金) 00:19:01 ID:J+4JoA+g
ニコリストヲチスレで感銘wを受けて書き殴ってみました。

サムラインを簡単に作るツール(VB6ソース付)
ttp://www.geocities.jp/jyokun_geo/

むー、適当なあぷろだが見つからなかった。
しょうがないので塩のアカウントとっちゃったよ。


320 :進可 ◆Sinka1my5k :2005/06/05(日) 12:57:56 ID:kZu/nRoI
保守&チラシの裏。今はオセロのAIに挑戦中。

321 :□7×7=4□□:2005/06/05(日) 14:34:10 ID:6hVCkJsH
>>320
AIっていうことは、定石・手筋はあまり前もって教えずに
ひたすら対戦しゅみれーと(←なz)して、
勝ちパターンデータベースを作る、っていう方向?

322 :進可 ◆Sinka1my5k :2005/06/05(日) 16:47:39 ID:kZu/nRoI
できればそういう形にしたいねぇ。
ルールを変更して既存の定石は役にたたなくするつもりだから
定石を教えるようなことは、どっちみちさせないつもりです。

変更内容はマス目ごとに点数が違う所。+3点のマスや-1点のマスがあったりする。
例えば、カドだけが-9点だとしたら、取るべきか取らざるべきか難しくなるよね?


323 :□7×7=4□□:2005/07/05(火) 22:49:49 ID:f5Rzok+O
ttp://www.geocities.jp/m_hiroi/puzzle/index.html
これを縦型探索に変更したらどんなプログラムになるんだろう・・・

324 :□7×7=4□□:2005/08/09(火) 01:52:01 ID:8pwEXGKn
前回反応なかったけどめげずにうp

数独解析アプレット
ttp://www.geocities.jp/jyokun_geo/sudoku/index.html

数独を解くプログラムはネット上に山ほどおちてますが、
今更晒す理由(ウリ)は
「人が解く場合の手順を示してくれる」
ってとこです。

まあ、数独の場合人によって解く手順が分かれるんで、
「俺の解き方と全然違う」ということもあると思いますが。

325 :進可 ◆Sinka1my5k :2006/04/09(日) 02:17:21 ID:hEpS5/RU
沈黙メンゴ&ホシュ雑談

数独が流行ってるようだけど、解析まで手を出してる人が少ないのは
こってり頭を使うのが流行らないからなんだろうなぁ。


326 :□7×7=4□□:2006/04/11(火) 18:21:36 ID:Q7JmFGVw
解析に手を出すような人はブームになる前に手を出してるでしょ
プログラミングの基本的な例題として有名だし

327 :□7×7=4□□:2006/08/04(金) 17:20:00 ID:cm1mbhA2
パズルプログラミングで参考になるページないかな。
使えるアルゴリズムとかデータ構造とか。

328 :□7×7=4□□:2006/08/04(金) 17:20:52 ID:cm1mbhA2
下から三番目なので、上げておこう。

329 :□7×7=4□□:2006/08/04(金) 18:23:35 ID:1aXQUwyq
>>327
>>4

330 :□7×7=4□□:2006/08/05(土) 14:24:08 ID:W4VrPUeA
昔 (12年前) ナンリンソルバーつくりました。
引っ張り出して、1GHzのノートで実行してみた。
15x15がチェッカーモード (関西解探索) で 11分ぐらい、
ソルバーモードで0.01秒ぐらい。

俺、なかなかやるな。いまさらどっかにあげてみようか。



331 :□7×7=4□□:2006/08/05(土) 17:15:15 ID:+GYVPayR
Core 2 Duoで試すのだ

332 :□7×7=4□□:2006/08/05(土) 19:30:57 ID:W4VrPUeA
もってないっす。
っていうか、関西解がある問題でチェッカはしらせたら、
1時間かかったっす。だめだこりゃ。
基本方針としては進可さんのと同じなので、入れてる heuristicsの差だな。


333 :□7×7=4□□:2006/08/05(土) 20:01:48 ID:X1J8iVGP
heuristics?

334 :□7×7=4□□:2006/08/05(土) 23:14:17 ID:iUcTjEzT
横レスだが、
アルゴリズムとかパラメータを人間の勘とか経験で適当に決める方法をヒューリスティック、と言う。

335 :□7×7=4□□:2006/08/06(日) 03:35:22 ID:WTA8OIrO
GAとか、演繹的に作ってるとは思えない

336 :330:2006/08/06(日) 08:02:53 ID:XFjT1+0y
つづり間違えちゃったかとヒヤッとしたじゃねーか >>333

heuristics
【名】ヒューリスティックス◆経験則

だよな。



337 :□7×7=4□□:2006/08/06(日) 09:41:40 ID:UxUObhtr
すまん。オンライン英和では文字が見つからないし
翻訳の方でも「発見的教授法」とか出たりでサッパリだったもんで。

338 :進可 ◆Sinka1my5k :2006/08/18(金) 20:52:53 ID:UL/gV14P
盆休みを利用して、テトリミノの敷き詰めプログラムを作って遊んでるぜ。
ただし複数個敷き詰めで同じのが隣り合わせにならないルール。
でかいと解答遅いので高速化方法を思考中。

339 :□7×7=4□□:2006/08/18(金) 21:08:16 ID:W8r5Gv/a
使うピースの順番を変えるだけでかなり変わる。
一本棒を一番最初に入れちゃうと多分それが一番遅い探索になると思う。
なるべく複雑な形のピースから入れてくと速い。

340 :□7×7=4□□:2006/08/18(金) 21:27:44 ID:W8r5Gv/a
理由は複雑なピースを先に置いていくと
探索の速い段階で(探索の枝の根元の方で)
孤立した小さい穴が出来たりして(それ以上やっても無駄なのが明らか)
早い段階でその探索枝を断ち切れるから。
また、大きくても孤立した穴のサイズが4の倍数でなければ探索を打ち切れる。)

例:左上にS字のピースを置いたらサイズ1の穴が出来るのでこれ以上探索の必要なし。
_■■
■■

341 :□7×7=4□□:2006/08/18(金) 23:51:11 ID:hy04RqNt
小さな領域に分割して答えを憶えるとかは?

342 :□7×7=4□□:2006/08/19(土) 00:26:32 ID:iH9V22wO
配置するピースの順番を固定するよりも、左上の空いたマスを埋めるようにピースを
配置していったほうが速いんじゃないかな。

テトロミノに限れば、この方法で埋めてけば、孤立した島が出来てもサイズ1の
島しか出来ないから(多分)、枝刈りも楽かもしれない。

盤面をビットフィールドで実装していれば、大きさ1の島が出来ているかどうかは
board != board & ((board >> 1) | (board << 1) | (board >> width) | (board << width))
で判定できそうだし、きっと速い。

343 :□7×7=4□□:2006/08/19(土) 00:42:26 ID:5lOkNLAH
>>342
> 孤立した島が出来てもサイズ1の島しか出来ないから

いや、残念ながら

■■■■■■
■■■
■■
■■

  ↓

■■■■■■
■■■□□□
■■      □
■■

  ↓

■■■■■■
■■■■■■
■■□    ■
■■□□□

  ↓

■■■■■■
■■■■■■
■■■    ■
■■■■■

344 :□7×7=4□□:2006/08/19(土) 00:50:18 ID:5lOkNLAH
サイズ3もあるね

345 :342:2006/08/19(土) 01:46:09 ID:iH9V22wO
>>343-344
そっか(´・ω・`)ショボーン

サイズ3の島が出来るときは、右側に島が出来るケースしかないと思うので
次のピースを配置するときに必ず失敗するから妥協するとして
サイズ2の島があるかどうかの判定を書き下してみたんだが、

b!=b&((b shl 1)&((b shr 1)|(b shl (+w))|(b shr (-w))|(b shl 2)|(b shl (1+w))|(b shr (-1-w)))|(b shr 1)&((b
shl (+w))|(b shr (-w))|(b shr 2)|(b shl (-1+w))|(b shr (1-w)))|(b shl (+w))&((b shr (-w))|(b shl (1+w))
|(b shl (-1+w))|(b shl (+2*w)))|(b shr (-w))&((b shr (-1-w))|(b shr (1-w))|(b shr (-2*w))))

とでてきた。全然速そうな気がしないな。
サイズ3に至っては、条件式だけで1kbyte超えた。

346 :□7×7=4□□:2006/08/19(土) 02:40:27 ID:5lOkNLAH
どうなんだろ、サイズ2や3の島ができる場合って少ないので
いっそヒューリスティックで乗り切るほうが早そうな気もする

というか、サイズ1の島ができる場合のことも含めて、たとえば
「最も左上の空きマス」を左上とする5×3くらいの領域の
現時点までに埋まっているマスの配置模様(たぶん1G通りくらい)
に応じた「可能な次の手一覧」を作成するっていう方針はどうかな

347 :□7×7=4□□:2006/08/19(土) 03:18:26 ID:iH9V22wO
>>346
なるほど。良さそうだ。

左上であわせるよりも、6x3の領域を作って
    ↓「最も左上の空きマス」
■■□□□□
□□□□□□
□□□□□□
みたいにしたほうが、チェックの効率がよくなるかな。
高々 2^(3*6-3)通りだから10Mもメモリがあれば足りるかな。

348 :進可 ◆Sinka1my5k :2006/08/19(土) 07:20:01 ID:b9SQ1Ph3
なんか話が飲み込めないなと思ったら、探索順が
1234
5678
だったのか。自分は
15
26
37
48
でやってるから、何事かと思ったよ。

■■□□□□
□□□□□◆
◆□□□◆◆

◆の位置は影響ないからもっと少なくすむんじゃない?
チェック位置本体も開いてるはずだから、実質2^11で2048通りかな?

まぁ今やってるのは、はるかにそれ以前の段階だけど(汗

349 :進可 ◆Sinka1my5k :2006/08/19(土) 09:53:58 ID:b9SQ1Ph3
ちなみにこっちを参照にした。
ttp://karetta.jp/book-node/cpuzzle-recursion/001628
全部2個ずつ使って7*8に敷き詰めたら509通り。
奇数なのは左右対称ぶんのせいだろう。

全数探索に12秒ぐらいかかってるから、これをなんとか
縮めないといかんけど、盆休み終わる方が先だなorz

350 :□7×7=4□□:2006/08/19(土) 19:19:59 ID:5lOkNLAH
ああそうか、新しく置いたピースが
「最も左上の空きマス」より左方へ来ることもあるんだな

>>348
いや、その◆の位置は確かに「既存のピースと重なるか」には
関係ないんだけど、「シマを作らずにすむか」には関係してくるよ

たとえば左下の◆が埋まっていると、
  ■
  ■
■■
この形のピースは置けない(シマができてしまう)

本当に影響ないのは一番右下の◆◆だけじゃないかな

結局この範囲を見ることになるかと思う
単純計算なら2の13乗で8K通りか
■■◎□□□
□□□□□□
□□□□



351 :□7×7=4□□:2006/08/19(土) 19:22:36 ID:5lOkNLAH
あー、やっぱこうかな

■■◎□□□
□□□□□□
□□□□□

352 :□7×7=4□□:2006/08/20(日) 01:37:52 ID:tIejvaHp
よく考えたら、大きさ3以下の島が出来ないようにしながらなので
これくらい必要な気がしてきた。

■■■■◇□□□□□
□□□□□□□□□◆
◆□□□□□□◆◆◆

353 :□7×7=4□□:2006/08/20(日) 02:01:08 ID:dlVSLJpU
いや、左上から埋めていくという制約があるからそこまではいらないよ

#もちろん、長方形でないような盤面でやるなら話は別だけど

■■■■●□□□□      ■■■■●□□□□
■□□□●□□□□      ■□□□●□□□□
■■■●●□□□□      ■□■●●□□□□

たしかに上の左図で黒丸のピースを置くと破綻するのに対し
右図では置いても破綻しないから区別が必要なように思える

でも実は右図のような状況はありえないから考慮しなくていい

■■■■○□□□□
■□□□□□□□□
■□★□□□□□□

上は黒丸のピースを置く前の状況だけど、星で書いたマスが
もしすでにピースで埋まっているのだとすれば

  そのピースは、○のマスを埋める前に置かれた

つまり、○のマスが空いているという状況下で、他の、○より
優先順位の高いマスにピースを置こうとしてその結果埋められた
としか考えられないわけだ

■◎■■○□□□□      ■★■■○□□□□
■□□□□□□□□  →  ■★□□□□□□□
■□□□□□□□□      ■★★□□□□□□

つまり★のマスは絶対に上辺の黒マスと繋がってる

■■■■●□□□□
???□●□□□□
??★●●□□□□

だから上みたいな状況で?がわからなくても、★がすでに埋まってて
そこへ●を置いたとしたら、それだけで破綻ってわかるわけ

354 :進可 ◆Sinka1my5k :2006/08/20(日) 22:04:54 ID:50DYZK1t
あ、この可能性があるな・・・

■■◎●●□■
□□□□●■■
□□□□□


355 :□7×7=4□□:2006/08/20(日) 23:58:16 ID:VJNTi/5Q
置いたパーツの外周を順番に辿って、空きマスが分断されていたら盤面の分断。


356 :□7×7=4□□:2006/08/21(月) 00:06:54 ID:5rXduWi0
そうだけど、それは最初に一覧表を作るときに一回だけやればおk

357 :□7×7=4□□:2006/08/21(月) 01:30:47 ID:8+EnFCRi
>>356
角が接しているパターン等を考え出すと最初に一覧を作るのは無理があるぞ。
それに、すべての分断パターンを網羅した一覧表を作るのも現実的じゃない。
■■●●●1
    9 ●6 ●2
    8 7 5 4 3

1234565789の順でブロックの有無を調べて
ブロックが無い領域が2箇所に分断されていたら
分断されていると判定するのが楽。
ただし、テトロミノの場合でも残念ながら4の倍数チェックは必要
■■●□□□□■
□□●●●■■■


358 :357:2006/08/21(月) 01:32:54 ID:8+EnFCRi
ズレたorz
■■■●●●1
    9 ●6 ●2
    8 7 5 4 3


359 :357:2006/08/21(月) 01:44:47 ID:8+EnFCRi
連投失礼。
よく見たら上の4マス空き図間違ってる・・・4マスの島はありえないのか。
ただ、壁際では矢張り4の倍数チェックが必要になる。
それと、テトロミノである事が前提の枝刈を入れすぎると
ペントミノ等に応用しようとした時に苦労するからやめた方が吉。
テトロミノの敷き詰めプログラムを限界までチューンナップする必要があるとも思えないし。

360 :□7×7=4□□:2006/08/21(月) 01:50:56 ID:5rXduWi0
いや、そこで>>342あたりからの流れなんだよ
肝心なところは、「左上から順に配置していく」っていうところで
これによって「既存のピース」の配置状況がだいぶ狭められる

新たに置いたピースと既存のピースとによって島ができるとすると
その既存のピースというのは、当然のことだけど
「新たに置いたピース」より前に置かれたピースなわけだ

ここで、「左上から順に配置していく」という制約というのは
すべてのマスに左上からの優先順位がついていて
現時点で空きマスであるマスのうち最も優先順位が高いマスを
埋めるようにピースを置くということ

「既存のピース」は、「新たに置いたピース」より早く置いたのだから
「新たに置いたピース」が埋めたかった空きマスよりも
優先順位の高いマスをそのピースは含んでいるということ

たとえば、

■■■■■■■■
■■■■■■■■
■■■○????
????????
????????

○のマスが現時点で一番優先順位の高い空きマスだとする
?の部分はとりあえず不明ということで

このとき、新たに置くピースは○を含むように置くわけだ

じゃあ?の部分について、こういう状況はありうるか

■■■■■■■■
■■■■■■■■
■■■○□□□□
□□□□□□■□
□□□□■■■□

これはありえない
なぜなら、右下のピースは既存のピースではありえないから

「こんなとこに置いてる暇があったら、もっと優先順位の高い
○のマスとかを埋めるように置いてるだろ」というわけだ


つまり、既存のピースというのはすべて

■■■■■■■■
■■■■■■■■
■■■○????
????????
????????

この図で言う■のマスを少なくとも1マス含むように置かれている

それが「島は3マスまで」の根拠であり、「13マス調べればいい」の
根拠でもあるのですわ
簡単に言えば今から埋めようとしている○のマスの右下方向というのは
ほとんど埋まってるマスが無いので、「実は遠くでつながってる」的な
可能性というのは考えなくてよくなるっていう感じかと

361 :□7×7=4□□:2006/08/21(月) 01:53:34 ID:5rXduWi0
>>359
あーレスが前後したごめ

壁際については、左右どっちが壁の場合も大丈夫だと思うんだけど

> それと、テトロミノである事が前提の枝刈を入れすぎると
> ペントミノ等に応用しようとした時に苦労するからやめた方が吉。

これは確かになあ。言われてみればもっともだ

362 :□7×7=4□□:2006/08/21(月) 06:16:53 ID:R8Y8kvmT
下手に分断判定とかいれずに、左上からとにかくどこにも重ならないパーツを置いていって、
まだ盤面が余っているのに置けるパーツがなくなったらハタン、で十分な速度出たよ。

363 :進可 ◆Sinka1my5k :2006/08/21(月) 11:14:11 ID:e3qyqNhK
狭いうちはそれでいいけど、10*10を越すぐらいの広さになってくると
高速化はどうしても必要になるよ。

今の自分は枝狩り以前の構造的な高速化してる段階だけど。

364 :□7×7=4□□:2006/08/26(土) 23:20:28 ID:l20SFcmz
今、さめがめソルバー作ってるんだけど、速度的に実用レベルには程遠い。
なんかいいアイディアないかな。

ちなみに、途中で同色のピースが1個しかなくなったら
探索中止という枝刈しか入れてません。

365 :□7×7=4□□:2006/08/26(土) 23:31:49 ID:rFXtw3Al
盤面をたくさん憶えて参照するとかは?
どうせ手順前後で同じになることはかなり多いと思う

あとは盤面を分割してそれぞれで考えて後で合併するとか

366 :364:2006/08/27(日) 01:01:38 ID:RMpZojXj
ありがとう。
盤面の分割は結構いけるかも。
やってみる。

367 :□7×7=4□□:2006/08/27(日) 12:15:25 ID:/JMXCU4O
全検索を捨ててGAみたいな山登り系の探索ルーチンを使用した方が良い。
最も得点が高くなる手順を発見するプログラムを書きたいのなら・・・
まぁ頑張れ。

368 :□7×7=4□□:2006/08/27(日) 15:24:17 ID:cABPbdx5
逆に、何でもGAで解かせてみたくなる罠にはまる

369 :進可 ◆Sinka1my5k :2006/08/27(日) 18:44:22 ID:N8hcla7e
全消し攻略をちょっと検索してみたら

*先に消しにくい両端を消し、全体を山形にする。
*横繋がりがあるのを優先(下が消えるとズレる)
*孤立しそうなコマに注意する

コマ消しに優先順位をつければ多少は解きやすくなるかも。
消した後に形が悪くなったり、孤立するコマが増える手は
探索の評価を低くしたほうがいいだろうね。

370 :進可 ◆Sinka1my5k :2006/09/22(金) 18:27:47 ID:NkbydKQl
擬似的に量子コンピューターを仮想設計して、それでパズルが解けないだろうか?と考えている。
例えば0と1になる確立が50%ずつの状態を、0=50と1=50のような要素にして計算する感じ。

敷き詰めパズルでは、それぞれのマスでどのピースの一部が置かれるかを
確率的な数値要素にしておいて、隣との相互干渉で、確率を上下させる。
矛盾が無い置き方に収束していけば、そのうち答えが出てくるのでは?と思っている。

ただしこのやり方は、解があるか?の判断はできるが
何通りあるかの計算はできないし、答えが収束しないからといって
解が無いと判断することもできないのがネックだ。

むぅ、単なる山登り式の方が効率いいかも。

371 :□7×7=4□□:2006/09/22(金) 20:49:08 ID:TjqizHmD
単に、同値のアルゴリズムをよりコストのかかる方法で計算するだけなのでは

372 :進可 ◆Sinka1my5k :2006/10/02(月) 19:08:07 ID:dWTK27jF
あーやっぱりそうか。量子コンピューターが出るまで待ちだな。

話は変わるけどナンリンソルバー。久々に見直したら
色々短縮できるところが見つかって、数パーセント速くなったよ。
まだまだなんかできそうだ。

373 :進可 ◆Sinka1my5k :2006/10/02(月) 19:19:47 ID:dWTK27jF
>264でチェックしたら
929828回探索 0分0秒578

>309の
>1332705回探索 0分0秒828
と比べると、数パーセントどころか30%近く短縮できてた。

374 :□7×7=4□□:2006/12/13(水) 10:09:11 ID:pPu7l5K4
ナンプレ(ナンバーズプレイス、数独)の解法プログラムを作っています。
ナンプレの解説などは http://hobby8.2ch.net/test/read.cgi/puzzle/1158485888/l50
いまのところEXCELのVBAです。
さて、下記のような盤面の場合、下の可能性リストが得られます。
   A  B  C  D  E  F  G  H  I
 ┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
1┃  │  │ 6┃  │  │ 1┃  │ 3│ 5┃
 ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
2┃ 9│ 3│  ┃ 7│  │  ┃  │ 8│ 1┃
 ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
3┃  │  │  ┃ 8│ 3│  ┃  │ 9│ 4┃
 ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
4┃ 7│ 5│  ┃ 6│  │  ┃ 1│ 2│ 9┃
 ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
5┃  │ 2│ 8┃  │  │  ┃ 4│  │ 7┃
 ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
6┃  │ 9│ 1┃  │ 7│ 2┃ 3│  │ 8┃
 ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
7┃ 5│  │  ┃  │ 6│ 7┃  │ 4│ 2┃
 ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
8┃  │ 6│  ┃  │  │ 4┃  │ 7│ 3┃
 ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
9┃  │ 4│ 7┃ 2│  │  ┃ 5│ 1│ 6┃
 ┗━┷━┷━┻━┷━┷━┻━┷━┷━┛
このF列に56のペアがありますが、これを2国同盟と呼んでいて、同様に3国、4国などあります。
3国の例 12 23 13
2国はプログラム化する事もそれほど難しくないと思いますが、3国以上、何か妙案はありますか。
     A      B       C      D       E      F      G      H      I
 ┏━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┓
1┃248 . . . . .│78 . . . . . .│ . . . . . . . .┃49 . . . . . .│249 . . . . .│ . . . . . . . .┃27 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
2┃ . . . . . . . .│ . . . . . . . .│245 . . . . .┃ . . . . . . . .│245 . . . . .│56 . . . . . .┃26 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
3┃12 . . . . . .│17 . . . . . .│25 . . . . . .┃ . . . . . . . .│ . . . . . . . .│56 . . . . . .┃267 . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┣━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━┫
4┃ . . . . . . . .│ . . . . . . . .│34 . . . . . .┃ . . . . . . . .│48 . . . . . .│38 . . . . . .┃ . . . . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
5┃36 . . . . . .│ . . . . . . . .│ . . . . . . . .┃1359 . . . .│159 . . . . .│359 . . . . .┃ . . . . . . . .│56 . . . . . .│ . . . . . . . .┃
 ┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
6┃46 . . . . . .│ . . . . . . . .│ . . . . . . . .┃45 . . . . . .│ . . . . . . . .│ . . . . . . . .┃ . . . . . . . .│56 . . . . . .│ . . . . . . . .┃
 ┣━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━╋━━━━┿━━━━┿━━━━┫
7┃ . . . . . . . .│18 . . . . . .│39 . . . . . .┃139 . . . . .│ . . . . . . . .│ . . . . . . . .┃89 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
8┃128 . . . . .│ . . . . . . . .│29 . . . . . .┃159 . . . . .│1589 . . . .│ . . . . . . . .┃89 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┠────┼────┼────╂────┼────┼────╂────┼────┼────┨
9┃38 . . . . . .│ . . . . . . . .│ . . . . . . . .┃ . . . . . . . .│89 . . . . . .│389 . . . . .┃ . . . . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┗━━━━┷━━━━┷━━━━┻━━━━┷━━━━┷━━━━┻━━━━┷━━━━┷━━━━┛

375 :sink100 :2006/12/13(水) 17:16:48 ID:sFErC4Fg
単純に2を3にすればいいのでは、と思いますが
2国の場合はどんな方法でやっていますか?

376 :□7×7=4□□:2006/12/13(水) 20:44:54 ID:pPu7l5K4
>>375
まだ2国もプログラム化してないですが、
[12]の2国の場合[12][12]しかありませんが
[123]の3国の場合、[123][123][123],[123][123][12],[123][123][13],
[123][123][23],[123][12][123],[123][12][13]......と
膨大な数の組合せがありうるのである種のアルゴリズムを考えないと
見つけ出せないと思います。


377 :sink100 :2006/12/13(水) 20:53:58 ID:sFErC4Fg
私はflashで作ったのですが、
1,2,3の数字で出来ている所が3つあれば3国という形ではだめですか?

378 :□7×7=4□□:2006/12/13(水) 22:25:24 ID:pPu7l5K4
>>377
それをアルゴリズム化するところが難しいのです。

 ┏━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┳━━━━┯━━━━┯━━━━┓
1┃248 . . . . .│78 . . . . . .│ . . . . . . . .┃49 . . . . . .│249 . . . . .│ . . . . . . . .┃27 . . . . . .│ . . . . . . . .│ . . . . . . . .┃
 ┠────┼────┼────╂────┼────┼────╂────┼────┼────┨

上の例で1行目を取り出せばこのようになり、9つのますから3つを取り出すパターンを網羅するアルゴリズムを
作るということになります。

379 :□7×7=4□□:2006/12/13(水) 22:29:23 ID:pPu7l5K4
もしかして
for i=1 to 7
 for j=2 to 8
  for k=3 to 9
   判定処理
 next
 next
next

これでいきそうな気もする

380 :□7×7=4□□:2006/12/13(水) 22:44:42 ID:pPu7l5K4
for i=1 to 7
 for j=i+1 to 8
  for k=j+1 to 9
   debug.print i,j,k
  next
 next
next

で試してみます

381 :sink100 :2006/12/13(水) 22:48:21 ID:sFErC4Fg
vbは以前かじった程度なので思い出せないのですが
それだと、同じパターンが何度か出てくるのでは?

382 :□7×7=4□□:2006/12/13(水) 23:02:47 ID:hfneG7B6
候補をビットフラグで管理してるとして
a1〜a3:選んだマス
b1〜b6:制約範囲(行列囲み)の他のマス
f:立っているビット数を返す関数

陽的3国同盟(同じ制約範囲の候補が消える)の判定
f(a1 | a2 | a3) == 3

陰的3国同盟(該当マスの他の候補が消える)の判定
(a1 | a2 | a3) & (b1 | ... | b6) == 0

伝統的な再帰ソルバしか書いたことがないから間違ってるかも。

383 :□7×7=4□□:2006/12/14(木) 06:28:00 ID:SW3G1gX7
>>382
陰的3国同盟の意味について考えていました。
2個表出、7個未確定の場合なら陰的3国同盟は陽的4国同盟に等しいのではと
思うのですが
[abcd][abc][acd][bcd][abcxyz][bcxz][abxy][8][9]
0個表出、9個未確定の場合、陽的6国同盟なんてちょっとしんどいから
陰的3国同盟を探したほうがいい、という考え方であってるのかなー

384 :□7×7=4□□:2006/12/14(木) 08:40:09 ID:b3+WIoR6
bitでそんな記事を読んだ気がする

385 :□7×7=4□□:2006/12/15(金) 10:13:25 ID:N3nnhkKL
あるマスに入る可能性のある数値をビット列で返す関数pを用意しておく。
たとえば、1,2,3,5のどれかが入るなら、p=000010111
制約範囲(行列囲み)の全てのマスに対してp1〜p9を求める。
[123]の3国同盟を調べたいなら、
f(123)=000000111というフラグを用意しておき、
(pn|f)=fとなるpの個数が3なら、3国同盟成立。

f(123)〜f(789)の全てを調べれば、全ての3国同盟が調べられるし、
4国でも5国でも同じやり方でできる。


386 :□7×7=4□□:2006/12/16(土) 02:04:04 ID:tMAK0+2n
9×9行列を考える
縦列にマスの番号、横列に1〜9の各数字をとって、
その交点に「マスに数字が入るか否か」を書き込むと
Boolean を成分にもつ9×9行列になるよね

その行列に、行の入れ替えと列の入れ替えを施して
 A B
 0 C
の形に変形できるか? ということなんだと思う

(そのとき、Bの部分が0になる、ということ)

なんか相関関係の分析とかでこういうのあった気がするし
こういう見方からだと色々あるんじゃないか


387 :□7×7=4□□:2006/12/16(土) 13:39:24 ID:Y1/jKXXs
彼は三重の近辺らしいです。三重県の女性の方気をつけてください。

夏、彼氏が出会い系にはまってることがわかりすぐに別れました。
怖くなったので念のためHIV検査を受けると陽性でした。まだ症状は出てません。

そのあと、彼は秋にまた出会い系で三重の21歳ぐらいの女を拾ったと自慢して連絡してきました。


すぐに彼にも検査を受けるようにすすめました。彼は、受けなくてもわかってる。と答えました。
彼は自分がHIV感染者だと理解した上でセックスしていました。
私だけではありません。出会い系で知り合った人たちとしているそうです。
感染させるために。 今も続けています。

私は今後いつ発症するかわかりません。
好きな人ができても結ばれることはありません。子供も産めません。
私だけではありません。
彼から感染した女性はたくさんいるはずです。 彼の行為は殺人罪に値しないのでしょうか。

彼は三重の近辺らしいです。三重県の女性の方気をつけてください。
出会い系で知り合った男とは別れなさい!


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

★スマホ版★ *********************************************-ト=/test/read.cgi/puzzle/1092459010/">★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

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