🚀 go-pugleaf

福林＠べっこあめ　と申します。はじめまして。

最近、NetNewsを読む環境を手に入れ、このニュースグループを
遡って読ませていただきました。

「ライツアウト」のことが話題になっていて興味深く読みました。
やや浦島フォローですが、お付き合いください。

このパズルは確か、一昨年のＮＴＶのスペシャル番組で、私の同級生の
吉澤くん（当時中３）が解かされた(^_^;)問題ではなかったかと記憶
します。番組ではPeter Frankl氏が解説しておられました。ちなみに
吉澤くんは今年度のIMOメダリストです。

私も学校の仲間と、10月中頃から、中間テスト中の現実逃避に(^_^;)
議論しました。その時に、性質を探る意味で作った「解探索プログラム」
があります。
始めは全検索のものを作って、「すべて０の状態」に対する解を１つ見
出しました。そして、その解と、その解の回転形とのxorをとることに
よって、（「何も押さない」を含め）て４つの解があることを得ました。
問題と解とが１：４。解がある確率は１／４で、あるとすれば４個に限
るというわけですね。
＃どこかで聞いた群論の言葉を使えば明快に言えそうなのですが
＃自信も気合も足りませんので控えます。。

そのことを参考にして検索ループ最大回数を2^21にまで落としたものを、
現在の最終バージョンとしてハードディスクにしまってあるのですが、
どんくさい代物で、i486DX4/60MHzの環境で４０秒程度かかってしまい
ます。与えられた問題に対する解があるか否かを一目で見分けられれば
いいのですが、うまい方法を思いつきません。
このことについては、同級生の山下くんから説明を受けたのですが、ど
うも納得できぬまま失念してしまいました。

    明快な方法があるのでしょうか。
    25以外の場合に拡張した場合についても興味があります。

＃私はi86 assembler出身でいまだＣに慣れず、かなりたどたどしいですが、
＃解検索プログラム、見てみたいとおっしゃる方、いらっしゃいます？ ^^;

-- 
=========================================================================
 E-mail:1-pei@gem.bekkoame.or.jp     de JJ3IKY  灘高２ (49回生) 福林一平
=========================================================================