プログラミングパズルに関心のある人は雑談しましょう！
続きです、 deepgreenさんのプログラムは幅優先なのでしょうか？それとも下限からの反復深化ですか。 反復深化かな〜でしょうね。下から攻めるか上から攻めるか迷ったのですが、よくよく考えて みると普通に下からの反復深化で良かったような気がしてきました。 上から攻めた場合、上限値が甘すぎると地獄ですからね。（ラッキーな場合もありますが） とくしんさん提案による、上と下から２分探索で絞り込むのもいい方法ですが、１回分の探索 時間があまりに長すぎるので何回も探索できる余裕がないんですよね。 で、上から攻めてラッキー過ぎたために書き込みミスをしたお詫びというか、証拠の品というか、 ソースコードを置きます。コンパイルして実行すると私のアホな事情が分かるかも知れません。
deepgreenさん、こんばんは。 「５個の数字から３個以上」の問題で、Ｎ＝１３の最適解は８個で間違いありません。 すみませんでした、久しぶりの書き込みなので、あせっていたようです。 私のソルバーも間違いなく８個という結果が出ていたのですが書き込みの時に単純コピー によるミスがありました。というか、、、 記録をよく見ると、Ｎ＝１３での８個解は「欲張り法」ですぐに見つかったのですが、 あまりに簡単に見つかり過ぎたので気にもとめずに勘違いしていたようです。 （７個で解がないというは、一晩かかっています。） うぅ、美味しいところを取られてしまった。（←はずかしながら、素直な気持ち）
皆さん、こんばんは。deepgreenです。 私も、誘惑には勝てず、久しぶりにＳｏｌｖｅｒを作りました。 「５個の数字から３個以上」の場合、Ｎ＝１３には、８個の解があることが わかりました。７個の解は存在しません。 ==== (13, 7) ==== Thu Feb 17 02:47:52 2005 −＞ 解なし ==== (13, 8) ==== Thu Feb 17 02:51:30 2005 ==== Congratulation !!! ==== Thu Feb 17 05:00:52 2005 1 2 3 4 5 6 7 8 9 0 1 2 3 ------------------------- s1 1 1 1 1 1 . . . . . . . . s2 1 1 1 . . 1 1 . . . . . . s3 . . . 1 1 1 . . . . . 1 1 s4 . . . 1 1 . 1 . . 1 1 . . s5 . . . . . 1 . 1 1 1 1 . . s6 . . . . . . 1 1 1 . . 1 1 s7 . . . . . . . 1 . 1 1 1 1 s8 . . . . . . . . 1 1 1 1 1 どこか勘違いしてるかな ???
N=9 の場合の説明ありがとうございました。 カークマンの１５人の女学生の問題についてはたまたま http://www.sampou.org/cgi-bin/haskell.cgi?blog%3aEveryday%3a2004-11-22&l=jp のときに調べたことがありました。 「３個の数字から２個以上」で N=10 のとき {(1,2,3),(1,4,5),(2,4,5),(3,4,5),(6,7,8),(6,9,10),(7,9,10),(8,9,10)} の８個の解が見つかっているそうです。（上限８が確定）
塗り壁さん、皆さんこんばんは。 数学的な議論は全く苦手なのですが、deepgreenさんの「３個の数字から２個以上」で Ｎ＝９の場合の上限解の求め方は良く理解出来ました。とても明解で感激しました。 ところで、この前の３連休の時に私も考えてみました。前回のサッカーくじと違って 今回は最適解にこだわったのですが、「５個の数字から３個以上」の本来の問題では、 Ｎ＝１０ ２個 Ｎ＝１１ ５個 Ｎ＝１２ ６個 Ｎ＝１３ ９個 までは結果を出せました。（欲張り法で上限解を求めてから、総当り法で最適解を確定） 久しぶりにパズルのプログラムを書いて楽しかったのですが、かなりの難問ですね。 三吉さん提案による「３個の数字から２個以上」にプログラムを書き替えてもみました。 Ｎ＝９の場合の解は、欲張り法で９個、最適解は７個と一瞬で結果が出ていました。 最終的に最適解を得ようとするならば、総当り法をベースにしたアルゴリズムにおいて 対称性を考慮して同等のパターンを排除しながらの探索を行うプログラムが必要です。 加えて、２種類の枝刈り法も搭載したのですが、それはほとんど役に立っていません。 サッカーくじ同様に乱数を使って、近似的な最適解を求めるしかないような気がします。 ただ、あまり得意な分野ではないし時間もないので、どうにもならないのですが。。。 ところで、塗り壁さんにくどいような質問で申し訳ありませんが、以下の結果は最適解 と断定されたものなのでしょうか、それとも見つかった解の最小記録なのでしょうか。 Ｎ＝１４ １０個 Ｎ＝１５ １３個 Ｎ＝１６ １６個
すみません。肝心の問題について抜けていました。 「３個の数字から２個以上」でＮ＝９の場合について、 シンプルな解（１２個）を具体的に求めた結果です。
初等幾何で考えてみました。 （１）９ケの数字を３ｘ３の格子点に対応させる。 ７ ８ ９ ４ ５ ６ １ ２ ３ （２）９ケの数字から３ケの数字を選択する。 → ３ｘ３の格子点上では３角形を特定（選択）したことになる。 （［１，２，３］のようにつぶれているものも含む） （３）２組の３ケの数字の間で、２ケの数字が一致する。 → ２つの３角形が辺を共有するということ。 ｅｘ．［２，３，４］と［３，４，５］は、辺[３，４］を共有している （４）代表として、以下の１２ケの３角形を選択する。 ａ．傾きが０度の線分を網羅するもの ［１，２，３］ ［４，５，６］ ［７，８，９］ ｂ．傾きが９０度の線分を網羅するもの ［１，４，７］ ［２，５，８］ ［３，６，９］ ｃ．傾きが４５度の線分を網羅するもの ［１，５，９］ ［２，６，７］ ［３，４，８］ ｄ．傾きが−４５度の線分を網羅するもの ［１，６，８］ ［２，４，９］ ［３，５，７］ この１２ケの３角形で、縦、横、斜めのすべての線分が網羅されていることがポイント。 （５）３ｘ３の格子点上の任意の３角形は、少なくとも１辺として、縦、横、斜めのいずれか の線分をもつ。 （説明） １を頂点とする３角形を考える。他の２点として２，５のような自明な点を 除外すると、残るのは、６，８のみである。この１，６，８の３点で構成さ れる３角形は、［６，８］という−４５度の線分が含まれる。 従って、１を頂点とする３角形は題意を満たしている。 同様にして、他の点を頂点とする場合も成り立つ。（説明略） （４），（５）より、３ｘ３の格子点上の任意の３角形は、（４）の１２ケの３角形のいすれか と辺を共有していることがわかる。
yahoo掲示板では、ロト問題の最適解を直接求める のが困難なため下記のような上限問題も議論されました。 上限問題「Ｎを与えられた自然数とする。また、１以上Ｎ以下の相異なる５個の 数字からなる集合、及び相異なる３個の数字からなる集合をそれぞれ５−集合、 ３−集合ということにする。 このとき、次の条件を満たす５−集合の集合Ｘを考える。 条件Ｃ 任意の３−集合が、Ｘに含まれる何れかの５−集合に含まれる。 条件Ｄ Ｘは条件Ｃを満たす集合のうちで位数が最小である。 これらの条件を満たすＸを具体的に求めよ」 この問題の解が、ロト問題の解の上限を与えることはすぐわかると思います。 この問題に対する掲示板での最良の結果は次のとおりでした。 Ｎ＝８ ８個 Ｎ＝９ １２個 Ｎ＝１０ １７個 で、昨日の続きですが、 「３個の数字から２個以上」でＮ＝９の場合の最適な個数は１２個です。 を１２個以下に訂正します。１２個が最適だと言ったのは５，３を３，２に変えた 上限問題の場合の話でした。 この上限問題で１２が最適であることは、有限幾何学における（有限）アフィン 平面を用いてわかります。 Ｎ次のアフィン平面とは、次のような集合から構成される幾何学的構造です。 １ Ｎ＾２個の点を持つ集合Ａ ２ Ａの部分集合（直線と呼ぶ）からなるある集合Ｌで次の条件を満たす。 条件Ｅ 全ての直線はＮ個の点を含む 条件Ｆ 任意の相異なるＡの２点を含む直線が唯ひとつ存在する。 また、Ｎ次のアフィン平面はＮ（Ｎ＋１）本の直線を持つことも言えます。 従って、特に、３次のアフィン平面の直線全体は上限問題の解で、従って、最適解は 直線の本数である１２ということが言えます。 昨日数学的に興味深いといったのは、こちらの上限問題の話でした。Ｎ＝９の場合のそれは、カークマンの１５人の女学生の問題（興味があれば検索してください）の簡略バージョンにもなっています。 なお、代数学（特に有限体）の知識がアフィン平面を具体的に構成するときに必要になりますが、そこまで触れるとほとんどの人が退いてしまいそう（とっくに退いているかも知れないが）なのでやめておきます。
> ただ、Ｎ＝９の場合は数学的にかなり興味深い事実があります。 それは楽しみです。代数は大丈夫（なはず (^_^;)）なので解説お願いします。
三吉様今晩は。 ＞「３個の数字から２個以上」についてはすでに何かしらの公式が ＞見つかっていますか？ わかりませんが、多分無いと思います。 ただ、Ｎ＝９の場合は数学的にかなり興味深い事実があります。 もう遅いので詳細は明日にして、この場合の結果だけ述べると最適な個数は１２個です。 なお、この結果は、プログラムで検索したものでなく、純粋に理論的に得られたものです。 詳細を述べるためには、数学的（特に代数方面）な議論が必要になりますが、 この辺は如何でしょうか。