ホームページへ戻る  書き込みリストへ戻る
「コンピュータ&パズル」訪問者の自由メッセージコーナー

お気づきの点や感想要望などなんでもOK!


究極のナンプレ問題 投稿者:高橋謙一郎  投稿日:07月29日(木)12時53分14秒

マナさんの「NIFTY-Serveの庭」にある、ナンバープレースパズルの庭
にはN=20の問題のありました。【問題10】がそれです。
URLを下に書きました。また、五条さんの「パズルの小部屋」には
ナンバープレース(その6のその2)にN=20の問題がありましたが、
残念ながら重複解のあるものでした。

んー、N=20は可能ですね。deepgreenさんのN=18という予想
は、結構いい線いっているのかも知れませんね。

http://www2s.biglobe.ne.jp/~garden_b/wor_puz/nif_w/nif.html


re:次ぎは[究極のナンプレ問題?]..  投稿者:deepgreen  投稿日:07月26日(月)20時48分49秒

チョット気になったので補足します。

>「短いときは00をpadding」という部分におやっと思いました。その後ろに
>接続されるビット列を正確に考慮する必要はないのだろうかと。私は6通りの
>つなぎ方を生成することで同じ長さにしてその中から最小のものを選択するよ
>うにしたのですが、そこまでしなくても結果が同じだったので、これは私の思
>い過ごしだったかも知れません。

高橋さんが気にしているのは以下のケースでb=c1の時ではないかと思います。
  【B】: b
  【C】: c1c2     (c1はbと同じ長さ、残りをc2)
  【D】: d
この場合に、bdc1c2とc1c2bd(=bc2bd) とを比較する必要が
あるのではないかという事ですね。
しかし、【C】の中には【B】を部分列として含むことは後述の理由によりおこり
えないので(つまり、b≠c1)、【B】と【C】の比較は、b,c1の部分のみ
で判断できてしまいます。その理由は、

  仮にb=c1というケースがあったとすると、1つのBitmapが異なる2つの構造
  体を表わしている事になります。
      (1)【B】として完結している形
      (2)【C】の一部としてc2への結合をもつ炭素を含む形
   (1)と(2)は矛盾しています。従って、b=c1はありえません。

[究極のナンプレ問題]
>究極のナンプレ問題の実験的試みとしてどん欲にNの値が小さいものを探すプログラムを作って
>みました。このプログラムは乱数を用いて「反復再試」(反復深化ではない)という独自のロジ
>ックで探索を行います。実行すると数分後に、N=21のナンプレ問題を発見しました。(下
>図)
意外と簡単に進みましたね。私の方も準備をはじめています。その一環で藤原博文さんのHPに
あるナンプレ問題集を解いていてN=21(No.83)を見つけました。N=20はありませんでした。
私の予想は、N=18あたりですが、そこまでいけますかね?



究極のナンプレ問題 投稿者:高橋謙一郎  投稿日:07月26日(月)12時23分00秒

究極のナンプレ問題の実験的試みとしてどん欲にNの値が小さいものを探す
プログラムを作ってみました。このプログラムは乱数を用いて「反復再試」
(反復深化ではない)という独自のロジックで探索を行います。実行すると
数分後に、N=21のナンプレ問題を発見しました。(下図)

欠点は、乱数を使用するのでコンパイラによって異なった探索進行になること
と、Nの最小値が保証されないことです。つまり、このプログラムがN=21
のナンプレ問題を発見したからと言ってNの最小値が21であることにはなり
ません。本質的な解決にはなっていない便宜的な実験にすぎないのです。

少なくともN=21のナンプレ問題は可能であることが立証されただけです。

N=21
+−+−+−+−+−+−+−+−+−+
|1| | | | | | | |9|
+−+−+−+−+−+−+−+−+−+
| |5| |7| | | |2| |
+−+−+−+−+−+−+−+−+−+
| |8| | | |3| | | |
+−+−+−+−+−+−+−+−+−+
| |1| | |6|5|8| | |
+−+−+−+−+−+−+−+−+−+
| |6| | | | | | | |
+−+−+−+−+−+−+−+−+−+
| | |7|2| | | | |5|
+−+−+−+−+−+−+−+−+−+
| |3| | | | | | |8|
+−+−+−+−+−+−+−+−+−+
| | |2|9|7| | | | |
+−+−+−+−+−+−+−+−+−+
| | | | | | |6| | |
+−+−+−+−+−+−+−+−+−+


