ホームページへ戻る  書き込みリストへ戻る
プログラミングパズル雑談コーナー

プログラミングパズルに関心のある人は雑談しましょう!


私もどうにかヒント数17を発見 投稿者:高橋謙一郎  投稿日:01月26日(日)19時35分10秒

面白い議論が展開されているようですね。

ところで、私もヒント数が17の問題を見つけました。
プログラムは全くいじってなくて、とくしんさんの評価法を
70%以上に設定して、まるまる2日間も粘ってみました。

HINTS=17 156981sec
 - 3 5 - 9 - - - -
 - - - - - - - - -
 2 - - - - - 4 - 8
 4 8 - - - - - - -
 - - - - 7 9 - - -
 - 5 - - - - - - 1
 - - 7 - - - 9 6 -
 - - - 8 - - - - -
 - - - - - - - 3 -

閉所に着目したアイデアはとても魅力的なので今後は私も
いろいろと考えて、是非取り入れてみようと思っています。


3つの数字における閉所 投稿者:浅海 焔  投稿日:01月26日(日)18時28分16秒

>2個の数字だけじゃなくて3個以上の数字で同じ事を調べたら
「最低2個以上」この時点で、その2つが同じ閉所に入っている保証が
なくなってしまいますので同じ方法というわけにはいかないと思います。

それで私は「解の数を数える」という手法を試みました。
3つの数字を全て抜いて、それでソルバーに解を数えさせる、と。
閉所が多ければ多いほど解の数は増えるだろう、と見込んだのですが
効果があるかどうかはなんとも・・・といった感じでした。
よくよく考えてみれば、閉所の数が同じでも
特定の数字の組み合わせに閉所が偏れば合計値も変わってくるでしょうし。


素質のある解答図を作成する点については、
問題作成と同様に改善を試みる手もあります。
・ランダムに解答図を作成
・閉所を見つけ次第、試しに入れ換えてみる
・もう一度閉所を数え直す
・悪化していれば元に戻す
・適当に改善されなくなるまで繰り返す
これだと後々になって閉所の評価方法が変わってきても
融通が利くんじゃないかなと思います。

自分は今のところ解答図作成については無作為でいくつもりです。
無作為に生成する方法の1つとして自分が採用しているのは、
・ランダムな順番テーブルを生成する
 (これを仮定するマスの優先順位とする)
・すべて空白(未確定)マスの盤面を問題として、解かせる。
・最初に得た解を解答図とする。
SbitやUbitのような確定的な探索はある程度仮定してからが
効率的だと思います。
要するにとくしんさんの仰る方法と変わりません。
もっと画期的に速く生成できる方法ありませんかね?


閉所つぶしで枝刈りした回答図作成 投稿者:とくしん  投稿日:01月26日(日)16時01分51秒

閉所の考え方は僕も考えてましたがどうやってプログラムすればいいのか判らずに諦めていました。
まさか自分の諦めていた方法でヒント数17の問題を発見されるとは・・・ちょっと悔しいです。
閉所の考え方は早速取り入れねば、ということで閉所の考えを応用した回答図の作り方を考えてみました。
・まずは1を適当に全て入れる。
・2をランダムに入れ、1と2で閉所が出来ていたらやり直す。
・3をランダムに入れ、1と3、2と3で閉所が出来ていたらやり直す。
・以下繰り返し
この方法でランダムな配置から探すより遥かに効率よく閉所の少ない回答図を作成できると思います。
閉所の1個も無い回答図が存在するかは判りませんがこんな方法で作ってみてはどうでしょう?

ところで、2個の数字だけじゃなくて3個以上の数字で同じ事を調べたらどうでしょう?
当然数字は最低2個以上置かなければ成立しませんがヒント数の少ない問題を作る上では重要な気がします。


ナンプレの解答図自動生成 投稿者:とくしん  投稿日:01月26日(日)13時29分21秒

