ホームページへ戻る　驚異のライツアウト解法ロジックへ戻る

ライツアウト(３カラーパズル)の計算解法


　2000年に新しいライツアウトが発売されました。今度のは３カラー版で、■→■→■→■の順に色がローテーションします。従来のライツアウトの解を計算式を使って一発で求められることが判った以上、この新型の３カラー版も計算式を使って解いてみたいものです。パックトラッキングなら３の５乗＝２４３通りの探索で求められる訳ですが、それではもはや面白味がありません。

さっそく作ってみたのが、このエクセル版の自動解答計算です。(当然ですが計算式が書き込んであるだけです)

　ライツアウト(３カラーパズル)のエクセル版ソルバー　


■連立方程式を立てる

最初に立てる連立式はどのようにすれば良いのか。２カラー版と全く同じで良いのか？
下図の結果面[イ]は、問題面[あ]と押下法[Ａ,Ｂ,Ｃ]を使って

　　イ＝（あ＋Ａ＋Ｂ＋Ｃ）ｍｏｄ３　と表すのが正しい表し方になります。

ただし、問題面と結果面は、■＝０，■＝１，■＝２、押下法は押す回数とする。

問題面押下法結果面
あ




















ＡＢ
Ｃ















イ




















イは０にするのだから、つまりは、

　　（あ＋Ａ＋Ｂ＋Ｃ）ｍｏｄ３＝０　　となって、
　　（Ａ＋Ｂ＋Ｃ）ｍｏｄ３＝（−あ）ｍｏｄ３　　となる。

右辺はマイナスとなります。そこで３の倍数なら幾ら加算しても良いから、

　　（Ａ＋Ｂ＋Ｃ）ｍｏｄ３＝（３−あ）ｍｏｄ３

つまり、最初に立てる連立方程式はこのようになります。

   1: 11---1-------------------  2------------------------
   2: 111---1------------------  -2-----------------------
   3: -111---1-----------------  --2----------------------
   4: --111---1----------------  ---2---------------------
   5: ---11----1---------------  ----2--------------------
   6: 1----11---1--------------  -----2-------------------
   7: -1---111---1-------------  ------2------------------
   8: --1---111---1------------  -------2-----------------
   9: ---1---111---1-----------  --------2----------------
  10: ----1---11----1----------  ---------2---------------
  11: -----1----11---1---------  ----------2--------------
  12: ------1---111---1--------  -----------2-------------
  13: -------1---111---1-------  ------------2------------
  14: --------1---111---1------  -------------2-----------
  15: ---------1---11----1-----  --------------2----------
  16: ----------1----11---1----  ---------------2---------
  17: -----------1---111---1---  ----------------2--------
  18: ------------1---111---1--  -----------------2-------
  19: -------------1---111---1-  ------------------2------
  20: --------------1---11----1  -------------------2-----
  21: ---------------1----11---  --------------------2----
  22: ----------------1---111--  ---------------------2---
  23: -----------------1---111-  ----------------------2--
  24: ------------------1---111  -----------------------2-
  25: -------------------1---11  ------------------------2
■連立方程式を解く

この連立式をｍｏｄ３で解いていく訳ですが、今回は左辺に係数として２がつく場合があります。
その時は両辺を２倍してｍｏｄ３の計算をすると１にすることが出来ます。

　　5: ----2-----------------12- 222-12-2--2-2122211--1---
　　　　　　　　　　　↓
　　5: ----1-----------------21- 111-21-1--1-1211122--2---