次ぎは[究極のナンプレ問題?].. 投稿者:高橋謙一郎  投稿日:07月22日(木)18時02分16秒

A1の方法はどうにか自力でプログラムが書けました。deepgreenさんご指摘のように
N=20程度までが限界のようでした。このプログラムの唯一の難所は前回書いた
ように、局面からBitMapの最小値を得る部分ですがdeepgreenさんの説明によるもの
と私の書いたものはちょっと違う感じがしました。A1addendum.txtのこの部分です。

(4) 【B】【C】【D】は、この関数をrecursive callして作成する。
    (以下のBitmap形式が作られる)
        【B】   0101100000
        【C】   11000000
        【D】   10000100

(5) 【B】【C】【D】を比較して、小さい順にならべる。
    (比較は、文字列比較と同様に、先頭から順番に比較する。短いときは00をpadding)
     −−>  【B】<【D】<【C】となる

「短いときは00をpadding」という部分におやっと思いました。その後ろに接続される
ビット列を正確に考慮する必要はないのだろうかと。私は6通りのつなぎ方を生成すること
で同じ長さにしてその中から最小のものを選択するようにしたのですが、そこまでしなく
ても結果が同じだったので、これは私の思い過ごしだったかも知れません。

A2の方法はあきらめました。(どう考えても私には理解できない)

[究極のナンプレ問題?]これはナンプレのソルバーを作ったり問題を作成した経験のある
方なら誰しも一度は考えたことがあるのではないでしょうか。そう言うことからして、既に
この結果を得ている人がいたとしてもおかしくは無い気がします。私も初めてナンプレの
ソルバーを作った時に同じことを考えたことがあります。しかし、その時は最終結果まで
には至りませんでした。

この問題は私もとても興味があります。とりあえずN=22の問題をプログラムで1つでも
作れるかを試みて、それが存在していればN=21へ挑戦すると言う原始的な方法で手応え
を掴んでみることから始めるのも、ひとつの手かと思っています。

どなたか情報をお持ちの方がおられましたら、是非教えてください。


re:RE:re:Re:んー(CnH2n+2の構造異性体の数)  投稿者:deepgreen  投稿日:07月18日(日)00時08分58秒

高橋さんのコメントがあったので少し説明を追加しました。(前と同じURLです)
A1addendumは、プログラムを作ったあとで見ていただく方が良いでしょう。
A2memoは、(2日かけて)丁寧に書いたつもりでしたが、それでも抜けがありますね。
A2addendumを作りましたので見てください。説明とは本当に難しいものです。

ところで、道草のついでに、前から気にしていた問題をやってみようと思っています。
以下のようなナンバープレースの問題ですが、どなたかご存じの方がいらっしゃいま
したら教えてください。

[究極のナンプレ問題?]
ちょっと大袈裟ですね。 実は最小問題です。
皆さんご存知のように、ナンプレは、9X9の中のいくつかのマスに数字が与えられ
たとき、残りのマスの数字がuniqueに決まるという問題です。
(これをコンピュータで解くのは、簡単なのであまり面白くありません)
ナンプレの難しさは、最初に指定するマスの数Nでほぼ決まると思います。Nが小さ
くなるほど難しいでしょう。私の持っている本では、N=23が最小でした。
私が気にしているのは、
    「このNはどこまで小さくできるのでしょうか? そして
      そのときの配置はどのようになるのでしょうか?」
ということです。

この問題は、コンピュータで解こうとしても簡単にはできません。単純な方法では、
膨大な組合わせをテストしなければならないので、いつになっても答えが出てこない
という結果になるでしょう。どうやってコンピュータで扱える範囲まで組合わせを落
とし込むかというところに面白さがあるのです。しかし、その方法が???です。

高橋さん、すみません。かけこみ寺にしちゃっていいのかな?

