こんばんは、deepgreenです。

ＢＩＮＧＯさんの紹介された１５パズルのサイトはなかなか盛況のようですが、
私には解けそうもないので１５パズルのＳｏｌｖｅｒを作ってます。
(本当はＣマガ２０００／１１月号の高橋謙一郎さんの記事を見て始めた)

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

高橋さんが解いた７８手の問題　　　最短手数７８手の問題
　（ＭＤ＝５８）　　　　　　　　　（ＭＤ＝６０）　
 　*  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秒） 

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

京理１回ですね！

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

https://computerpuzzle.net/etc/bbs/bbs8.html

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

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

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

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

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