プログラミングパズルに関心のある人は雑談しましょう！
とくしんさん、こんばんは。 究極のナンプレ問題の研究がだいぶ進んでいるようですね。 解答図からランダムに40個だけ配置してその問題が解けるかどうかを 統計的に調べて解答図の良し悪しを評価する、というアイデアは面白い ですね。ただ、N=17の問題の解答図が46％というのは一般的にどれだけ 珍しく優れているのか、もう少し多くの実験データがほしいですね。 さて、N=17の解答図から逆算してN=17の問題を探すプログラムですが、 せっかく、そのプログラムを置いていただけているのですが、どのような 実行環境が必要なのでしょうか。エラーになってしまいます。 ところでそのプログラムがN=17の問題を見つけるまでの実行時間はどの くらいでしょうか。私の作ったものは平均１０分くらいなのですが。 ----- 1回目 --------- 16: 0 17: 1 18: 0 19: 7 20: 48 21: 9 22: 0 計: 65 時間: 00 00:03:32 ----- 2回目 --------- 16: 0 17: 1 18: 2 19: 40 20: 230 21: 25 22: 0 計: 298 時間: 00 00:16:12
N=17の解答図から逆算してN=17の問題を探すプログラムです。 解答アルゴリズムはSbitとUbitしか使ってなくて枝狩りも何もやっていませんが テスト実行の時は計2回（両方とも元の問題と全く同じ配置）探し出しました。 こんなに簡単なプログラムでも見つかると言う事は元々の作者も何らかのアルゴリズムで作成したのかもしれませんね（苦笑http://www.geocities.co.jp/Playtown-Darts/9133/Num.lzh
自作ソルバーのチェックで試し解き用の問題を作っている時に解答図の評価法を思いつきました。 解答図からランダムに40個（いくつでもいいけど多い方が解くのが速いので良い）だけ配置して、 その問題が解けるかどうか調べる。 ↑を1000〜10000回ほど繰り返して解けた問題の数をカウントすれば どれぐらいヒントの数字を減らせるかの目安になります。 ちなみに、N=17の問題の解答図は46％、9/8の図2は13％、図3は39％程度でした。 矢張りN=17の問題は解答図の素質も良かったみたいですね・・・。
今、N=17やN=16の問題を探すべく挑戦しているのですが ナンプレは普通のソルバーさえ作った事が無いので苦戦しています（苦笑 高橋謙一郎さんの作ったUNITILEのソルバーのアルゴリズムを基に考えた方法を紹介します。 1．まず、解答図を作る（自動化するか手動で入力するかは検討中） 2．解答図から数字を抜く順番を乱数により作る 3．順番の一番若い数字と「さらにもう1つ」抜いた時解のあるパターンがいくつあるか調べる 4．全て解があるならその数字を抜く 解が無いパターンが1つでもある場合は全ての数字の中からその数字ともう1つ抜いた時 解が最も多くなる数字を探し、それを抜く 5．どの数字を抜いても解が得られなくなった場合、Nの値と検出されたNが最小の問題数を記録する 6．2で作った数字を抜く順番をランダムに2つ入れ替え3〜5を繰り返す 7．5と6でNの値と最小の問題数を比較して6が優れていればそのまま、 5が優れていれば交換をキャンセルして6から繰り返す この方法ならかなり効率良く最小問題を探せるような気がしますが、 1回のループが非常に遅くなるのが欠点です。 上手く枝刈りを行ってループを高速化すれば（N=16が存在するかはわからないが） N=16〜N=18の問題を作る事も可能だと思います
とくしんさん、はじめまして。 究極のナンプレ問題に関心のある方は本当に多いんですね。 そして、貴重なコメントをありがとうございます。 いかんせん、私は青年会長としてお祭りの準備に没頭するモードに入りました。 かなり大規模なお祭りなので身の引き締まる思いで悪戦苦闘しております。 既に頭の中はお祭り一色に染まっていてプログラミングパズルとは無縁の世界に います。 いろいろコメントしいたこともあったのですが約２週間くらいは沈黙します。 申し訳ございません。
誰かぁ〜 WATTA Freakのstage２のヒント下さぁ〜い！ お願いしまぁ〜す！いくら積み上げても 届かない〜ん(;´д｀)トホホ
はじめまして〜 ナンプレの最小問題に興味があって暇を見つけては色々考えていたのですが 2つの数字が小さい範囲で閉じている（図1）配置はヒント数を減らす際に邪魔になるので そのような配置の出来るだけ少ないパターンが優れていると思います 試しに極端な例を作ってみました。図2と図3でどっちが優れているかは見たまんまですね（笑 （図1） １２３ ４７９（1と4、5と8、3と9がそれぞれ2x2の範囲で閉じていて ４５６ １８２ 最低3個ヒントを置かないと決定できない） ７８９ ３５３ （図2） １２７ ３５９ ４６８ ３４８ １６７ ２５９ ５６９ ２４８ １３７ ２１５ ７８３ ９４６ ９８６ ４２５ ７１３ ４７３ ９１６ ８２５ ６５４ ８７２ ３９１ ７３１ ５９４ ６８２ ８９２ ６３１ ５７４ （図3） １２３ ９７８ ６４５ ４５６ １２３ ８９７ ７８９ ５６４ １２３ ９１５ ６３２ ７８４ ３４８ ７１５ ２６９ ６７２ ４８９ ５３１ ８６１ ３４７ ９５２ ２９４ ８５１ ３７６ ５３７ ２９６ ４１８ 時間があればこの法則を自動化して最小問題に挑戦したいと思います
UNITLEの松本さん、はじめまして。 全自動のサイトとは面白いことを考えたものです。考えたとしても普通は作れないですね。 私のＨＰも一部ＣＧＩで自動化してますが、なかなか全自動とまでは行きません。 さて、UNITLEランキングの件ですがプログラムに解かせてランキング登録してしまったことを お許し下さい。(もちろんランキングをメチャクチャにするつもりなど全くありません) > たぶん、これまでランクインしている方は頭の中だけで解いたのでは > ないかと思います。皆さん尊敬してしまいます。 ほんとすごいですね。Level34まで行ける人は何か凄いロジックを見つけているのだと思います。 私の場合は、どんな解法プログラムを書けばよいのかが興味の中心になるので普通の考え方とは 異なるアプローチになることが多くあり、UNITILE の場合も自力で解く方法とは全く異なる 方法になってしまいました。 > こちらのサイトでsolverのアルゴリズムを議論される分には迷惑とか > そういうのは全然ありませんので、ばりばり明かしてしまってください。 いいのでしょうか。お言葉に甘えて私の書いたソルバープログラムの仕組みをバラします。 先ず、「初期空欄マス」の座標を値に持つテーブルを作ります。これを「順番テーブル」と呼ぶ ことにして、格納した順番を乱数を使って一旦シャッフルします。 さて、順番テーブルに格納されている順番通りに空欄マスにタイルを最後までハメ込んでいきます。 この時の、ハメ込むタイルの色は総て「青」としておきます。そして、初期空欄マス以外の「初期 タイルマス」が最後に「赤」になってしまった数をかぞえ、その値をその順番テーブルの「評価値」 とします。評価値が小さいほど優れた順番テーブルということになり、評価値＝０が答えです。 この時、初期空欄マスのタイルの色は最後に何色になってもかまいません。青でハメ込んだ結果が 赤ならば、実際にハメ込む時には赤にすれば良いだけです。 いよいよ評価値＝０の順番テーブルを探すアルゴリズムですが次の行程を繰り返すだけです。 順番テーブル内から乱数で２地点を選び座標値を交換し、その評価値を求める。 交換前と同じか改善されればそのままとし、改悪されるようなら元に戻します。 これを繰り返すと、順番テーブルは、しだいに改善されて終いには、評価値＝０の順番テーブルに まで改善されます。ただし、時として局所解に陥ってしまう場合があるので繰り返し回数を制限し、 制限に達しても解が見つからない時は、またシャッフルしてやり直すようにしますが、大抵は 一瞬で見つかるようです。 こんないい加減な方法が成功する訳は、解が一通りではない、むしろ解の個数が非常に多いから ではないでしょうか。再帰を使って真面目に探索したのでは割に合わないパズルのようでした。 > 本当は、もっとすんごいCPU TIMEを食うようなアルゴリズムで問題生成もしてみたいのですが、 松本さんのナンバーパズル(数独)の問題を自動作成するプログラムにも何らかの「順番テーブル」 が使われていると思います。上記した方法でヒント数が少なくなる改善のループを走らせてみては いかがでしょうか。私の実験では約５０％の確立でヒント数が１９個くらいまで改善なるようでした。 「ヒント数が少ない＝難しい」とはならないのですが。 では、今後ともよろしくお願いします。
どうも初めまして＞mtkさん。高橋さん。 ramoxこと松本と申します。UNITLEの作者です。 ランキングの画面にURLが貼ってありましたので、来てみました。(^-^) もう何年も前に作ったものなのですが、こうして解法を考えている方が 居たのかとちょっと感動しております。 # 作った頃、WindowsのバージョンはNT3.51だったような・・・ ご指摘の通り、このパズルはsolverを書いてしまうと簡単に解けます。 また完成形から逆向きにタイルを抜いて問題を作っているというのも、 ご想像の通りです。私自身は全然パズルを解かない人なので、ルールを 考えたり、問題を作ったりするプログラムを考える方が楽しいんです。 このパズルはタイルがひっくり返る様子が見てて楽しかったので、それ でルールを考えたようなものです。 こちらのサイトでsolverのアルゴリズムを議論される分には迷惑とか そういうのは全然ありませんので、ばりばり明かしてしまってください。 読むのは楽しいですし。 ただ、solverで解いてランキングを埋め尽くすとかやっても、それは お互い楽しくないと思いますので、できればそれは避けてください。 (^-^;) たぶん、これまでランクインしている方は頭の中だけで解いてのでは ないかと思います。皆さん尊敬してしまいます。 私自身は未だにLevel13が限界なんですけど、知り合いには自力でLevel 30まで解いた人も実際に居ましたしね（今回のLevel34の記録にはびっ くりです）。 そういえば。Level99まで行っちゃったときどうなるのか、試験した 記憶がありません。どうなるんだろう・・・バグらなきゃいいけど。 そもそも、Level90あたりになると、パズルになってないですよね。 たぶん・・・ 本当は、もっとすんごいCPU TIMEを食うようなアルゴリズムで問題生成 もしてみたいのですが、いかんせん頭の構造が理数系でないのと、そこ まで自分の自由になるサーバもないので、実現しないで今に至っていま す。 一日一問コースで出題しているパズルの問題も、超簡単なアルゴリズム でバックトラックしてるだけです。ナンバーパズルなんて、３ヶ月分の 問題を生成するのに数秒しかかかってないんですよね。パズル好きな方 を唸らせるようなのを生成してみたいものです。 まぁ、今後の課題、ということで。 今後ともよろしくです。 では。
UNITILEのランキングから、リンクさせていただきました。