お気づきの点や感想要望などなんでもＯＫ！
N=17のナンプレとてもビックリです。かなり疑ってました。 私もヒント数最少の問題を探すべく、 乱数で250万問ほど作ってみました。 N 度数 % 18 0 0.00000 19 7 0.00026 20 658 0.02469 21 20928 0.78529 22 204075 7.65761 23 711538 26.69941 24 977611 36.68341 25 574855 21.57058 26 154302 5.78995 27 19756 0.74131 28 1228 0.04608 29 37 0.00139 30 0 0.00000 が、N=18すら出てきてくれませんでした。 N=19のヒントの配置にも規則性は見出せません。 私としては作図問題を地道に証明していって、 最終的にN=??が最少でその配置はこれ ということが証明できないかと期待しています。
お役に立てて嬉しいです。 果たしてこれ以上ヒントの少ないものが存在するのか、 もし存在するのであれば是非見てみたいものです。 私もパズルを解くプログラムに興味があるのですが、 どちらかというとパズルを解くためではなく、 パズルを作るためのプログラムの一部として 用いるという使い道に、より魅力を感じます。 ここにリンクを張らせてもらいました。 これからも頑張ってください。http://www26.freeweb.ne.jp/play/puz/
稲葉さん、こんばんは。 大変に貴重な情報をどうもありがとうございます。 N=17のナンプレ問題なんて本当に存在するのか半信半疑だった のですが正真正銘N=17のナンプレ問題ですね！！！！ 自力で解いてみましたが難易度はちょっと低いようです。 もちろん難易度なんて私の興味の範囲内では関係ありません。 少ない情報量から芋づる式に解が確定されていく様子は実に 見事なものがあります。とても巧く出来た問題です。 そして、この様子を見ていてひとつ思い付いたことがあります。 ただ残念なことに私もdeepgreenさん同様に１５パズルにハマ っています。後回しになってしまうアイデアですが、 あるマスがどれだけ少ない情報量によって確定出来てしまう かという評価値を設けます(局地的に)。この評価値を使った最良 優先探索をさせてみてはどうかという案です。そして、N=17とか N=16とかの問題面を探索させてやろうということです。 ところで稲葉さんのＨＰはすごいボリュームで驚きました。 会社の昼休みにでも遊びに行きたいと思ってます。 これからもよろしくお願いします。
2月28日に、N=17の作品が見てみたいという 記述を見つけたので、まだご存じでなければ どうぞ、 □□□ □□□ □６８ □□□ □□□ □□９ □５□ □３□ □□□ ８□□ □４□ ７□１ □□□ ５□□ □□□ ９□６ □□□ □□□ □７□ □□□ ２□□ ４□□ □□□ ３□□ □□□ ９□□ □□□ Ａさんが投稿してＢ誌に掲載された作品です。http://www26.freeweb.ne.jp/play/puz/
あらさん、はじめまして。deepgreenです。 ナンプレ作図問題に関心をもたれた方がいらっしゃるのは嬉しいかぎりです。 私としては１年半前の話ですので、記憶はかなりあやしくなっています。 当時この程度は結論を出したいと思っていた問題です。下記の作図問題は解があるでしょうか？ （□に数字をいれてナンプレ問題として完成できるか？） ・・□□・□□・・ ・□・・□・・□・ □・・・・・・・□ □・・・・・・・□ □・・・・・・・□ ・□・・・・・□・ ・・□・・・□・・ ・・・□・□・・・ ・・・・□・・・・ もし時間がとれたら、またやってみたいと思っています。（しばらくは１５パズルと格闘） どなたかご存知でしたらお願いします。
みなさんはじめまして、"あら"と申します。ナンプレに興味を持っています。 下の図はdeepgreenさんが https://computerpuzzle.net/etc/bbs/bbs9.html において投稿された問題を変形し確定マスを増やしたものです。 □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ □□□ ・・・ □□□ □・・ ・・・ ・・□ □・・ ・・・ ・・□ □・・ ・・・ ・・□ この図も作図不可能ではないかと思いますがどうでしょうか？ なお、あと1つ確定マスを増やしたものは全て作図可能なようです。
高橋さん、としひでさん、こんばんは。ｄｅｅｐｇｒｅｅｎです。 ＞MD = LowerBoundと解釈していいのですか？ 高橋さんのいっているＬｏｗｅｒＢｏｎｄと同じです。 私のＳｏｌｖｅｒは、高橋さんの１〜４＋以下のパターンデータベースの枝刈りを いれました。 １２３４ ５６？？ ？？？？ ？？？＊ ＩＤＡ＊の探索は、２手すすむと探索空間は約９倍になります。幅優先探索では１手にすすむ ことに探索空間は約２倍になります。２手では４倍くらいですのでこの差は重複ということに なります。この辺を改善するため、探索にキャッシュ機能をいれてみようかなと考えています。
高橋さん、ありがとうございます。 夜動かして…は3×3の8パズルを反復深化で解いたときにやりますた。 この掲示板に書かれていた、3×3を4×4の左上に当てはめると、 3×3の世界で解くより、早く解けるかもしれない、とありましたが、 実際そのようですね。2手短くなるパターンがあるようですね。 MD = LowerBoundと解釈していいのですか？ 毎回局面から計算してました…差分を使ったほうが速いですね。
としひでさん、はじめまして。 > 70手とか80手という手数でも解けるなんて！ > どういう方法を使われているのですか？ > CMAGAZINE 2000年11月号…今更手に入らないかな。 解けるといっても数時間かかります。夜寝る前に実行しておくと 朝起きたときには解けている程度のものです。Ｃマガ2000年11月号 にあるプログラムはIDA*を使っていて高速化の工夫としてはこのよう なものです。 1.各ピースの最終到達地点までの距離の総和をLowerBoundにした枝刈り 2.次の1手で親局面に戻す手の排除 3.深さ制限の初期値をLowerBound値とし増加量は+2とする 4.LowerBound値は親局面のLowerBound値から相対的に求める それからdeepgreenさんのＭＤ（各ピースの最短距離の総和）の最大となる 問題を探索したというのは面白いアプローチですね。ＭＤの最大値が６０ という発見もなかなかです。このアプローチから何か新しい展開が生まれて こないか私も考えてみます。
私もBINGO書き込みがあってから、ソルバー作りに励んでおりました。 でも、単なるDFIDSでは、24手で数秒と言う感じで、1手毎に約2倍のノード数となってしまいました。 MDによる枝刈りを入れたIDA*でも30手を越えると同様になってしまい、行き詰まっていました。 幅優先でも両側から解いて40-50手で限界かなと思い、こちらは作るには至っていません。 短手数ではあまり同一局面は出ないと思って同一性チェックはしてないけど、 70手とか80手という手数でも解けるなんて！ どういう方法を使われているのですか？ CMAGAZINE 2000年11月号…今更手に入らないかな。 追伸、N^2-1パズルはNP完全だそうです。