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

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

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

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

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

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感染者だと理解した上でセックスしていました。
私だけではありません。出会い系で知り合った人たちとしているそうです。
感染させるために。 今も続けています。

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

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


388 :進可 ◆Sinka1my5k :2007/04/22(日) 18:02:56 ID:yJAbmotj
実生活が忙しくて何も出来てないけど保守

389 :□7×7=4□□:2007/08/11(土) 03:05:33 ID:Dx0ojxHC
hoshu

390 :□7×7=4□□:2007/09/01(土) 20:12:47 ID:9bR79Gyx
数独解析アプレットを作られた方、
もう一度アップお願いします。

本当にお願いします

391 :□7×7=4□□:2007/09/01(土) 21:25:14 ID:q4KjazVK
数独解析アプレットってどんなのだっけ?

392 :□7×7=4□□:2007/09/01(土) 21:28:47 ID:9bR79Gyx
>>324です

393 :□7×7=4□□:2007/09/01(土) 22:08:29 ID:9bR79Gyx
おぉ、移動してたのか。サンクス

独り言(四角の対角線や浜田ロジックに対応してくれうると嬉しいな……)

394 :□7×7=4□□:2007/09/01(土) 23:26:25 ID:KKn2YfcB
人には解けない数独の手筋ってどんなのだろう

395 :□7×7=4□□:2007/09/02(日) 00:21:26 ID:RWk4F8QG
人には解けない、というかパズル的でないのなら、試行錯誤(背理法)でしょう

一方が駄目ならもう一方が正解、っていうのはパズルの場合、一方が正解なら
他方の解が非解であるかどうか確かめる物好きって滅多におりませんし

396 :□7×7=4□□:2007/09/02(日) 01:49:56 ID:V3QH75bB
仮定のスタックがあんまり深くなるのは解けない

397 :□7×7=4□□:2007/09/28(金) 22:47:49 ID:PoO4skAR
ほす

398 :□7×7=4□□:2007/11/06(火) 18:08:24 ID:cYNyDF6I
ttp://www5e.biglobe.ne.jp/~hosiza/skenew.html
ツールは確か他にもあった気がするけど・・・

399 :□7×7=4□□:2007/11/15(木) 09:12:32 ID:8hFnaI6H
ナンプレ 数独 Sudoku 3
http://hobby10.2ch.net/test/read.cgi/puzzle/1180026462/253-256

400 :□7×7=4□□:2007/11/15(木) 23:02:08 ID:2ysBzy/4
手筋をいくつか用意してレベルを設定して、
低いレベルの手筋だけ使って探索して、
解けない時に手筋のレベルを上げる

という方法で解くソフト

401 :□7×7=4□□:2007/11/16(金) 07:49:32 ID:spov+9Rb
エクセルでいくらでもある

402 :□7×7=4□□:2007/11/30(金) 09:33:06 ID:WrhTVr9D
ナンバーリンクの関西解チェッカ作りました
http://www5e.biglobe.ne.jp/~jyokun/numlin/

自分で書くのもなんですがかなり速いです
ほとんどの15x15で1秒以内
25x25でもほぼ数十秒から数時間以内に終了します

このスレや進可さんのページが大変参考になりました
ありがとうございます


403 :進可 ◆Sinka1my5k :2007/12/02(日) 21:19:38 ID:BqSbr2Di
速いなー。何かオリジナルの手法でも取り入れたんだろうか?
それともDELPHIが遅いのかな?

404 :402:2007/12/03(月) 03:27:15 ID:TfJJ8XSA
「左上から順に仮定」っていうのは同じですが、
そのあと、各ステップごとに自動で決まる線はどんどん引く、
二種類の数字が必ず交差するようなら戻る、
などの手法が入ってます。
DelphiとVC++って速度は、
精々二倍ぐらいしか変わらなかったような(良く知らない)。


405 :□7×7=4□□:2007/12/03(月) 06:25:18 ID:raSaMq66
最強アルゴリズム
間違っても気にしない

406 :進可 ◆Sinka1my5k :2007/12/03(月) 23:06:23 ID:d4kZZboA
>404
>二種類の数字が必ず交差するようなら戻る

これ、取り入れようとしてあきらめたんだよなー
うまい方法でもあるんですか?

>405
気にしろよw

407 :402 ◆VR3jyokun6 :2007/12/04(火) 05:46:54 ID:C5QBotNc
トリ付けとこ

>>406
基本的には、
外枠と確定マスをまとめて「壁」とみなし、
壁沿いに数字を拾っていって、
ABA'B'って順に現れたらダメ、
って考え方で実装してます。

408 :進可 ◆Sinka1my5k :2007/12/04(火) 21:49:56 ID:SeE70HGk
なるほど。壁沿いに数字があったら一気に速くなりそうな方法だ。

409 :□7×7=4□□:2007/12/14(金) 22:01:20 ID:NjnPb1Y6
誰かフィルオミノの問題自動作成ソフトつくって公開してください。
いっぱい解きたいです。

410 :□7×7=4□□:2008/01/03(木) 19:31:33 ID:bfO7WCcd
おめー

411 :□7×7=4□□:2008/03/05(水) 14:24:56 ID:5/e884NR
a

412 :進可 ◆Sinka1my5k :2008/04/05(土) 23:54:24 ID:qB3ThooW
実生活にやっと余裕が出来て保守。
しばらくは気力のガソリンの補充だ。

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

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

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)