2000.05.19 deepgreen 「解の存在条件式のパターンと０解のｐｕｓｈパターンが一致する」ことの 説明です。（証明と言えるほど厳密ではないので） □問題の定義 ０解：反転する部分が全くないようなある特定のｐｕｓｈパターン (ある複数ボタンを押すと何も押さないのと同じになること） ５ｘ５のライツアウトの場合 解の存在条件式（の1つ） ０解 ａ−ｃ−ｅ １０１０１ ｆ−ｈ−ｊ １０１０１ −−−−− ０００００ ｐ−ｒ−ｔ １０１０１ ｕ−ｗ−ｙ １０１０１ 要するに、言いたいことは、 （１）解の存在条件式が分かると、そのパターンから０解を生成できる （２）逆に、０解が分かると、それから解の存在条件式を生成できる □連立式の作成 @ 問題面での位置および解のパターンでの位置を以下のように表現する 分かり易くするために、問題面は小文字、解のパターンは大文字とする。 ［問題面］ ［解］ ａｂｃｄｅ ＡＢＣＤＥ ｆｇｈｉｊ ＦＧＨＩＪ ｋｌｍｎｏ ＫＬＭＮＯ ｐｑｒｓｔ ＰＱＲＳＴ ｕｖｗｘｙ ＵＶＷＸＹ Ａの位置をｐｕｓｈすると、ａ，ｂ，ｆの位置が反転する。これを、 式01 A == （a,b,f) と記述することにする。(a,b,f)をＡの構成要素と呼ぶことにする。 同様に、 式02 B == （a,b,c,g) 式03 C == (b,c,d,h) ・・・ 式25 Y == （t,x,y) となる。 A これを、以下のように略記することにします。 式xx 構成要素 ｐｕｓｈ位置 1 ab---f------------------- A------------------------ 2 abc---g------------------ -B----------------------- 3 -bcd---h----------------- --C---------------------- 4 --cde---i---------------- ---D--------------------- 5 ---de----j--------------- ----E-------------------- 6 a----fg---k-------------- -----F------------------- 7 -b---fgh---l------------- ------G------------------ 8 --c---ghi---m------------ -------H----------------- 9 ---d---hij---n----------- --------I---------------- 10 ----e---ij----o---------- ---------J--------------- 11 -----f----kl---p--------- ----------K-------------- 12 ------g---klm---q-------- -----------L------------- 13 -------h---lmn---r------- ------------M------------ 14 --------i---mno---s------ -------------N----------- 15 ---------j---no----t----- --------------O---------- 16 ----------k----pq---u---- ---------------P--------- 17 -----------l---pqr---v--- ----------------Q-------- 18 ------------m---qrs---w-- -----------------R------- 19 -------------n---rst---x- ------------------S------ 20 --------------o---st----y -------------------T----- 21 ---------------p----uv--- --------------------U---- 22 ----------------q---uvw-- ---------------------V--- 23 -----------------r---vwx- ----------------------W-- 24 ------------------s---wxy -----------------------X- 25 -------------------t---xy ------------------------Y B 次に、＋演算を以下のように定義する。 Ｘ＋Ｙ ＝＝ （Ｘ，Ｙの片方にしか存在しないもののリスト） つまり、Ｘ，Ｙ共通に存在する要素を取り除いたもの Ｂ＋Ｃの場合、ｂ，ｃが共通なので、ａ，ｄ，ｇ，ｈがのこり、 Ｂ＋Ｃ ＝＝ （ａ，ｄ，ｇ，ｈ） となる。この式の意味は､「Ｂ，Ｃをｐｕｓｈすると、ａ，ｄ，ｇ，ｈが反転 する」ということになりますが、実際の操作と一致しています。 つまり、複数の個所をｐｕｓｈする操作は、上記の＋演算となります。 □連立式の解 ところで、この連立式は見覚えがあるでしょう。高橋謙一郎さのＨＰで、解 を求める時に作成したものと全く同じです。しかも、＋演算も同様に排他的 論理和として定義されています。 従って、これをａ，ｂ，ｃ，．．．ｙについて解くと、 式xx 構成要素 ｐｕｓｈ位置 1 a-----------------------y -BCD---H-J---NO----T----- 2 -b---------------------x- AB-DE-G-----MNO---S------ 3 --c--------------------xy A-CDEF-HI---MN-PQRST-V--- 4 ---d-------------------x- ABC---G---------Q---UVW-- 5 ----e-------------------y -BC-EF----K-M-O--R-TUV--- 6 -----f-----------------xy --C-E-GH-J--M-----ST----- 7 ------g------------------ -B-D-FG-IJ---N-PQR---V--- 8 -------h---------------xy A-C--F-HI-----OP-R-TU-W-- 9 --------i---------------- --C---GHI-K--NOP--S--VW-- 10 ---------j-------------xy A----FG---K-M-O-QR-T--W-- 11 ----------k------------x- ----E---IJ--M-OPQRS--V--- 12 -----------l-----------x- ----------------Q---UVW-- 13 ------------m------------ -BC-EF---JK-MN---R--UV--- 14 -------------n---------x- ABC---G-I---MNO---S------ 15 --------------o--------x- AB--E--HIJK--NOPQ-S-U---- 16 ---------------p-------xy --C---GHI-K---OP-R-TU-W-- 17 ----------------q-------- --CD--G--JKL--O-QRS---W-- 18 -----------------r-----xy --C-E-GH-JK-M--PQ-STU---- 19 ------------------s------ -BC--F--I-K--NO-QRS---W-- 20 -------------------t---xy A-C-EF-H-J-----P-R-TU-W-- 21 --------------------u---y ---DE--H---LM-OP-R-TUV--- 22 ---------------------v-x- --CDE-G-I-KLM-------UVW-- 23 ----------------------wxy ---D---HIJ-L---PQ-ST-V--- 24 ------------------------- -BCD-F-H-JKL-NOP-R-T-VWX- 25 ------------------------- A-C-EF-H-J-----P-R-TU-W-Y （解釈） 式01は、「B,C,D,H,J,N,O,Tをｐｕｓｈすると、ａとｙが反転する」と いう意味です。 では、式24，式25はどのような意味なのだろうか？ 左辺は反転するものなし＝無操作であり、右辺はｐｕｓｈパターンと なっているので、これは、０解ということになります。 つまり、式24，式25は、０解の存在を示している。 ところで、「以前は、式24，式25が解の存在条件式を表していた」が､ その「同じ式が０解を定義している」点に着目してください。 これこそが、最初に求めていた結論である。 □まとめ 前回の方法と今回のアプローチとの関係を整理すると、 ［前回］ 問題面 pushﾊﾟﾀｰﾝ □□□ □■□ □■□ <==== ■■■ □□□ □■□ 問題面の■を反転させる条件（右のpushパターン）を求め､その解法の 結果として、解の存在条件が判明した。 ［今回］ pushﾊﾟﾀｰﾝ 問題面 □□□ □■□ □■□ ====> ■■■ □□□ □■□ 「pushパターンの■を反転させると問題面のパターンが反転する」とい うルールそのものの関係式を定義し、ｐｕｓｈパターンの重ね合わせが ＋演算（排他的論理和）で表現できることを確認した。この結果、今回 の連立式が前回と全く同じものとなった。その解法の結果を解釈するこ とで０解の存在パターンを求めることができた。 何故、このような結果が得られたかは、いままでの経過よりあきらかで ある。前回と今回のアプローチは全く同じパターンになっていることが その原因です。 もし、ルールとして以下のような反転パターンのゲームを考えると、 このような結果がえられないことは明らかであろう。 pushﾊﾟﾀｰﾝ 問題面 □□□ □□■ □■□ ====> ■■□ □□□ □■□ （おわり）