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

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


15パズルSolver 投稿者:deepgreen  投稿日:03月09日(金)21時50分48秒

こんばんは、deepgreenです。

BINGOさんの紹介された15パズルのサイトはなかなか盛況のようですが、
私には解けそうもないので15パズルのSolverを作ってます。
(本当はCマガ2000/11月号の高橋謙一郎さんの記事を見て始めた)

高橋さんのIDAサーチのSolverが非常に好成績だったので、もう少し頑張れば
最長手数の問題を解くことができるのでは、(一方では時間の無駄と思いつつ)と
はじめましたが、やはり、Solverのアルゴリズムで苦戦しています。
何とか78手の解が得られるようになりましたが、(数時間かかる)問題はその先です。
最長手数の探索には90手弱まで解けるSolverが欲しいのですが、。。。

高橋さんが解いた78手の問題   最短手数78手の問題
 (MD=58)         (MD=60) 
  *  f  e  d              f  b  e  d
   c  b  a  9             c  *  9  a
   8  7  6  5             8  3  6  5
   4  3  2  1             4  7  2  1
                                   (約23600秒) 

なるべく長い手数の問題を探すために、MD(各ピースの最短距離の総和)の最大となる
問題を探索してみました。こちらは、以下のような結果となりました。おそらく、最長
手数の問題はこの中にあるだろうと思っていますが、約3M個を調べるのは、大変?
(理論的に最長手数をいうためには別のアプローチが必要)

                 MD   問題数 
+++ Searched .... 58  count=2678400
+++ Searched .... 59  count=331776
+++ Searched .... 60  count=41472
+++ Searched .... 61  count=0

ということで、なにか面白いアイデアがありましたらお願いします。


究極のナンプレ問題 投稿者:ゆたか  投稿日:03月01日(木)23時40分30秒

>それにしても初期表示マス数Nについて、N=18とかN=17のナンプレ問題が存在することを知り
>ながら未だ見たことがない。見た人でも教えてくれない。ペンシルパズルマニアとコンピュータ
>パズルマニアの間には大きな隔たりがあるような気がします。

コンピュータパズルには偏見が多々ありますよね。

実際、雑誌系パズルの懸賞商品欲しさのためだけに、コンピュータを使って問題を解き(厳密
には解くとは言わない)応募するという節操のない人たちがいるおかげで、コンピュータパズル
のイメージが下がってしまっていると思います。

著作権がどうのこうという人もいますけど、引用という形を取れば何ら問題はないです。
無断転載はダメですけど。


re:ナンバープレイス 投稿者:高橋謙一郎  投稿日:02月28日(水)22時58分35秒

しえるさん、sssさん、こんばんは。

究極のナンプレ問題に関しては過去に何度も行き詰まった経験があり探索量は天文学的です。
この掲示板の過去の書込みを調べて頂ければ分かることですがプログラム的には限界です。
新しい数理的なロジックの発見がないかぎり一歩も前に進まない、というのが私の感想です。

それにしても初期表示マス数Nについて、N=18とかN=17のナンプレ問題が存在することを知り
ながら未だ見たことがない。見た人でも教えてくれない。ペンシルパズルマニアとコンピュータ
パズルマニアの間には大きな隔たりがあるような気がします。

Aさんが投稿してB誌に掲載された作品です、と明記して匿名でもいいから教えていただける
人がいれば良いのですが、、、、どうしても見てみたい。


# 尚、単なるナンプレソルバープログラムなら、この掲示板の過去の書込みを調べていけば入手
# 出来ます(当HPのJAVA版)。C言語版ならCmagazineの2000/11号にあったのですが........


ナンバープレイス 投稿者:sss  投稿日:02月27日(火)03時51分37秒

はじめまして。
パズラー等の雑誌でナンバープレースを知り、投稿コーナーもあったので、
最小問題には興味がありました。
で、その助けになればと、僕もいまナンバープレースのソルバーをつくっています。

ソルバーのアルゴリズムとしては、
deepgreenさんのページ http://www2.tokai.or.jp/deepgreen/
が詳しく非常に参考になりました。
一度みてみてはいかがでしょうか>しえるさん

ソルバーはなんとか完成しましたが、最小問題に関してはどう手をつけてよいものやら。。
まずは経験的にも正しいと思われるdeepgreenさんの「確定的アルゴリズムの仮説」
をなんとか証明できないかなあと考えてます。
もしかして、もう証明されてますか?


ナンバープレイス 投稿者:しえる  投稿日:02月27日(火)01時22分39秒

はじめまして。いつも楽しく見させていただいております。
ナンバープレイスを解かせるプログラムを作っています。
アルゴリズムとしてはバックトラックを用いているのですが、
局面戻しのいい方法が見つかりません。(1から入れていくのですが・・・)
そこで、よろしかったら参考にソースを見せていただきたいのですがよろしいでしょうか?
言語はなんでもOKです!お願いします。


ともよしさん 投稿者:お!  投稿日:02月25日(日)19時02分21秒

京理1回ですね!


数独 投稿者:としひで  投稿日:02月25日(日)19時01分20秒

ここの過去の書き込みを参照されては如何でしょうか。

http://www2.ic-net.or.jp/~takaken/auto/guest/bbs8.html


数独 投稿者:ともよし  投稿日:02月25日(日)13時15分59秒

はじめまして、
ところで
ナンバープレイスの初期状態に書かれる
数字は最低いくつ必要なのでしょうか。


だ、誰か! 投稿者:BINGO  投稿日:02月17日(土)00時34分13秒

初めまして!では単刀直入に。
ここの人達はとても頭がよさそうなので
ぜひこれをやっていただきたい!
強者求む!

http://www.nob21.com/cgi-bin/15p/15p.cgi


norも12素子でできるようです 投稿者:としひで  投稿日:02月16日(金)13時01分26秒

ところで、ソースファイルで、COUNTが初期化されてません。おそらく、
int main(void)
{
    StartTime = clock();
    Initialize();
    for (DEPTH=3, COUNT=0; !COUNT; DEPTH++)
        BackTrack(3);

    return 0;
}
ではないでしょうか。
解は、6通りと3通りに別れて、
一方は各入力に対して非対称、もう一方は2つだけが対称のようです。
ほんと、勉強になります。


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