お気づきの点や感想要望などなんでもＯＫ！
マナさんの「NIFTY-Serveの庭」にある、ナンバープレースパズルの庭 にはＮ＝２０の問題のありました。【問題１０】がそれです。 ＵＲＬを下に書きました。また、五条さんの「パズルの小部屋」には ナンバープレース(その６のその２)にＮ＝２０の問題がありましたが、 残念ながら重複解のあるものでした。 んー、Ｎ＝２０は可能ですね。deepgreenさんのＮ＝１８という予想 は、結構いい線いっているのかも知れませんね。http://www2s.biglobe.ne.jp/~garden_b/wor_puz/nif_w/nif.html
チョット気になったので補足します。 ＞「短いときは００をpadding」という部分におやっと思いました。その後ろに ＞接続されるビット列を正確に考慮する必要はないのだろうかと。私は６通りの ＞つなぎ方を生成することで同じ長さにしてその中から最小のものを選択するよ ＞うにしたのですが、そこまでしなくても結果が同じだったので、これは私の思 ＞い過ごしだったかも知れません。 高橋さんが気にしているのは以下のケースでｂ＝ｃ１の時ではないかと思います。 【Ｂ】： ｂ 【Ｃ】： ｃ1ｃ2 （ｃ１はｂと同じ長さ、残りをｃ2） 【Ｄ】： ｄ この場合に、ｂｄｃ１ｃ２とｃ１ｃ２ｂｄ（＝ｂｃ２ｂｄ） とを比較する必要が あるのではないかという事ですね。 しかし、【Ｃ】の中には【Ｂ】を部分列として含むことは後述の理由によりおこり えないので（つまり、ｂ≠ｃ１）、【Ｂ】と【Ｃ】の比較は、ｂ，ｃ１の部分のみ で判断できてしまいます。その理由は、 仮にｂ＝ｃ１というケースがあったとすると、１つのBitmapが異なる２つの構造 体を表わしている事になります。 （１）【Ｂ】として完結している形 （２）【Ｃ】の一部としてｃ２への結合をもつ炭素を含む形 （１）と（２）は矛盾しています。従って、ｂ＝ｃ１はありえません。 ［究極のナンプレ問題］ >究極のナンプレ問題の実験的試みとしてどん欲にＮの値が小さいものを探すプログラムを作って >みました。このプログラムは乱数を用いて「反復再試」(反復深化ではない)という独自のロジ >ックで探索を行います。実行すると数分後に、Ｎ＝２１のナンプレ問題を発見しました。（下 >図） 意外と簡単に進みましたね。私の方も準備をはじめています。その一環で藤原博文さんのＨＰに あるナンプレ問題集を解いていてＮ＝２１（Ｎｏ．８３）を見つけました。Ｎ＝２０はありませんでした。 私の予想は、Ｎ＝１８あたりですが、そこまでいけますかね？
究極のナンプレ問題の実験的試みとしてどん欲にＮの値が小さいものを探す プログラムを作ってみました。このプログラムは乱数を用いて「反復再試」 (反復深化ではない)という独自のロジックで探索を行います。実行すると 数分後に、Ｎ＝２１のナンプレ問題を発見しました。（下図） 欠点は、乱数を使用するのでコンパイラによって異なった探索進行になること と、Ｎの最小値が保証されないことです。つまり、このプログラムがＮ＝２１ のナンプレ問題を発見したからと言ってＮの最小値が２１であることにはなり ません。本質的な解決にはなっていない便宜的な実験にすぎないのです。 少なくともＮ＝２１のナンプレ問題は可能であることが立証されただけです。 Ｎ＝２１ +−+−+−+−+−+−+−+−+−+ |１| | | | | | | |９| +−+−+−+−+−+−+−+−+−+ | |５| |７| | | |２| | +−+−+−+−+−+−+−+−+−+ | |８| | | |３| | | | +−+−+−+−+−+−+−+−+−+ | |１| | |６|５|８| | | +−+−+−+−+−+−+−+−+−+ | |６| | | | | | | | +−+−+−+−+−+−+−+−+−+ | | |７|２| | | | |５| +−+−+−+−+−+−+−+−+−+ | |３| | | | | | |８| +−+−+−+−+−+−+−+−+−+ | | |２|９|７| | | | | +−+−+−+−+−+−+−+−+−+ | | | | | | |６| | | +−+−+−+−+−+−+−+−+−+
A1の方法はどうにか自力でプログラムが書けました。deepgreenさんご指摘のように Ｎ＝２０程度までが限界のようでした。このプログラムの唯一の難所は前回書いた ように、局面からBitMapの最小値を得る部分ですがdeepgreenさんの説明によるもの と私の書いたものはちょっと違う感じがしました。A1addendum.txtのこの部分です。 (4) 【Ｂ】【Ｃ】【Ｄ】は、この関数をrecursive callして作成する。 （以下のBitmap形式が作られる） 【Ｂ】 ０１０１１０００００ 【Ｃ】 １１００００００ 【Ｄ】 １００００１００ (5) 【Ｂ】【Ｃ】【Ｄ】を比較して､小さい順にならべる。 （比較は､文字列比較と同様に、先頭から順番に比較する。短いときは００をpadding） −−＞ 【Ｂ】＜【Ｄ】＜【Ｃ】となる 「短いときは００をpadding」という部分におやっと思いました。その後ろに接続される ビット列を正確に考慮する必要はないのだろうかと。私は６通りのつなぎ方を生成すること で同じ長さにしてその中から最小のものを選択するようにしたのですが、そこまでしなく ても結果が同じだったので、これは私の思い過ごしだったかも知れません。 A2の方法はあきらめました。(どう考えても私には理解できない) ［究極のナンプレ問題？］これはナンプレのソルバーを作ったり問題を作成した経験のある 方なら誰しも一度は考えたことがあるのではないでしょうか。そう言うことからして、既に この結果を得ている人がいたとしてもおかしくは無い気がします。私も初めてナンプレの ソルバーを作った時に同じことを考えたことがあります。しかし、その時は最終結果まで には至りませんでした。 この問題は私もとても興味があります。とりあえずＮ＝２２の問題をプログラムで１つでも 作れるかを試みて、それが存在していればＮ＝２１へ挑戦すると言う原始的な方法で手応え を掴んでみることから始めるのも、ひとつの手かと思っています。 どなたか情報をお持ちの方がおられましたら、是非教えてください。
高橋さんのコメントがあったので少し説明を追加しました。(前と同じＵＲＬです） A1addendumは、プログラムを作ったあとで見ていただく方が良いでしょう。 A2memoは、(２日かけて）丁寧に書いたつもりでしたが、それでも抜けがありますね。 A2addendumを作りましたので見てください。説明とは本当に難しいものです。 ところで、道草のついでに､前から気にしていた問題をやってみようと思っています。 以下のようなナンバープレースの問題ですが、どなたかご存じの方がいらっしゃいま したら教えてください。 ［究極のナンプレ問題？］ ちょっと大袈裟ですね。 実は最小問題です。 皆さんご存知のように、ナンプレは、９Ｘ９の中のいくつかのマスに数字が与えられ たとき、残りのマスの数字がｕｎｉｑｕｅに決まるという問題です。 （これをコンピュータで解くのは、簡単なのであまり面白くありません） ナンプレの難しさは、最初に指定するマスの数Ｎでほぼ決まると思います。Ｎが小さ くなるほど難しいでしょう。私の持っている本では、Ｎ＝２３が最小でした。 私が気にしているのは、 「このＮはどこまで小さくできるのでしょうか？ そして そのときの配置はどのようになるのでしょうか？」 ということです。 この問題は、コンピュータで解こうとしても簡単にはできません。単純な方法では、 膨大な組合わせをテストしなければならないので、いつになっても答えが出てこない という結果になるでしょう。どうやってコンピュータで扱える範囲まで組合わせを落 とし込むかというところに面白さがあるのです。しかし、その方法が？？？です。 高橋さん、すみません。かけこみ寺にしちゃっていいのかな？http://www2.tokai.or.jp/deepgreen/shortnotes/alkane/index.htm
deepgreenさんには本当に驚かされてしまいます。今回で何度目のカルチャーショック になるでしょうか。とても刺激的です。本当にありがとうございます。さて、 A2の方法は理解に苦しんでますが、A1の方法はとても興味深く拝見させて頂きました。 スタックを使って局面を表現(圧縮,展開)する訳ですね。パズル的に解くならこの方法 しか無いようですね。お見事と言うしかない問題解析力でうらやましいです。 ところでBitMap形式から局面を展開するのは簡単なようですが、その逆の場合だと、 BitMap値が最小(標準形)になるものを探す必要があるので、とても大変な気がします。 プログラム作成能力が問われる、その部分だけでも充分に面白いパズル問題のようです。 実は、私もdeepgreenさんの解説文も参考にして独自にプログラムを書いたのですが、 局面をBitMap形式に圧縮する部分で、マジにつまずいています。とほほ。
deepgreenです。 以前に解けると言ってしまった手前、エントリしない訳にもいきませんね。 一応、２通りの方法（パズルとして、組合せ論として）で解いてみました。 下記のＵＲＬに置いてあります。 拙い説明ですので、ご不明な点は遠慮なくどうぞ。 http://www2.tokai.or.jp/deepgreen/shortnotes/alkane/index.htm
問題の意とするところが良く理解できました。ありがとうございます。しかし、 まさに超難問ですね。図形問題として処理するには同型チェックが複雑すぎるし 数量問題として処理するには相当に深い事前考察が必要です。 どのように扱えば良いのかデータ構造の持ち方それ自体が最大の難関のようです。 N88basic(86)で n=40 まで42分で計算した方の説明文を読んでも全く理解出来 ない低レベルな私にはサジを投げるしかないようです。 化学の専門用語を一切使用しないでソースコードとプログラムの説明を提示出来 る方はいないものでしょうか。この場で募集します。
＞高橋さんへ > Ｃ原子ｎ個を持つアルカン系炭化水素の、構造異性体の数は？ (1) 一つのＣには、４つまでＣをつなげる事が出来る。 Ｃ │ Ｃ─Ｃ─Ｃ │ Ｃ ↑こんなカンジ（水素は省略） (2) Ｃがループを作ってはならない。 Ｃ─Ｃ Ｃ─Ｃ ／ ＼ │ │ Ｃ Ｃ─Ｃ Ｃ─Ｃ ＼ ／ Ｃ─Ｃ ↑これらはダメな例 これらの条件のもと、Ｃの数をｎとした時に何パターンの形が作れるか…って問題です。 例えば、Ｃが三つなら、１通り。 Ｃ─Ｃ─Ｃ Ｃが４つなら、２通り。 Ｃ │ Ｃ─Ｃ─Ｃ Ｃ─Ｃ─Ｃ─Ｃ Ｃが６つなら、５通り。 Ｃ Ｃ │ │ Ｃ─Ｃ─Ｃ─Ｃ─Ｃ Ｃ─Ｃ─Ｃ─Ｃ─Ｃ Ｃ Ｃ Ｃ │ │ │ Ｃ─Ｃ─Ｃ─Ｃ Ｃ─Ｃ─Ｃ─Ｃ Ｃ─Ｃ─Ｃ─Ｃ─Ｃ─Ｃ │ Ｃ と、まあこんなカンジ…でいいのだろうか＾＾； ＞直井さんへ この問題についてネットを漁ってみたら、次のページを見つけたので紹介します。http://cssjweb.chem.eng.himeji-tech.ac.jp/jcs/v5n2/a3/abstj.html
高橋さん，どうもありがとうございます． 私は現在JAVAを勉強中で勉強の一環として ナンプレのプログラムを作成中です． ただどうしてもアルゴリズム的にわからないところがあり 困っていました． このソースを見て勉強したいと思います． はやく一人でいろいろなプログラムを作れるよう がんばりたいとおもいます．