はじめまして〜>おめがさん。
何か某所で会ってた気もしますが気にしない方向で。(ぉ

解答図自動生成の方法は色々ありますが、一番簡単なのは
・左上から順小さい数字から順に入れていく。
・破綻したら1つ戻って1大きい数字を入れる
・9まで順に入れてもダメだった場合も1つ戻る
という方法です。このままだと毎回同じ問題が出来てしまうので
適当に乱数を使って適当にかき混ぜればOKです。

もしかしたら究極のナンプレ問題用の解答図を作りたいのなら
閉所を作らないような方法で作った方が効率が良いかもしれませんが。


はじめまして 投稿者:をめが  投稿日:01月26日(日)11時40分56秒

はじめまして。をめがです。


突然ですがナンプレの解答図自動生成の方法が分かりません・・・


はじめまして 投稿者:Yz  投稿日:01月24日(金)12時37分41秒

多分はじめましてのYzです。
JAVAのパズル作りたいなぁと思ってさまよっていたら着きました
よかったらJAVAをパズルを作るときに参考にしたほうがいい書籍やサイトがあったら
教えてくださいね。まぁJAVA自体ろくにしらないので親切な入門書でもいいのですが(笑

話変わりますがこのサイトにある自動回答意外と便利でした。
あまりナンプレの類は得意でないので詰まっている問題もあるので
できればiアプリ版をつくってくれると非常にうれしいかな

http://ip.tosp.co.jp/i.asp?I=logichouse


Re:ヒント数17のナンプレ問題 投稿者:浅海 焔  投稿日:01月23日(木)20時01分39秒

またヒント数17の問題を発見してしまいました。

 - 9 - - - - 5 - -
 - - 7 - - 3 - - -
 3 - - - 2 8 - - -
 - - 8 - - - - - -
 - - - 5 - - 1 - -
 7 - 3 - - - - - -
 - - - - 6 - - 7 4
 - 1 - - - - - - -
 - - - - - - - 3 -

まさか自分が次を見つけるとは思ってもいませんでしたが・・・
こんなペースで見つけたらそれこそ鬼ですが、流石にそんなことはないでしょう。


Re:ヒント数17のナンプレ問題 投稿者:とくしん  投稿日:01月22日(水)03時32分27秒

なんと、ひさびさに来てみたらヒント数17の問題が新たに2問も出来ているではないか!
僕も別の方法で挑戦せねば・・・と言いたいところだけど最小問題に関しては新しいネタが思い浮かばないなぁ・・・
作図問題に関してはちょっと良い考えがあるので暇があったら挑戦したいと思います。
ヒント数17とは言わないけどせめて18、19ぐらいの作図問題は解けるようになれば良いな・・・


Re:ヒント数17のナンプレ問題 投稿者:高橋謙一郎  投稿日:01月21日(火)23時49分25秒

浅海さん、ありがとうございます。

実は私も4マスで閉じている場所を数えて評価したことが
あって、もしやと思ったのですが、やはりそうでしたか。

それにしても、6マスとか8マス以上という配置で閉じている
パターンがあることには気づきませんでした。(ビックリ!)
4マスのパターンだけで評価した時はぜんぜん効果が無かった
と記憶しているのですが、あきらめるのが早すぎたのか、
4マスを超えるパターンがあることに気づかなかったのが悪い
のか、、、

面白い情報をどうもありがとうございます。そして、N=17問題
の発見、おめでとうございます。

今後ともよろしくおねがいします。


Re:ヒント数17のナンプレ問題 投稿者:浅海 焔  投稿日:01月21日(火)23時21分32秒

説明不足で申し訳ありませんでした。
私の言う閉所というのは、高橋さんの仰る通りのものです。
解答図の生成は無作為に行っています。

2つの数字が4マスで閉じている例
A口□ B口口 口口口
B口口 A口口 口口口
口口口 口口口 口口口

2つの数字が6マスで閉じている例
A口□ B口口 口口口
B口口 口口口 A口口
口口口 A口口 B口口

2つの数字が8マスで閉じている例
A口□ B口口 口口口
口B口 口口口 A口口
口口口 A口口 B口口

BA□ 口口口 口口口
口口口 口■口 口■口
口口口 口■口 口口■

口口■ 口口口 口■口
口口■ 口口■ 口口口
口口口 口口■ 口口■ (■はA,Bのどちらかが入る場所の1例)

この場合、■の方は「2つの数字が10マスで閉じている」
ということになります。

2つの数字の組み合わせ36通りについて全て調べて、
このように狭い範囲で閉じているものがある程度少ない解答図を選びます。


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