ホームページへ戻る驚異のライツアウト解法ロジック
ライツアウトを解く為の基本原則はこのようなものです。
１．同じ場所を偶数回押しても意味が無い。(押さなかったと同じ) つまり、ライツアウトの解は、全２５マスについて押すか押さないかの、２の２５乗＝３３,５５４,４３２通りを調べれば解が得られます。
最上段５マスの押下パターンを決めてしまうと２段目以降は選択の余地なく押下パターンが決定されてしまいます。 つまり、実際は２の５乗＝３２通りだけを調べれば良いのです。
「ある複数ボタンを押すと何も押さないのと同じ」という組み合わせがあります。
ここで最上段の左側の２マスに着目してみてください。これは２進数の４通りパターンが網羅されています。この事から上段左側の２マスの押下パターンは適当に固定してしまっても解が得られることを意味します。(最適解の保証は無くなるけど)
下図の問題面[Ａ]のライトをオンオフできるのは押下法の[あ,い,か]です。この関係を下の計算式に表現する事が出来ます。 ここで、問題面の[Ａ]から[Ｙ]の値は、０＝消灯,１＝点灯、押下法の[あ]から[の]の値は０＝押さない,１＝押す とします。 尚、最後に得られる計算式に一般性を持たせる為この関係式は問題面が総て消灯した状態で作ります。
Ａ＝（あ＋い＋か）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さん(*2)のＨＰで解き明かされています。
連立式をいちいち手で解くのは面倒なので、考察６に書いた通りの手順で解くプログラム(掃き出し法)を作っておけば楽です。(*1) では、そのプログラムの仕事量はどの程度のものでしょう。Ｎ×Ｎのライツアウトを従来の方法で解くなら、２のＮ乗通りのパターンを生成しますが、 この方法なら二重のＮ×Ｎ回ループの中で簡単な計算をするだけです。Ｎの値に従ってＮ乗レベルの増加量が２乗レベルの増加量で済みます。 Ｎが大きくなればなるほど驚異的な高速化が実現されることになります。プログラムをビット演算処理で書けばもっと高速になるでしょう。
ライツアウトに良く似たパズルに「８めくり」というのがあるそうですが、deepgreenさんは、３２×３２の８めくりを従来方式のプログラムを書いたら７６時間で解を出したそうですが、この連立式を使う方式に変えるとわずか３秒で解いてしまったそうです。(もちろん連立式を解くのに要した時間を含みます) 正に驚異的なアルゴリズムだったと言う訳です。
細江さんはプログラムを書けないそうです。プログラムを書ける人なら３２通りを調べるだけで良いと判った段階でサラッとプログラムを書いておしまいです。 さらに突っ込んだ解析をすれば、こんな素晴らしいロジックに出会えたなんて反省ものです。細江さんどうも有難うございました。 そして、この考え方をプログラムを使ってさらに明確に解析し、また、連立方程式の解き方までも教えて頂きましたdeepgreenさんにも心から深く感謝いたします。
(*1) 私の書いたプログラム(Ｃ言語)は、ここ (高速ビット処理版)
ホームページへ戻る |