ホームページへ戻る  書き込みリストへ戻る
「コンピュータ&パズル」訪問者の自由メッセージコーナー

お気づきの点や感想要望などなんでもOK!


re:ブラックボックスの解を最短で見つける   投稿者:major  投稿日:08月21日(水)00時34分55秒

高橋さんがつくられたプログラムを独自ルールの方で動かさせていただいたのですが
PCが固まってしまうのはなぜでしょうか?


re:ブラックボックスの解を最短で見つける  投稿者:major  投稿日:08月20日(火)10時03分28秒

高橋さん、としひでさん本当にありがとうございます。

今回は見ず知らずの自分にいろいろと教えていただきありがとうございました。
もう少し勉強して自分なりに理解を深めたいと思います。もしまたわからないこと
がありましたらお世話になるかもしれません。
ありがとうございました。


re:ブラックボックスの解を最短で見つける 投稿者:高橋謙一郎  投稿日:08月19日(月)23時06分27秒

一応、私の書いたプログラムも下に置いておきます。

ミニマックス法まで組み込まれていますが、提示された例題を解くだけなら
ミニマックス法の反復深化部は起動されません。(main()内の設定は例題を解く)

../temp/blackbox.c


re:ブラックボックスの解を最短で見つける 投稿者:としひで  投稿日:08月19日(月)22時13分06秒

組み合わせnCrを計算しています。
盤面board[0..n-1]中からボールを置く場所を設定します。
n:今見ているboardの位置。
r:あと幾つボールを置くか。
選択肢としては、board[n]にはボールを置くか置かないかの二択。
置けるためには、r>0でなければなりません。
そうやってboard[n],board[n-1],...,board[0]にボールを置く置かないを決めて行き、
n<0になった時点で盤面を全て見終わったことになります。
もし、ちょうどr=0になっていれば、次のステップ(check)に進みます。

突貫で作ったので、コメントがなく直接数値を書くなど、
作りがひどいですのであまり参考にならないかもしれませんが。


re:ブラックボックスの解を最短で見つける   投稿者:major  投稿日:08月19日(月)17時25分56秒

たびたび申し訳ありません。としひでさんが教えてくださったプログラムを動かして
実際答えがでることは確認したのでが、ソースを解釈しようとしたところいきなり
つまづいてしまいました。combination関数では何が行われているのか何回読み直しても
よくわかりません。(再帰関数はわかるのですが)あとcheck関数についてもどう汎用化し
ていいのかつまづいています。よろしかったら助言をお願いします。
 


re:ブラックボックスの解を最短で見つける  投稿者:major  投稿日:08月16日(金)10時10分34秒

いろいろと教えていただき本当にありがとうございます。
自分が考えているインターフェイスとしては
(入力位置,出力位置)をプログラムに入力という動作を何回か繰り返し
答えが求まった時点で終了といってことを想定しています。


re:ブラックボックスの解を最短で見つける 投稿者:高橋謙一郎  投稿日:08月16日(金)09時00分25秒

> 最短ということから離れて入力位置と出力位置の情報から答えを求めるということ
> だけを考えた場合はとしひでさんが示してくださった方法でやればよさそうですかね。

この質問の意味を取り違えたかも知れません。時系列的な解答者と返答者のやりとりを
考えずに始めから光の入力位置を総て指定する方法のことを言っているのでしょうか。

例えばオリジナルルールでボール1個の場合は、2,3,6,7の4箇所に光をあてれば
必ずボールの位置が判ります。この場合はたまたま最短4手と同じ4箇所という結果には
なりますが、確かにこの方法だと一般的には最短の保証は無くなります。
こういう方法を採用するとなれば私ならヘボイ方法かも知れませんが、こんな感じです。

for (入口の個数=1〜) {
    for (総ての入口の組合せについて) {
        for (総てのボール配置について) {
            それぞれの出口を求める
            if (ソルバー関数() == 重複解あり) break;
        }
        if (総てのボール配置について重複解がない)
            return 発見;
    }
}


