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

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

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

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

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

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
■ このスレッドは過去ログ倉庫に格納されています

>>782>>784
>>807>>813-818>>829>>845>>852
>>854>>860★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50


read.cgi ver 05.05 2022/08/31 Walang Kapalit ★
FOX ★