お気づきの点や感想要望などなんでもOK!
塗り壁さん、こんばんわ。 グラフ理論に強そうなので教えていただけると幸いです。 1年程前にアルカン(化学式:CnH2n+2)の構造異性体の数を求めるという 話題がありました。その時、グラフ理論を使って解く方法があることはわかりましたが、 具体的な方法は私には解かりませんでした。(本を探したが見つからなかった) もし、ご存じでしたら教えていただけないでしょうか?
訂正ばかりで申し訳ありません。先ほどの投稿に、ごみが混じってしまいました。 後ろの2行は無視して下さい。
高橋さん今晩は (実は、私の本名も高橋なので、deepgreenさんの投稿の一行目で どっきりしたりもしました) 記載のホームページ拝見しました。ただ、具体的なアルゴリズムが無いのが ちょっと残念。 アルゴリズムによっては、LightsOutだけでなく8めぐりやその他もろもろの反転問題も 全く同じロジックで解けるはず。そのへんがグラフを扱う大きなメリットですね。 がっかりしました。 は意見しました。
高橋さん、一言多いかもしれませんが、... グラフ理論のアプローチでライツアウトを解いたという事実は貴重な情報だと思います。 この卒論へのリンクを追加していただいたほうがよいのではないでしょうか?
塗り壁さん、はじめまして。 貴重な情報をありがとうございます。ライツアウトの記事を書いた直後にネットサー フィンで下記のURLを発見して、この人は間違い無く同じ方法で解いていると確信し まして、こう言うアルゴリズムがグラフ理論の中にあるのだろうと思いこんでしまいま した。 「多項式アルゴリズム」というのは「多項式時間計算可能アルゴリズム」と言う意味で 問題の大きさ(N)について探索時間が、N乗レベルで増大するものではなくNの定数乗 レベルで増大するアルゴリズムのグループを総称してそう呼ぶのだ。と言うことなので すね。勉強になりました。(さっそく追記を削除したいと思います。)http://www.yilab.tutics.tut.ac.jp/abstract/aoki.html
前便で、最後の行が日本語としておかしいので次のように訂正します。 多項式云々と有りましたが、もしかすると多項式時間計算可能アルゴリズムの事でしょうか。 そうならば、これは特定のアルゴリズムでなくコンピューターで実行可能なアルゴリズムの グループを表わします。(実行可能とは、常識的な範囲内で終了できるもの、実行に、 何億年もかかったりはしないようなアルゴリズムです)
はじめまして、塗り壁と言います。パズル及びプログラミングに興味が有るので、 時々覗かせてもらってます。私はグラフ理論をベースにプログラミングをしているので、 ライツアウトの回答のところの追記が気になりました。記載のアルゴリズムは 連立方程式の話で、グラフ理論に関係しているようには見えないのですが。 多項式云々と有りましたが、もし多項式時間計算可能アルゴリズムの事でしょうか。
パズル・ゲーム・クイズのページです。毎日更新、誰でも遊べる。いつも新鮮な情報が有ります。http://www2.odn.ne.jp/~cbp61410/
昔、パズラー(世界文化社)という雑誌で、19個の問題は見た覚えがあります。 それ以下は、ちょっとないです。。 18個というと、各ブロックに平均で数字2つの割合ですよね。わたしには、 多分、作れないですね (-_-;; 存在するなら、ぜひ、解いてみたいなぁ。http://motokiya.pobox.ne.jp/mugimaru/
麦丸さん、はじめまして。 ナンプレ(数独)にかなり精通していようですね。9×9通常ナンプレでの初期ヒント数 (最初に数字が表示されているマスの数)で最小はどの程度なのか(究極のナンプレ問題) 18個,17個の具体例をご存知でしょうか。存在するそうですが未だ見た事がないのです。