・細江さんから頂いたLightsOutの解を求める、EXELファイル
| ■考察１（３３,５５４,４３２通りの組合せ） |
１．同じ場所を偶数回押しても意味が無い。(押さなかったと同じ)
２．押す順番は関係ない。(解答は２次元マップのオンオフで表現可)
つまり、ライツアウトの解は、全２５マスについて押すか押さないかの、２の２５乗＝３３,５５４,４３２通りを調べれば解が得られます。
| ■考察２（３２通りの組合せ） |
| ■考察３（８通りの組合せ） |
|
|
|
|
ここで最上段の左側の２マスに着目してみてください。これは２進数の４通りパターンが網羅されています。この事から上段左側の２マスの押下パターンは適当に固定してしまっても解が得られることを意味します。(最適解の保証は無くなるけど)
つまり、上段左側の２マスを００と固定してしまっても解が得られるし、また、解が１つ見つかれば上の４パターンの押下法を重ねることによって４通りの解が得られる。ということです。
結局、最上段の残りの右３マスだけでの組み合せ(８通り)を調べれば、解を見付けることが出来るのです。
| ■考察４（一発で解を求める） |
|
|
| ■考察５（検証） |
あ＝０
い＝０
う＝(Ｂ＋Ｃ＋Ｇ＋Ｈ＋Ｉ＋Ｋ＋Ｌ＋Ｏ＋Ｑ＋Ｔ＋Ｗ＋Ｘ) mod２
え＝(Ａ＋Ｂ＋Ｃ＋Ｋ＋Ｌ＋Ｍ＋Ｑ＋Ｓ＋Ｗ＋Ｘ＋Ｙ) mod２
お＝(Ａ＋Ｃ＋Ｄ＋Ｋ＋Ｍ＋Ｎ＋Ｐ＋Ｔ＋Ｖ＋Ｗ＋Ｘ) mod２
か＝(Ａ) mod ２
き＝・・・・省略・・・・
｜
せ＝(Ｃ＋Ｄ＋Ｅ＋Ｉ) mod２
｜
[あ]と[い]が０と言うのは考察３で書いた通りです。さて、試しに[せ]が短い式なのでそれを検証してみます。
最初に立てられる連立方程式の[Ｃ,Ｄ,Ｅ,Ｉ]の関係式は次のようになります。
Ｃ＝（い＋う＋え＋く）mod２
Ｄ＝（う＋え＋お＋け）mod２
Ｅ＝（え＋お＋こ）mod２
Ｉ＝（え＋く＋け＋こ＋せ）mod２
この４つの式を「mod２」のルールで右辺・左辺をそれぞれ加算します。（排他的論理和）
つまり偶数個あるものは消滅し奇数個あるものは１個だけ残るという計算になります。その結果は、
（Ｃ＋Ｄ＋Ｅ＋Ｉ）mod２ =（い＋せ）mod２
ここで[い]＝０なので、せ＝(Ｃ＋Ｄ＋Ｅ＋Ｉ) mod２ となります。総ての式が同様にして検証できます。
| ■考察６（連立方程式を解く） |
|
|
式1: あい−え−−−−− Ａ−−−−−−−− 式2: あいう−お−−−− −Ｂ−−−−−−− 式3: −いう−−か−−− −−Ｃ−−−−−− 式4: あ−−えお−き−− −−−Ｄ−−−−− 式5: −い−えおか−く− −−−−Ｅ−−−− 式6: −−う−おか−−け −−−−−Ｆ−−− 式7: −−−え−−きく− −−−−−−Ｇ−− 式8: −−−−お−きくけ −−−−−−−Ｈ− 式9: −−−−−か−くけ −−−−−−−−Ｉ この連立式を解いて下の様な形の連立式に変換したいと言う訳です。 式1: あ−−−−−−−− ？？？？？？？？？ 式2: −い−−−−−−− ？？？？？？？？？ 式3: −−う−−−−−− ？？？？？？？？？ 式4: −−−え−−−−− ？？？？？？？？？ 式5: −−−−お−−−− ？？？？？？？？？ 式6: −−−−−か−−− ？？？？？？？？？ 式7: −−−−−−き−− ？？？？？？？？？ 式8: −−−−−−−く− ？？？？？？？？？ 式9: −−−−−−−−け ？？？？？？？？？ さて、[あ]は式１,２,４にあります。式１だけを残して式２,４の[あ]を消すには、 式１ xor 式２ → 式２と 式１ xor 式４ → 式４のmod２による加算を行います。 つまり左辺・右辺それぞれの「排他的論理和」です。 式1: あい−え−−−−− Ａ−−−−−−−− 式2: あいう−お−−−− −Ｂ−−−−−−− ↓ ↓ 式2: −−うえお−−−− ＡＢ−−−−−−− そして、 式1: あい−え−−−−− Ａ−−−−−−−− 式4: あ−−えお−き−− −−−Ｄ−−−−− ↓ ↓ 式4: −い−−お−き−− Ａ−−Ｄ−−−−− その結果、次のようになります。[あ]が式１だけになりました。 式1: あい−え−−−−− Ａ−−−−−−−− 式2: −−うえお−−−− ＡＢ−−−−−−− 式3: −いう−−か−−− −−Ｃ−−−−−− 式4: −い−−お−き−− Ａ−−Ｄ−−−−− 式5: −い−えおか−く− −−−−Ｅ−−−− 式6: −−う−おか−−け −−−−−Ｆ−−− 式7: −−−え−−きく− −−−−−−Ｇ−− 式8: −−−−お−きくけ −−−−−−−Ｈ− 式9: −−−−−か−くけ −−−−−−−−Ｉ 次に[い]ですが、式２には[い]が無いので[い]のある式３と交換します。 式１にも[い]がありますが、式１は[あ]を残す為の式なので式１と交換してはいけません。 式1: あい−え−−−−− Ａ−−−−−−−− 式2: −いう−−か−−− −−Ｃ−−−−−− ←┐ 式3: −−うえお−−−− ＡＢ−−−−−−− ←┘ 式4: −い−−お−き−− Ａ−−Ｄ−−−−− 式5: −い−えおか−く− −−−−Ｅ−−−− 式6: −−う−おか−−け −−−−−Ｆ−−− 式7: −−−え−−きく− −−−−−−Ｇ−− 式8: −−−−お−きくけ −−−−−−−Ｈ− 式9: −−−−−か−くけ −−−−−−−−Ｉ では、式２以外の式から[い]を消すために、式２ xor 式１ → 式１，式２ xor 式４ → 式４、式２ xor 式５ → 式５の 排他的論理和を行います。その結果、[い]があるのは式２だけとなりました。 式1: あ−うえ−か−−− Ａ−Ｃ−−−−−− 式2: −いう−−か−−− −−Ｃ−−−−−− 式3: −−うえお−−−− ＡＢ−−−−−−− 式4: −−う−おかき−− Ａ−ＣＤ−−−−− 式5: −−うえお−−く− −−Ｃ−Ｅ−−−− 式6: −−う−おか−−け −−−−−Ｆ−−− 式7: −−−え−−きく− −−−−−−Ｇ−− 式8: −−−−お−きくけ −−−−−−−Ｈ− 式9: −−−−−か−くけ −−−−−−−−Ｉ 以下同様にして最終的にはこのような結果となります。 式1: あ−−−−−−−− Ａ−Ｃ−−ＦＧＨ− 式2: −い−−−−−−− −−−−Ｅ−ＧＨＩ 式3: −−う−−−−−− Ａ−ＣＤ−−−ＨＩ 式4: −−−え−−−−− −−Ｃ−ＥＦ−−Ｉ 式5: −−−−お−−−− −Ｂ−ＤＥＦ−Ｈ− 式6: −−−−−か−−− Ａ−−ＤＥ−Ｇ−− 式7: −−−−−−き−− ＡＢ−−−ＦＧ−Ｉ 式8: −−−−−−−く− ＡＢＣ−Ｅ−−−− 式9: −−−−−−−−け −ＢＣＤ−−Ｇ−Ｉ
| ■考察７（５×５ライツアウトの結果） |
式 1: 1-----------------------5 -BCD---H-J---NO----T----- 式 2: -2---------------------4- AB-DE-G-----MNO---S------ 式 3: --3--------------------45 A-CDEF-HI---MN-PQRST-V--- 式 4: ---4-------------------4- ABC---G---------Q---UVW-- 式 5: ----5-------------------5 -BC-EF----K-M-O--R-TUV--- 式 6: -----6-----------------45 --C-E-GH-J--M-----ST----- 式 7: ------7------------------ -B-D-FG-IJ---N-PQR---V--- 式 8: -------8---------------45 A-C--F-HI-----OP-R-TU-W-- 式 9: --------9---------------- --C---GHI-K--NOP--S--VW-- 式10: ---------0-------------45 A----FG---K-M-O-QR-T--W-- 式11: ----------1------------4- ----E---IJ--M-OPQRS--V--- 式12: -----------2-----------4- ----------------Q---UVW-- 式13: ------------3------------ -BC-EF---JK-MN---R--UV--- 式14: -------------4---------4- ABC---G-I---MNO---S------ 式15: --------------5--------4- AB--E--HIJK--NOPQ-S-U---- 式16: ---------------6-------45 --C---GHI-K---OP-R-TU-W-- 式17: ----------------7-------- --CD--G--JKL--O-QRS---W-- 式18: -----------------8-----45 --C-E-GH-JK-M--PQ-STU---- 式19: ------------------9------ -BC--F--I-K--NO-QRS---W-- 式20: -------------------0---45 A-C-EF-H-J-----P-R-TU-W-- 式21: --------------------1---5 ---DE--H---LM-OP-R-TUV--- 式22: ---------------------2-4- --CDE-G-I-KLM-------UVW-- 式23: ----------------------345 ---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式24と式25の左辺が消えてしまいました。これでは一意に解を得ることは出来ません。
この２つの式は何を意味しているかと言うと「解の存在条件」を示しています。解が存在する為にはこの２つの式が共に０でなければなりません。
そのどちらかでも計算結果が１なら解は存在しないことになります。
式24: 0 = (B+C+D+F+H+J+K+L+N+O+P+R+T+V+W+X) mod 2 式25: 0 = (A+C+E+F+H+J+P+R+T+U+W+Y) mod 2そしてさらに最後の２マスはオンでもオフでも構わないということも意味します。これは、細江さんの解き方の図を逆さまにしたものと同じですね。
また、この２つの式は計算結果が０になる式であることから、下から３段目以上の計算式に重ねても正しい計算式になります。
つまり、それぞれのマスには４通りの計算式(計算結果は同じ)があることになります。項数が一番少なくなるものをそれぞれ選んでおけばベターですね。
蛇足になるかも知れませんが最後の２マスに０と入れておくよりも、素直に式24と式25を入れておけば、そこを見ただけで解の正誤を知ることが出来ます。
| ■考察８（最適解を求める） |
最後の２マスは４通りの決め方がありますので、その４通りの解の中に必ず最適解が見つかることになります。
尚、一般的には「２の条件式数乗」通りの解があることになります。
式 1: 1---------------------- -5-BCD---H-J---NO----T----- 式 2: -2--------------------- 4-AB-DE-G-----MNO---S------ 式 3: --3-------------------- 45A-CDEF-HI---MN-PQRST-V--- 式 4: ---4------------------- 4-ABC---G---------Q---UVW-- 式 5: ----5------------------ -5-BC-EF----K-M-O--R-TUV--- 式 6: -----6----------------- 45--C-E-GH-J--M-----ST----- 式 7: ------7---------------- ---B-D-FG-IJ---N-PQR---V--- 式 8: -------8--------------- 45A-C--F-HI-----OP-R-TU-W-- 式 9: --------9-------------- ----C---GHI-K--NOP--S--VW-- 式10: ---------0------------- 45A----FG---K-M-O-QR-T--W-- 式11: ----------1------------ 4-----E---IJ--M-OPQRS--V--- 式12: -----------2----------- 4-----------------Q---UVW-- 式13: ------------3---------- ---BC-EF---JK-MN---R--UV--- 式14: -------------4--------- 4-ABC---G-I---MNO---S------ 式15: --------------5-------- 4-AB--E--HIJK--NOPQ-S-U---- 式16: ---------------6------- 45--C---GHI-K---OP-R-TU-W-- 式17: ----------------7------ ----CD--G--JKL--O-QRS---W-- 式18: -----------------8----- 45--C-E-GH-JK-M--PQ-STU---- 式19: ------------------9---- ---BC--F--I-K--NO-QRS---W-- 式20: -------------------0--- 45A-C-EF-H-J-----P-R-TU-W-- 式21: --------------------1-- -5---DE--H---LM-OP-R-TUV--- 式22: ---------------------2- 4---CDE-G-I-KLM-------UVW-- 式23: ----------------------3 45---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
|
|
|
| ■考察９（連立式をプログラムで解く） |
ライツアウトに良く似たパズルに「８めくり」というのがあるそうですが、deepgreenさんは、３２×３２の８めくりを従来方式のプログラムを書いたら７６時間で解を出したそうですが、この連立式を使う方式に変えるとわずか３秒で解いてしまったそうです。(もちろん連立式を解くのに要した時間を含みます)
その詳しい情報はdeepgreenさん本人のホームページで見ることが出来ます。
正に驚異的なアルゴリズムだったと言う訳です。
| ■おわりに |
(*1) 私の書いたプログラム(Ｃ言語)は、ここ (高速ビット処理版)
(*2) deepgreenさんのホームページは、ここ
※ このライツアウトはグラフ理論を使って高速に解くことも出来るようです。ここ (青木史郎さんの卒論)
※ トミーから発売されている３カラー版ライツアウトの計算解法をエクセルで作ってみました。ここ
ホームページへ戻る 開発ノートメニューへ戻る