http://www2.tokai.or.jp/deepgreen/shortnotes/alkane/index.htm


RE:re:Re:んー(CnH2n+2の構造異性体の数) 投稿者:高橋謙一郎  投稿日:07月15日(木)17時17分24秒

deepgreenさんには本当に驚かされてしまいます。今回で何度目のカルチャーショック
になるでしょうか。とても刺激的です。本当にありがとうございます。さて、

A2の方法は理解に苦しんでますが、A1の方法はとても興味深く拝見させて頂きました。
スタックを使って局面を表現(圧縮,展開)する訳ですね。パズル的に解くならこの方法
しか無いようですね。お見事と言うしかない問題解析力でうらやましいです。

ところでBitMap形式から局面を展開するのは簡単なようですが、その逆の場合だと、
BitMap値が最小(標準形)になるものを探す必要があるので、とても大変な気がします。
プログラム作成能力が問われる、その部分だけでも充分に面白いパズル問題のようです。

実は、私もdeepgreenさんの解説文も参考にして独自にプログラムを書いたのですが、
局面をBitMap形式に圧縮する部分で、マジにつまずいています。とほほ。


re:Re:んー(CnH2n+2の構造異性体の数)  投稿者:deepgreen  投稿日:07月13日(火)01時09分07秒

deepgreenです。

以前に解けると言ってしまった手前、エントリしない訳にもいきませんね。

一応、2通りの方法(パズルとして、組合せ論として)で解いてみました。
下記のURLに置いてあります。
拙い説明ですので、ご不明な点は遠慮なくどうぞ。

  http://www2.tokai.or.jp/deepgreen/shortnotes/alkane/index.htm




Re:んー(CnH2n+2の構造異性体の数) 投稿者:高橋謙一郎  投稿日:07月07日(水)10時03分06秒

問題の意とするところが良く理解できました。ありがとうございます。しかし、
まさに超難問ですね。図形問題として処理するには同型チェックが複雑すぎるし
数量問題として処理するには相当に深い事前考察が必要です。

どのように扱えば良いのかデータ構造の持ち方それ自体が最大の難関のようです。
N88basic(86)で n=40 まで42分で計算した方の説明文を読んでも全く理解出来
ない低レベルな私にはサジを投げるしかないようです。

化学の専門用語を一切使用しないでソースコードとプログラムの説明を提示出来
る方はいないものでしょうか。この場で募集します。


んー。 投稿者:小悪魔  投稿日:06月27日(日)10時45分38秒

>高橋さんへ

> C原子n個を持つアルカン系炭化水素の、構造異性体の数は?

(1) 一つのCには、4つまでCをつなげる事が出来る。
  C
  │
C─C─C
  │
  C
↑こんなカンジ(水素は省略)

(2) Cがループを作ってはならない。
     C─C
C─C  /  \
│ │ C   C─C
C─C  \  /
     C─C
↑これらはダメな例

 これらの条件のもと、Cの数をnとした時に何パターンの形が作れるか…って問題です。


 例えば、Cが三つなら、1通り。

C─C─C


 Cが4つなら、2通り。
  C
  │
C─C─C C─C─C─C


 Cが6つなら、5通り。
  C           C
  │           │
C─C─C─C─C C─C─C─C─C

  C       C C
  │       │ │
C─C─C─C C─C─C─C C─C─C─C─C─C
  │
  C


 と、まあこんなカンジ…でいいのだろうか^^;


>直井さんへ

 この問題についてネットを漁ってみたら、次のページを見つけたので紹介します。

http://cssjweb.chem.eng.himeji-tech.ac.jp/jcs/v5n2/a3/abstj.html


ありがとうございます 投稿者:riry  投稿日:06月20日(日)00時13分30秒

高橋さん,どうもありがとうございます.
私は現在JAVAを勉強中で勉強の一環として
ナンプレのプログラムを作成中です.
ただどうしてもアルゴリズム的にわからないところがあり
困っていました.
このソースを見て勉強したいと思います.
はやく一人でいろいろなプログラムを作れるよう
がんばりたいとおもいます.


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