これが連立方程式を解いた結果です。 

   1: 1---------------------22-  11211-2221-11-22221-22---
   2: -1--------------------2-2  1--21211--221-2--2-112---
   3: --1-------------------1--  2-1211-22---1--22---22---
   4: ---1------------------1-1  1222--1-111-221222-21----
   5: ----1-----------------21-  111-21-1--1-1211122--2---
   6: -----1----------------211  -21-11--121-1-211222-2---
   7: ------1---------------111  21-1---1221---2222221----
   8: -------1--------------2--  212-1-1--2-121-222--22---
   9: --------1-------------222  2-21-12--21-22111211-2---
  10: ---------1-------------22  1--1-222221--21--21121---
  11: ----------1-----------121  -2-1111-11121--11-12-2---
  12: -----------1----------212  12-----1--2-22-111212----
  13: ------------1------------  111211-22-121--22---1----
  14: -------------1--------121  ---22--122-2-2-1111211---
  15: --------------1-------212  22-1122-11-----11-2111---
  16: ---------------1------122  2-2211221-11211---1112---
  17: ----------------1-----222  2-2211221-11211---1121---
  18: -----------------1----1--  22-2222222-1-1---2-------
  19: ------------------1---111  1---222-1112-1211-22-2---
  20: -------------------1---11  -1-2-22-1121-2111-222----
  21: --------------------1-2-1  2121--12-2-211112--2-1---
  22: ---------------------1-1-  222-22-2212--1121-2-1----
  23: -------------------------  112211211-21-212122-1-1--
  24: -------------------------  2---111-2221-2122-11-1-2-
  25: -------------------------  -1-2-22-1121-2111-222---1

解の存在条件式が３つあります。つまり、解が存在するとき３の３乗＝２７通りの解があることになります。

なお、実際に３色ライツアウトを解くときは右辺の数字を係数にして計算させることになります。


■４色ライツアウトについて

最初に立てる連立式は先ほどと同様の理由によりこの様になります。 

   1: 11---1-------------------  3------------------------
   3: 111---1------------------  -3-----------------------
   3: -111---1-----------------  --3----------------------
   4: --111---1----------------  ---3---------------------
   5: ---11----1---------------  ----3--------------------
   6: 1----11---1--------------  -----3-------------------
   7: -1---111---1-------------  ------3------------------
   8: --1---111---1------------  -------3-----------------
   9: ---1---111---1-----------  --------3----------------
  10: ----1---11----1----------  ---------3---------------
  11: -----1----11---1---------  ----------3--------------
  13: ------1---111---1--------  -----------3-------------
  13: -------1---111---1-------  ------------3------------
  14: --------1---111---1------  -------------3-----------
  15: ---------1---11----1-----  --------------3----------
  16: ----------1----11---1----  ---------------3---------
  17: -----------1---111---1---  ----------------3--------
  18: ------------1---111---1--  -----------------3-------
  19: -------------1---111---1-  ------------------3------
  30: --------------1---11----1  -------------------3-----
  31: ---------------1----11---  --------------------3----
  33: ----------------1---111--  ---------------------3---
  33: -----------------1---111-  ----------------------3--
  34: ------------------1---111  -----------------------3-
  35: -------------------1---11  ------------------------3
４色の場合も同様にしてこの連立方程式を解けそうですが、ひとつ問題があります。
左辺に係数として２がついたときｍｏｄ４では１に出来ないのです。

４色の場合の連立方程式を単純に解いた結果はこのようになります。 

   1: 2-----------------------2  -222---2-2---22----2-----
   2: -2---------------------2-  22-22-2-----222---2------
   3: --2--------------------22  2-2222-22---22-22222-2---
   4: ---2-------------------2-  222---2---------2---222--
   5: ----2-------------------2  -22-22----2-2-2--2-222---
   6: -----2-----------------22  --2-2-22-2--2-----22-----
   7: ------2------------------  -2-2-22-22---2-222---2---
   8: -------2---------------22  2-2--2-22-----22-2-22-2--
   9: --------2----------------  --2---222-2--222--2--22--
  10: ---------2-------------22  2----22---2-2-2-22-2--2--
  11: ----------2------------2-  ----2---22--2-22222--2---
  12: -----------2-----------2-  ----------------2---222--
  13: ------------2------------  -22-22---22-22---2--22---
  14: -------------2---------2-  222---2-2---222---2------
  15: --------------2--------2-  22--2--2222--2222-2-2----
  16: ---------------2-------22  --2---222-2---22-2-22-2--
  17: ----------------2--------  --22--2--222--2-222---2--
  18: -----------------2-----22  --2-2-22-22-2--22-222----
  19: ------------------2------  -22--2--2-2--22-222---2--
  20: -------------------2---22  2-2-22-2-2-----2-2-22-2--
  21: --------------------2---2  ---22--2---22-22-2-222---
  22: ---------------------2-2-  --222-2-2-222-------222--
  23: ----------------------222  ---2---222-2---22-22-2---
  24: -------------------------  -222-2-2-222-222-2-2-222-
  25: -------------------------  2-2-22-2-2-----2-2-22-2-2
