プログラミングパズルに関心のある人は雑談しましょう！
Ｎ＝１６までの結果ありがとうございます。 「５個の数字から３個以上」はプログラムで総当りで試すには 手におえそうにないので練習がてら「３個の数字から２個以上」 を総当りで試してみているのですがＮ＝９ですでに辛くなっています。 「３個の数字から２個以上」についてはすでに何かしらの公式が 見つかっていますか？
> > yahooの掲示板でもＮ＝２０程度までは条件Ａを満たすＸで位数が小さいものが求められました。 > その結果を教えてもらえませんか。 ２０程度までと思っていたのですが、メモを見返したら１６まででした。メモを取り忘れたか実際に１６までだったかはよくわかりません。 それに、位数だけで具体的な組の内容は、写していません。 Ｎ＝１０ ２個 Ｎ＝１１ ５個 Ｎ＝１２ ６個 Ｎ＝１３ ９個 Ｎ＝１４ １０個 Ｎ＝１５ １３個 Ｎ＝１６ １６個
> yahooの掲示板でもＮ＝２０程度までは条件Ａを満たすＸで位数が小さいものが求められました。 その結果を教えてもらえませんか。
実は「こけらおとし」と掛けたギャグだったんですね！ 簡易ロト問題、面白そうですね。今は暇が無いのでプログラムを書く余裕は無さそうですが プログラムの方針だけでも考えてみました。 ・場合の数によって求めた下限値からの上方向への反復深化 ・最適化の手法を使って求めたある程度小さい解からの下方向への反復深化 ・下限値とある程度小さい解の間での2分探索 結局は下限値の解とそれ-1で出来ない事の証明の2つが最低限必要ですが その敷居値を効率良く求める事がこの問題の本質だと思います。
題記の問題は昨年の春から夏にかけてyahooの数学掲示板で 話題になったものです。残念乍、現在はそのトピックは消滅しています。 この問題に対し、私のホームページのメインテーマであるグラフを使ったアプローチが いろいろできそうなので、この度取り上げることにしました。 が、ここの掲示板でも、興味のある方はご意見を頂きたいと思います。 で、問題は以下のとおりです。 Ｎを与えられた自然数とし１以上Ｎ以下の相異なる５個の数字からなる集合を 単に組ということにする。従って、組の個数は全部でＣ（Ｎ，５）になります。 このとき、次の条件を満たす組の集合Ｘを考える。 条件Ａ 任意の組が、Ｘに含まれる何れかの組と必ず３個以上の共通な数を持つ。 条件Ｂ Ｘは条件Ａを満たす集合のうちで要素の個数（位数）が最小である。 与えられたＮに対して、上記二つの条件を満たす集合Ｘを具体的に求めよ。 Ｎ＝１０の場合はほぼ自明です。で、yahooの掲示板でもＮ＝２０程度までは条件Ａを満たすＸで位数が小さいものが求められました。 が、条件Ｂを示すのがかなり困難で、結局投稿が減り自然消滅に至ったという状態でした。 この問題が解けたからといって、ロトの的中率が上がるとは思えませんが、理論的（特に離散数学方面では） には、かなり重要な問題のような気がします。
塗り壁さん、お久しぶりです。 そして大変貴重な情報をありがとうございます。 Ｎクイーン問題でＮ＝２４を求めていたとは本当に驚きです。 それも日本人のようですね。FireCoreという名のコンピュータ を使用したことがポイントのようですが、私の翻訳に間違いが 無ければ２．８ＧＨｚのＣＰＵを２個搭載したコンピュータを ３４台、つまり６８個のＣＰＵを使用したのでしょうかね。 基本的なアルゴリズムも大事ですが分散処理のアルゴリズム も大きな成果を得られる方法としてとても興味が沸いてきました。 素人にはＬＡＮ接続による複数のパソコンを使う方法を考える のも現実的で面白そうです。 気持ちと時間にゆとりが持てるようになるのはいつのことか。
ご無沙汰しています。塗り壁です。 またまた、Ｎ−クイーン問題の話です。貴ページでは世界記録が Ｎ＝２３となっていますが、２４次が下記サイトに載っていましたので ご参考まで。 なお、このサイトではいろいろな数列を扱っていて最初の数項を入れると どんな数列かを判定することができます。 私も現在研究中の数列（Ｎ−クイーン問題の関係ですが）が ヒットしたのでびっくりしました。 なお、英語のページです。http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000170
とても楽しかったです。 続編を期待している方が大勢いるのですが、予定はないですか？ 宜しくお願いします。
とくしんさん、はじめまして。ｄｅｅｐｇｒｅｅｎです。 すばらしいです。どうもありがとうございます。 この作図問題は、当時ずいぶんさがしましたがどうしても解が見つからず、 あきらめていました。 今は,仕事が忙しくてパズルの方は中断していますが,時間がとれたらもう一度 挑戦してみたいと思っています。
2001年03月17日の書き込みにあった作図問題が解けたので報告してみます。 とは言っても自分で作ったジェネレータではなく、 他人の作ったジェネレータで実験したらたまたま見つけただけなんですけど・・・ ・・４９・５１・・ ・３・・２・・９・ ８・・・・・・・６ ６・・・・・・・４ ７・・・・・・・３ ・２・・・・・６・ ・・９・・・４・・ ・・・６・８・・・ ・・・・７・・・・ 色々と実験していて気付いたのですけど、 作図問題に関しても解の出来やすいパターン、出来にくいパターンが存在するようです。 n=18等の極端に少ない配置での作図を試みると配置による差が顕著に表れます。 □□・ ・・・ ・・・ □・・ ・・・ ・・・ ・・・ □□・ ・・・ ・・□ ・・・ ・・・ ・・□ ・・・ ・・・ （以下省略） このようなL字＋空いてるラインに2個以上というパターンを多く含む盤面がどうやら解が出やすいようです。 逆に、全てのブロックに2個ずつ数字の入っているパターン等だと18個程度では殆ど無理でした。 表出17個に関しては問題の存在する配置さえ与えれば何とか作図出来るようなので、 表出16個、17個の問題は作図問題からのアプローチもあるのではと思いました。 ※答えの配置を利用してナンプレを解かずに答えのある盤面か見極める方法 現実的な方法かはわかりませんが・・・ ・解答図から特定の数字群を抜くと全てのマスの選択肢が2通りになり、 どこか1箇所でも埋めれば全てのマスが決定する時、そのマスを閉所と呼ぶ ・解答図に存在する全ての閉所とその数字郡を調べ尽くす ・ヒントをいくつか選んだ時、そのヒントで全ての閉所が網羅されているかを調べる。 ・網羅されていればそのヒントで解は1通りに決定し、網羅されていなければ （少なくともその閉所で）別解が生じる。 1つの解答図に存在する閉所の数がどれぐらいになるのか、 また全てを調べ尽くす方法が存在するのかがわからないのでこの方法が有効かはわかりませんが、 解答図から問題図を作る場合はこのような方法もあります。