カラー版ライツアウトの解法(補足)                          2000.09.18 deepgreen カラー版ライツアウトの解法そのものについては、高橋謙一郎さんのHPに 詳細な解説があるので、ここでは、落穂拾い的な話題を扱うことにする。 □解法のポイント(おさらい)   問題面      pushパターン  ABCDE     x01x02x03x04x05  FGHIJ     x06x07x08x09x10  KLMNO  x11x12x13x14x15  PQRST  x16x17x18x19x20  UVWXY     x21x22x23x24x25  カラー版(C色)になって変わったのは、同じ箇所をC回押さないともどら  ない点である。A〜Y,x01〜x25は、0〜(C−1)の値域となる。  2色の場合と同様に連立式をたてることができる。   式01  x01+x02+x06   +A = 0 mod C   式02  x01+x02+x03+x07 +B = 0 mod C          ...   式25  x20+x24+x25   +Y = 0 mod C  定数を右辺に移項した形にして、以下のように略記する。(移項によって係数はC−1となる) [5x5、Color=3] 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - - - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - - - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - - - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - - - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - - 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - - 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - - 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - - 1 1 - - - - - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - - - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - - - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - - - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 - - - - - - - - - - - - - - - - - - - - - - - - 2 【Cが素数の場合】  フェルマの定理によって、ある数m(≠0)の逆数r(m*r=1 modC)が保証  されているので、上記の連立式は掃出し法で簡単に解くことができる。 【Cが素数でない場合】  ある数mの逆数r(m*r=1 modC)が保証されない場合がある。  (例えば、mod4の場合、2の逆数は存在しない。)  この場合、連立式を掃出し法で解くための基点にすることはできないので、他  の行と入れ換える操作が必要になる。  逆数の存在しない数をmとするとき、ある行をm倍する操作はしてはいけない。  (元にもどれないから) [結果の解析] (1) Color=3,Raw=5,Col=5    1 - - - - - - - - - - - - - - - - - - - - - 2 2 - 1 1 2 1 1 - 2 2 2 1 - 1 1 - 2 2 2 2 1 - 2 2 - - -   - 1 - - - - - - - - - - - - - - - - - - - - 2 - 2 1 - - 2 1 2 1 1 - - 2 2 1 - 2 - - 2 - 1 1 2 - - -   - - 1 - - - - - - - - - - - - - - - - - - - 1 - - 2 - 1 2 1 1 - 2 2 - - - 1 - - 2 2 - - - 2 2 - - -   - - - 1 - - - - - - - - - - - - - - - - - - 1 - 1 1 2 2 2 - - 1 - 1 1 1 - 2 2 1 2 2 2 - 2 1 - - - -   - - - - 1 - - - - - - - - - - - - - - - - - 2 1 - 1 1 1 - 2 1 - 1 - - 1 - 1 2 1 1 1 2 2 - - 2 - - -   - - - - - 1 - - - - - - - - - - - - - - - - 2 1 1 - 2 1 - 1 1 - - 1 2 1 - 1 - 2 1 1 2 2 2 - 2 - - -   - - - - - - 1 - - - - - - - - - - - - - - - 1 1 1 2 1 - 1 - - - 1 2 2 1 - - - 2 2 2 2 2 2 1 - - - -   - - - - - - - 1 - - - - - - - - - - - - - - 2 - - 2 1 2 - 1 - 1 - - 2 - 1 2 1 - 2 2 2 - - 2 2 - - -   - - - - - - - - 1 - - - - - - - - - - - - - 2 2 2 2 - 2 1 - 1 2 - - 2 1 - 2 2 1 1 1 2 1 1 - 2 - - -   - - - - - - - - - 1 - - - - - - - - - - - - - 2 2 1 - - 1 - 2 2 2 2 2 1 - - 2 1 - - 2 1 1 2 1 - - -   - - - - - - - - - - 1 - - - - - - - - - - - 1 2 1 - 2 - 1 1 1 1 - 1 1 1 2 1 - - 1 1 - 1 2 - 2 - - -    - - - - - - - - - - - 1 - - - - - - - - - - 2 1 2 1 2 - - - - - 1 - - 2 - 2 2 - 1 1 1 2 1 2 - - - -   - - - - - - - - - - - - 1 - - - - - - - - - - - - 1 1 1 2 1 1 - 2 2 - 1 2 1 - - 2 2 - - - 1 - - - -    - - - - - - - - - - - - - 1 - - - - - - - - 1 2 1 - - - 2 2 - - 1 2 2 - 2 - 2 - 1 1 1 1 2 1 1 - - -    - - - - - - - - - - - - - - 1 - - - - - - - 2 1 2 2 2 - 1 1 2 2 - 1 1 - - - - - 1 1 - 2 1 1 1 - - -    - - - - - - - - - - - - - - - 1 - - - - - - 1 2 2 2 - 2 2 1 1 2 2 1 - 1 1 2 1 1 - - - 1 1 1 2 - - -    - - - - - - - - - - - - - - - - 1 - - - - - 2 2 2 2 - 2 2 1 1 2 2 1 - 1 1 2 1 1 - - - 1 1 2 1 - - -    - - - - - - - - - - - - - - - - - 1 - - - - 1 - - 2 2 - 2 2 2 2 2 2 2 - 1 - 1 - - - 2 - - - - - - -     - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 1 - - - 2 2 2 - 1 1 1 2 - 1 2 1 1 - 2 2 - 2 - - -    - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 - 1 - 2 - 2 2 - 1 1 2 1 - 2 1 1 1 - 2 2 2 - - - -    - - - - - - - - - - - - - - - - - - - - 1 - 2 - 1 2 1 2 1 - - 1 2 - 2 - 2 1 1 1 1 2 - - 2 - 1 - - -     - - - - - - - - - - - - - - - - - - - - - 1 - 1 - 2 2 2 - 2 2 - 2 2 1 2 - - 1 1 2 1 - 2 - 1 - - - -  式23 - - - - - - - - - - - - - - - - - - - - - - - - - 2 2 1 1 2 2 1 2 2 - 1 2 - 1 2 1 2 1 1 - 2 - 2 - - 式24 - - - - - - - - - - - - - - - - - - - - - - - - - 2 - - - 1 1 1 - 2 2 2 1 - 2 1 2 2 - 1 1 - 1 - 2 - 式25 - - - - - - - - - - - - - - - - - - - - - - - - - - 2 - 1 - 1 1 - 2 2 1 2 - 1 2 2 2 - 1 1 1 - - - 2  式23、式24、式25は、2色の場合と同様に「解の存在条件式」となっている。  例えば、A=1,B=1,C=2 他は0という問題は、以下の計算により解が存在しない。    式23 2*1+2*1+1*2=6=0mod3 :OK    式24 2*1        =2       :NG □新しい「解の存在条件式」  5x5,Color=6の解には、今までと異なるパターンがでてきます。 [5x5,Color=6の最後の部分]   - - - - - - - - - - - - - - - - - - - - - 1 - 1 - 4 1 - 4 1 1 1 1 1 1 - 2 3 5 3 3 - 1 - 3 3 - 2 3 - 式23 - - - - - - - - - - - - - - - - - - - - - - 3 3 3 4 1 5 2 4 1 2 4 1 - 5 4 - 5 1 2 1 5 5 - 4 - 1 3 - 式24 - - - - - - - - - - - - - - - - - - - - - - - - - - 5 1 1 4 1 - 5 - 1 5 1 - 5 1 5 - 1 - 5 2 5 5 1 - 式25 - - - - - - - - - - - - - - - - - - - - - - - - - 5 4 1 2 5 3 2 5 4 5 2 4 - 2 4 3 4 1 2 1 3 - 5 - 5  式24、式25は、従来と同じものです。式23を、明に書くと    3*(x23+x24+x25) = 4*A+1*B+5*c... mod6  となります。もし、右辺が3の倍数でない場合、この等式はなりたちません。  つまり、解が存在するためには、3の倍数になることが必要となります。  右辺が3の倍数の場合、それを3mとすると       x23+x24+x25 = m   mod6 又は     x23+x24+x25 = m+2 mod6    をみたす、x23,x24,x25の組み合わせのみが解となり得る。  以上より、式23は、「右辺が3の倍数であること」という解の存在条件を  要請していると同時に、X23,x24,x25に対しても制約を課している新しい形  の「解の存在条件式」となっている。  ここまでが、高橋謙一郎さんのHPで議論した話です。  その後、Color=30,60,66,90にも新しいパターンがあるこ  とを高橋謙一郎さんから教えていただきました。  [5x5,Color=30の場合]   - - - - - - - - - - - - - - - - - - - - 1 - 2 - 1 222016271518 227 2181823131625 1 411 4 1 7212828 - 式22 - - - - - - - - - - - - - - - - - - - - - 427 127 1822 -2526202013 9 9 21518 41623 51013 1 - 714 2 - 式23 - - - - - - - - - - - - - - - - - - - - - - - - - -29 1 128 1 -29 - 129 1 -29 129 - 1 -29 22929 1 - 式24 - - - - - - - - - - - - - - - - - - - - - 921 -21 2617222511172526 22422 51513231623 1 7 -291514 9 - 式25 - - - - - - - - - - - - - - - - - - - - - - - - - 129 - 129 - - - - -29 1 -29 1 - - - - - 129 - 129     式22は、ちょっと見ずらいですが、x24の係数が1になっています。式23、式25  は従来のパターンです。式24は、ちょっと変わっています。この式は    3*(3*x22+7*x23+7*x25) = 26*A+17*B+... mod30  となりますので、右辺はやはり3の倍数が要請されます。この値を3mとすると    3*x22+7*x23+7*x25 = m,m+10,m+20 mod30  をみたす、x22,x23,x25の組み合わせが解となります。  (これから先は探索になります) □ちょっと補足  結局、連立式を解くためには、掃出しの基点となる位置の係数を1にする事が  本質です。逆数の存在は、その第1の手段ですが、他の方法もありますので、  簡単に触れておきます。(実際は必要ないでしょうが、...)    「a,bが互いに素な整数のとき、     a*m+b*n=1となる整数m、nが存在する」  という定理を利用します。    解法の過程で、a、bは互いに素 かつ a、bがC(カラー数)の約数で   (1)  a*X+...   modC   (2)  b*X+...   modC  という形の時、これをa*m+b*n=1となるm、nを求めて   mとCが互いに素の場合      (1)’ 1*X+...   modC    (2)  b*X+...   modC   nとCが互いに素の場合、    (1)  a*X+...   modC    (2)’ 1*X+...   modC  に変形することができます。 □「0解」  「0解」の定義は、2色のときと同様とします。すなわち、pushしても何ら  問題面の変化を生じないようなパターンです。  2色の場合は、「解の存在条件式」と「0解」は密接な関係がありましたが、  カラーになるとどうなるのでしょうか?  問題面の位置、解のパターンを以下のように表現する。   [問題面]     [解]   abcde     ABCDE   fghij     FGHIJ   klmno     KLMNO   pqrst     PQRST   uvwxy     UVWXY  Aの位置をpushすると、a、b、fの位置の色が1つすすむ。これを  以下のように記述する。  abcdefghijklmnopqrstuvwxy ABCDEFGHIJKLMNOPQRSTUVWXY 11---1------------------- 1------------------------ 他の位置も同様に記述できるので、全体は以下のようになる。   [5x5,Clor=3の場合]    1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - - - - - - - -    1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - - - - - - -    - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - - - - - -   - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - - - - -    - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - - - -    1 - - - - 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - - -    - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - - -    - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - - -    - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - - -    - - - - 1 - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - -    - - - - - 1 - - - - 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - -    - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - -    - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - - -    - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - - -    - - - - - - - - - 1 - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - - -    - - - - - - - - - - 1 - - - - 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - - -    - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - - -    - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - - -    - - - - - - - - - - - - - 1 - - - 1 1 1 - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - - -    - - - - - - - - - - - - - - 1 - - - 1 1 - - - - 1 - - - - - - - - - - - - - - - - - - - 1 - - - - -    - - - - - - - - - - - - - - - 1 - - - - 1 1 - - - - - - - - - - - - - - - - - - - - - - - 1 - - - -    - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - - - - - - - - - - - - - - - - - - - - - 1 - - -    - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - - - - - - - - - - - - - - - - - - - - - 1 - -   - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 - - - - - - - - - - - - - - - - - - - - - - - 1 -    - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 - - - - - - - - - - - - - - - - - - - - - - - - 1  この連立式には、modC演算(C:カラー数)が適用できます。  また、この連立式の左辺は、カラー版ライツアウトの解法と全く同じで右辺  のみが違います。(両者が補数の関係にあるのは注目すべき)  この連立式を解くと、(解き方は同じです) [Color=3,Raw=5,Col=5の構成要素]   1 - - - - - - - - - - - - - - - - - - - - - 2 2 - 2 2 1 2 2 - 1 1 1 2 - 2 2 - 1 1 1 1 2 - 1 1 - - -   - 1 - - - - - - - - - - - - - - - - - - - - 2 - 2 2 - - 1 2 1 2 2 - - 1 1 2 - 1 - - 1 - 2 2 1 - - -   - - 1 - - - - - - - - - - - - - - - - - - - 1 - - 1 - 2 1 2 2 - 1 1 - - - 2 - - 1 1 - - - 1 1 - - -   - - - 1 - - - - - - - - - - - - - - - - - - 1 - 1 2 1 1 1 - - 2 - 2 2 2 - 1 1 2 1 1 1 - 1 2 - - - -   - - - - 1 - - - - - - - - - - - - - - - - - 2 1 - 2 2 2 - 1 2 - 2 - - 2 - 2 1 2 2 2 1 1 - - 1 - - -   - - - - - 1 - - - - - - - - - - - - - - - - 2 1 1 - 1 2 - 2 2 - - 2 1 2 - 2 - 1 2 2 1 1 1 - 1 - - -    - - - - - - 1 - - - - - - - - - - - - - - - 1 1 1 1 2 - 2 - - - 2 1 1 2 - - - 1 1 1 1 1 1 2 - - - -   - - - - - - - 1 - - - - - - - - - - - - - - 2 - - 1 2 1 - 2 - 2 - - 1 - 2 1 2 - 1 1 1 - - 1 1 - - -   - - - - - - - - 1 - - - - - - - - - - - - - 2 2 2 1 - 1 2 - 2 1 - - 1 2 - 1 1 2 2 2 1 2 2 - 1 - - -    - - - - - - - - - 1 - - - - - - - - - - - - - 2 2 2 - - 2 - 1 1 1 1 1 2 - - 1 2 - - 1 2 2 1 2 - - -    - - - - - - - - - - 1 - - - - - - - - - - - 1 2 1 - 1 - 2 2 2 2 - 2 2 2 1 2 - - 2 2 - 2 1 - 1 - - -    - - - - - - - - - - - 1 - - - - - - - - - - 2 1 2 2 1 - - - - - 2 - - 1 - 1 1 - 2 2 2 1 2 1 - - - -   - - - - - - - - - - - - 1 - - - - - - - - - - - - 2 2 2 1 2 2 - 1 1 - 2 1 2 - - 1 1 - - - 2 - - - -   - - - - - - - - - - - - - 1 - - - - - - - - 1 2 1 - - - 1 1 - - 2 1 1 - 1 - 1 - 2 2 2 2 1 2 2 - - -    - - - - - - - - - - - - - - 1 - - - - - - - 2 1 2 1 1 - 2 2 1 1 - 2 2 - - - - - 2 2 - 1 2 2 2 - - -    - - - - - - - - - - - - - - - 1 - - - - - - 1 2 2 1 - 1 1 2 2 1 1 2 - 2 2 1 2 2 - - - 2 2 2 1 - - -    - - - - - - - - - - - - - - - - 1 - - - - - 2 2 2 1 - 1 1 2 2 1 1 2 - 2 2 1 2 2 - - - 2 2 1 2 - - -    - - - - - - - - - - - - - - - - - 1 - - - - 1 - - 1 1 - 1 1 1 1 1 1 1 - 2 - 2 - - - 1 - - - - - - -    - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1 2 - - - 1 1 1 - 2 2 2 1 - 2 1 2 2 - 1 1 - 1 - - -    - - - - - - - - - - - - - - - - - - - 1 - - - 1 1 - 2 - 1 - 1 1 - 2 2 1 2 - 1 2 2 2 - 1 1 1 - - - -    - - - - - - - - - - - - - - - - - - - - 1 - 2 - 1 1 2 1 2 - - 2 1 - 1 - 1 2 2 2 2 1 - - 1 - 2 - - -    - - - - - - - - - - - - - - - - - - - - - 1 - 1 - 1 1 1 - 1 1 - 1 1 2 1 - - 2 2 1 2 - 1 - 2 - - - -  q23 - - - - - - - - - - - - - - - - - - - - - - - - - 1 1 2 2 1 1 2 1 1 - 2 1 - 2 1 2 1 2 2 - 1 - 1 - - q24 - - - - - - - - - - - - - - - - - - - - - - - - - 1 - - - 2 2 2 - 1 1 1 2 - 1 2 1 1 - 2 2 - 2 - 1 - q25 - - - - - - - - - - - - - - - - - - - - - - - - - - 1 - 2 - 2 2 - 1 1 2 1 - 2 1 1 1 - 2 2 2 - - - 1  q23、q24、q25が「0解」である。  「解の存在条件式」の3個に対応して「0解」も3個となっている。  しかし、両者は別物か? [再掲:5x5、Color=5の解の存在条件式]  式23 - - - - - - - - - - - - - - - - - - - - - - - - - 2 2 1 1 2 2 1 2 2 - 1 2 - 1 2 1 2 1 1 - 2 - 2 - - 式24 - - - - - - - - - - - - - - - - - - - - - - - - - 2 - - - 1 1 1 - 2 2 2 1 - 2 1 2 2 - 1 1 - 1 - 2 - 式25 - - - - - - - - - - - - - - - - - - - - - - - - - - 2 - 1 - 1 1 - 2 2 1 2 - 1 2 2 2 - 1 1 1 - - - 2  q23+q23=式23となっている点に注目されたい。r23=q23+q23とすると、  q23=r23+r23となるので、q23とr23は等価(表と裏の関係)である。  従って、q23と式23は等価である。他も同様である。  結局、”カラーの場合も「解の存在条件式」と「0解」は一致する” 蛇足:新しい「解の存在条件式」がある場合は、別途検討が必要です。     (多分、補数関係にあるところまでしか言えないと思います)