運良く(？)総ての係数が２になっているので両辺を２で割り算すれば良さそうですが、それは間違いです。
例えば、
　　（２）ｍｏｄ４＝（２＋２＋２）ｍｏｄ４　　←これは正しい式です。
　　（１）ｍｏｄ４＝（１＋１＋１）ｍｏｄ４　　←これは正しくありません。

割り算を使ってはいけないのです。ではどうすれば良いのか？

■Ｎ色ライツアウトについて

左辺の係数を１に出来なければ方程式が解けたことにはなりません。
一般にＮ色ライツアウトを連立方程式で解く場合その方程式が単純に解けるのはＮが素数の場合に限られます。

フェルマの定理　　A^(p-1) = 1 (mod　p)　(ｐは素数,Aはｐと互いに素)

これはどういう意味かと言うと、pが素数でAの素因数にpが無ければAの(p-1)乗のmod pは1である。
ということです。つまり、pが素数であればAが0＜A＜pの範囲にあれば成り立つことになります。
(例:A=4,p=5)　4*4*4*4 mod 5 = 1

フェルマの式を変形　　A * A^(p-2) = 1 (mod　p)

色数(p)が素数のライツアウトなら左辺に生じた係数(A)に　A^(p-2)　をかければ
必ず１に出来ます。つまり、色数が素数なら連立方程式は解けると言うことです。

　　(注)この証明(発見?)はdeepgreenさんによるものです。


では、色数が素数で無い場合は連立方程式を使った解き方が出来ないのかと言うとそうではありません。
２通りの方法が考案されています。第１の方法は私の考察による「素因数分解法」です。

色数(Ｎ)が素数でないライツアウトを連立方程式を使って解くとき、Ｎを素因数分解し分解された
それぞれの素数での計算式を適用することで解くことが出来ます。
例えばＮ＝４の場合なら素因数分解すると２×２となるので「２色ライツアウト」の計算式を２段階で
使用します。例えば、答えが見え見えの簡単な例で示すと、

      　　　問題面　　 押下法1　　 結果面1　　 押下法2　　 結果面2 　　　押下法(1,2を合成)
      　　１１０２２　１００００　２２０２２　２０００２　０００００　　　３０００２
      　　１０００２　０００００　２０００２　０００００　０００００　　　０００００
      　　０００００　０００００　０００００　０００００　０００００　→　０００００
      　　３００００　０００００　０００００　０００００　０００００　　　０００００
      　　３３０００　１００００　０００００　０００００　０００００　　　１００００
最初の２色ライツアウト計算式適用では、問題面の数字が２で割り切れるものは０と見なされます。
従って、結果面1は［０,２］だけの集合になります。何故ならｍｏｄ２の世界では解けたと見なされ
ている状態だからです。２回目の計算式の適用は結果面1で ０→０,２→１ と見なして式を適用し、
得られた結果を今度は２倍します(２回押す)。そして、押下法1と押下法2を合成すると最終的な押下
法が得られることになります。

第２の方法は「１に出来ない係数を作らないように方程式を解く」という方法です。
この方法はdeepgreenさんの考案によるもので、これなら素因数分解法と違って一発で解を得ることが出来ます。

例えば４色ライツアウトの連立方程式を解いている途中の下の式で、 

   1: 3------23112-------------  33-1332------------------
   2: -1-----31323-------------  11-3121------------------
   3: --1-----13---------------  ---31--------------------
   4: ---3---22223-------------  1112221------------------
   5: ----3--22121-------------  3332323------------------
   6: -----3-12211-------------  32-2233------------------
   7: ------131333-------------  21-3111------------------
   8: -------212333------------  21-22111-----------------
   9: -------33323-1-----------  1112221-3----------------
  10: -------21223--3----------  1112121--1---------------
  11: -------32222---3---------  12-2211---1--------------
  12: -------131221---1--------  23-1333----3-------------
  13: -------1---111---1-------  ------------3------------
  14: --------1---111---1------  -------------3-----------
式8の2を掃出しの基点にしてはいけないということです。こういうときは、式8と式9を交換することになります。
尚、係数が３なら３倍すれば１に出来ます。（３×３）ｍｏｄ４＝１