re:ブラックボックスの解を最短で見つける 投稿者:高橋謙一郎  投稿日:08月15日(木)21時06分42秒

> 最短ということから離れて入力位置と出力位置の情報から答えを求めるということ
> だけを考えた場合はとしひでさんが示してくださった方法でやればよさそうですかね。

その通りですね。この部分は最短解をミニマックス法で得るプログラムのサブルーチン
として使えるでしょう。(check()関数を汎用化させる必要はありますが)

ところで、オリジナルルールの場合,ボール2個の最短手数は5手(探索時間 1時間40分)
と判明しました。ここで、ボール3個の場合はどうしても解を特定出来ないパターンが
見つかりました。(下図はその例で入口→出口の関係は総て同じになる)
結局、このパズルはボール2個までしか対応していないことになります。

    32 31 30 29 28 27 26 25
  1 口 口 ● 口 口 口 口 口 24
  2 口 口 口 口 口 口 口 口 23
  3 口 口 口 口 口 口 口 口 22
  4 口 口 口 口 口 口 口 口 21
  5 口 口 口 口 口 口 口 口 20
  6 口 口 口 口 口 口 口 口 19
  7 口 口 口 口 口 口 口 口 18
  8 ● 口 ● 口 口 口 口 口 17
     9 10 11 12 13 14 15 16

    32 31 30 29 28 27 26 25
  1 ● 口 ● 口 口 口 口 口 24
  2 口 口 口 口 口 口 口 口 23
  3 口 口 口 口 口 口 口 口 22
  4 口 口 口 口 口 口 口 口 21
  5 口 口 口 口 口 口 口 口 20
  6 口 口 口 口 口 口 口 口 19
  7 口 口 口 口 口 口 口 口 18
  8 口 口 ● 口 口 口 口 口 17
     9 10 11 12 13 14 15 16

majorさんの独自ルールの場合も同様にボールは2個までという結果も得ています。
majorさんの独自ルールでボール2個の場合に最短で何手になるかは8時間待っても探索が
終了せず、あきらめてしまいました。(6手以上になることだけは判った)

なんか予想外の結果になってしまいましたがボール2個でも結構楽しめるパズルとは思います。


re:ブラックボックスの解を最短で見つける  投稿者:major  投稿日:08月15日(木)09時57分08秒

確かに高橋さんがおっしゃる通り、解が正確にもとまらないパターンがありますね。
最短ということから離れて入力位置と出力位置の情報から答えを求めるということ
だけを考えた場合はとしひでさんが示してくださった方法でやればよさそうですかね。
もちろんボールは4つ以下で、自分のルールだと少し考え直さなければなりませんが。


re:ブラックボックスの解を最短で見つける 投稿者:高橋謙一郎  投稿日:08月14日(水)15時32分44秒

そもそも、このブラックボックスというパズルには限界があります。

下図においてボールが5個の場合、5番目のボールが 回 のエリアの
どこかにある場合は、その位置を特定することは絶対に不可能です。
要するにオリジナルルールでもmajorさんの独自ルールでもこのパズル
が一意性を持って成立するのは4個以内ということになります。

  32 31 30 29 28 27 26 25
 1 □ □ □ □ □ □ □ □ 24
 2 □ □ □ □ □ □ □ □ 23
 3 □ □ ● □ □ ● □ □ 22
 4 □ □ □ 回 回 □ □ □ 21
 5 □ □ □ 回 回 □ □ □ 20
 6 □ □ ● □ □ ● □ □ 19
 7 □ □ □ □ □ □ □ □ 18
 8 □ □ □ □ □ □ □ □ 17
   9 10 11 12 13 14 15 16

そして、2個〜4個の場合の最短解を得ることは超難問と思われます。


 ホームページへ戻る 書き込みリストへ戻る