このようにして４色ライツアウトの連立方程式は見事に解くことが出来ます。 

   1: 1-----------------------1  -113-223-1--2132-2232-2--
   2: -1---------------------1-  13233-1--22-1332--1--22--
   3: --1--------------------33  121111-3122231-31331232--
   4: ---1-------------------3-  331--21-2-22-2223-2-113--
   5: ----1------------------21  -31-31----3-3-1-21-3312--
   6: -----1-----------------33  2-121211-12-1-2--21122---
   7: ------1------------------  21-1-11233-22321332--32--
   8: -------1---------------11  3-3--1211-2--231-123121--
   9: --------1----------------  --12--31121-21132-3-231--
  10: ---------1-------------33  122--13-2-3212123321-23--
  11: ----------1------------1-  -22232-213223-11113--3---
  12: -----------1-----------3-  --22--2--222--2-122-133--
  13: ------------1------------  213-312-213-112-212-312--
  14: -------------1---------1-  1312--3212--111---3------
  15: --------------1--------3-  33-21223111221131-3-322--
  16: ---------------1-------11  2232--11321---3323231-1--
  17: ----------------1--------  --132-3-23112-12113--21--
  18: -----------------1-----33  2-3-1231-3121--31-31322--
  19: ------------------1------  2132-12232322332331--23--
  20: -------------------1---11  3-1-31-3-1-----3-1-31-3--
  21: --------------------1--23  2-2132-12--13-31-3-1332--
  22: ---------------------1-1-  -231123232331-2-222-311--
  23: ----------------------111  22232-2113-32-21123321---
  24: -------------------------  -13323-1-313-131-3-12113-
  25: -------------------------  1-3-13-1-3-----1-3-13-1-3
解の存在条件式が２つあります。つまり、解が存在するとき４の２乗＝１６通りの解があることになります。


■特殊な解の存在条件式について

５色は素数なので単純に解けます。６色ライツアウトを解くとこのようになります。 

   1: 1---------------------223  23354-41-3-44352---14-22-
   2: -1--------------------232  5543123-4222135-4-52--22-
   3: --1-------------------433  13425242155112141-142-35-
   4: ---1------------------1-1  3133225531252--34-153-5--
   5: ----1-----------------243  2-215423454315412-445-55-
   6: -----1----------------211  44541455214-1-242-132-22-
   7: ------1---------------444  4-1222131255-41-1--5--53-
   8: -------1--------------5--  33-44--5443421-53-511-25-
   9: --------1-------------555  -235-412411325145--52-52-
  10: ---------1------------322  15124-545--43122--134-21-
  11: ----------1-----------454  253155233-33154-3-53--35-
  12: -----------1----------545  2-254425134124432-113-1--
  13: ------------1------------  444514-52-451-352--31-33-
  14: -------------1--------454  51542-121--23534--542-44-
  15: --------------1-------212  35-434435512-1555-1-1--4-
  16: ---------------1------122  43222535-2-223255-551--5-
  17: ----------------1-----555  -325-312512325-44---2--1-
  18: -----------------1----433  441-1431451-32215-135-2--
  19: ------------------1---111  -----------------------5-
  20: -------------------1--344  31-232231154-5111-555--3-
  21: --------------------1-2-1  -15455-2431415-2--243-31-
  22: ---------------------1343  225-5235215-34451-531-3--
  23: ----------------------333  251425425-12-154511-2-53-
  24: ----------------------333  4--322231145-4211-55-5-4-
  25: ----------------------333  35-434435512-1555-111--35
ここで、最後の３つの式(23)〜(25)の左辺は全く同じなので、

（２４）−（２３）−＞ 新（２４）
（２５）−（２３）−＞ 新（２５）
とすると、新（２４），新（２５）の左辺はゼロになります。

  23: ----------------------333  251425425-12-154511-2-53-
  24: -------------------------  2155-3412133-33325454511-
  25: -------------------------  1-5-15-1-5-----1-5-15-1-5
式(24)と式(25)は通常の「解の存在条件式」ですが、では式(23)は何を意味しているのか？

これもやはりdeepgreenさんが解明しています。私が調べた結果ではdeepgreenさんの分析に間違いは無いと思います。
是非、deepgreenさん本人のＨＰをご覧下さい。それにしても、deepgreenさんて凄い人です。

ホームページへ戻る　驚異のライツアウト解法ロジックへ戻る