点灯游戏的解法讨论

ggglgq

　　
　　
  
    为什么要提及“ N 陪集魔方”呢？ 因我们可以利用类似本主题的“交换群”
  
很容易地构造“N 陪集魔方”，比如 灯 的色彩可自定义为
  
    灭、亮、色2、 ...  、色N-1  （ 0 、 1 、 2 、  ...  、 N-1 ） 循环
  
对于极个别的“灯 交换群”可构造出“N 陪集魔方”！
  
     当然，灯的形状也可自定义！ 大家可以试试！
  
   
     对比 “三陪集 正六面体四轴二阶魔方” ( Skewb ) ，需要注意的是：
  
     “正六面体四轴二阶魔方” ( Skewb ) 对于“四轴心”旋转构成“三陪集”
  
魔方，但如果按 八角方向旋转，那就谈不上“三陪集魔方”了！ 大家可以试试！
  
     对比 “ N 陪集魔方”，也要注意类似问题。
  
　　
　　
　　

lulijie

对于以下公式，有下面助记歌：
              B1 =A3+1                       B10 =A8+1
              B2 =A2+A4                     B9 =A9+A7
              B3 =A1+A3+A5+1           B8 =A10+A8+A6+1
              B4 =A2+A4+A6+1           B7 =A9+A7+A5+1
              B5 =A3+A5+A7+1           B6 =A8+A6+A4+1
                              10*10点灯歌
               1看3，      10看8，               没有灯亮点；         
               2看2、4， 9看9、7，          一盏灯亮点；
               余下就看三盏灯(n,n-2,n+2)，零盏、两盏灯亮点。

lulijie

10*10点灯的方法也可以如下：将原来第一步的点亮所有灯，变为熄灭所有灯。
这样，解法步骤如下：
第一步：从下往上逐渐熄灭每行的所有灯，只剩第一行，
            第一行灯的状态  S=A1A2A3A4A5A6A7A8A9A10     
           （Ai表示第一行第i列的灯的状态，值为1表示该灯亮，0表示灭。）
第二步：运用公式计算P的值：    P=B1B2B3B4B5B6B7B8B9B10
              B1 =A3+1                       B10 =A8+1
              B2 =A2+A4                     B9 =A9+A7
              B3 =A1+A3+A5+1           B8 =A10+A8+A6+1
              B4 =A2+A4+A6               B7 =A9+A7+A5
              B5 =A3+A5+A7               B6 =A8+A6+A4
         Bi为奇数表示点击最下面一行的第i个格子的灯，Bi为偶数表示该格子不点击。
第三步： 从下往上依次点亮每行格子的灯。
-----------------------------------------------------------------
这样若原来所有的灯都是熄灭的，那么所有的Ai值都等于0。代入上述公式得B1=B3=B8=B10=1，其他都等于0。
所以点击方法P就是1010000101。
将最下行的第1、3、8、10个格子各点击一下，然后从第九行往上，依次点亮所有下一行的灯即可。

lulijie

记得魔方转法中有换角、换边等公式，所谓的换角、换边公式，就是保持不参加交换的块不变的一系列手法公式。
       我突然觉得10*10点灯游戏中应该也有类似的公式。
       先把灯的一般状态转变成基本状态，使得除了第一行以外，其他各行的灯都是全亮的。
       那么第一行的第一列的灯若是灭的，那么应该存在一种点灯方法，该方法仅使得第一行第一列的灯的状态发生改变，而不影响其他所有的灯的状态。
10*10点灯的单格转换公式
      我们用g(m)表示仅使得第1行第m列的灯的状态发生改变，而其他所有灯状态都不改变的点灯方法。（可以用最后一行格子的点击组合来代替所有格子的点击方案）。
那么g(1)=3           g(10)=8
       g(2)=2,4        g(9)=7,9  
       g(3)=1,3,5   
       g(4)=2,4,6   
       g(5)=3,5,7  
       g(6)=4,6,8
       g(7)=5,7,9  
       g(8)=6,8,10
---------------------------------------------
这样经过第一步将一般状态转化成基本状态后，
若第一行只剩第3列的格子是灭的，因为g(3)=1,3,5
        那么只需要点击一下最后一行的第1、3、5格子，然后从第九行开始依次点亮下面一行所有的灯即可。
若第一行只剩第3、5列的格子是灭的，因为g(3)=1,3,5  ， g(5)=3,5,7
       那么先点击一下最后一行的第1、3、5格子，接着点击一下第3，5，7格子，然后从第九行开始依次点亮下面一行所有的灯即可。或者  g(3) + g(5)=1,3,5   +   3,5,7  =1,7        (点击两次等于不点击)
对于第一行其他的灯的状态，只要看那些灯是灭的，依次运行g(m)方法即可。
--------------------------------------------------------------------------------
这种方法的好处不用进行加法计算，转化为基本状态后，根据第一行那些灯灭着，对每盏熄灭的灯在第十行的格子各运行一次g(m)方法即可。g公式非常简单，点击过程几乎不假思索就可进行。

lulijie

如果我们用g(n,m)表示仅使得第n行第m列的灯的状态发生改变，而其他所有灯状态都不改变的点灯方法(点灯方法用最后一行需点击的格子的组合来表示)。
那么一共有100个值，运用这100个值，就可以推导出所有状态的最少步数解法。
--------------------------------------------------------------------
g(1,1)=3             ‘表示成10位2进制数就是  0010000000
g(1,2)=2,4           ‘表示成10位2进制数就是  0101000000
g(1,3)=1,3,5        ‘表示成10位2进制数就是  1010100000
g(1,4)=2,4,6        ‘表示成10位2进制数就是  0101010000
g(1,5)=3,5,7       ‘表示成10位2进制数就是   0010101000
g(1,6)=4,6,8       ‘表示成10位2进制数就是  0001010100
g(1,7)=5,7,9      ‘表示成10位2进制数就是    0000101010
g(1,8)=6,8,10      ‘表示成10位2进制数就是  0000010101
g(1,9)=7,9          ‘表示成10位2进制数就是  0000001010
g(1,10)=8           ‘表示成10位2进制数就是  0000000100

g(2,1)=2,3,4
g(2,2)=1,2,4,5
g(2,3)=1,3,5,6
g(2,4)=1,2,4,6,7
g(2,5)=2,3,5,7,8
g(2,6)=3,4,6,8,9
g(2,7)=4,5,7,9,10
g(2,8)=5,6,8,10
g(2,9)=6,7,9,10
g(2,10)=7,8,9

g(3,1)=1,5
g(3,2)=2,4,6
g(3,3)=5,7
g(3,4)=2,6,8
g(3,5)=1,3,7,9
g(3,6)=2,4,8,10
g(3,7)=3,5,9
g(3,8)=4,6
g(3,9)=5,7,9
g(3,10)=6,10


g(4,1)=1,3,5,6
g(4,2)=5,6,7
g(4,3)=1,3,4,6,7,8
g(4,4)=3,4,5,7,8,9
g(4,5)=1,2,4,5,6,8,9,10
g(4,6)=1,2,3,5,6,7,9,10
g(4,7)=2,3,4,6,7,8
g(4,8)=3,4,5,7,8,10
g(4,9)=4,5,6
g(4,10)=5,6,8,10

g(5,1)=3,5,7
g(5,2)=2,8
g(5,3)=1,5,9
g(5,4)=4,6,10
g(5,5)=1,3,5,7
g(5,6)=4,6,8,10
g(5,7)=1,5,7
g(5,8)=2,6,10
g(5,9)=3,9
g(5,10)=4,6,8

g(6,1)=1,2,6,7,8
g(6,2)=1,2,3,5,6,8,9
g(6,3)=2,3,5,7,9,10
g(6,4)=5,6,8,10
g(6,5)=2,3,4,6,7,9,10
g(6,6)=1,2,4,5,7,8,9
g(6,7)=1,3,5,6
g(6,8)=1,2,4,6,8,9
g(6,9)=2,3,5,6,8,9,10
g(6,10)=3,4,5,9,10

g(7,1)=9
g(7,2)=8,10
g(7,3)=7,9
g(7,4)=6,8
g(7,5)=5,7
g(7,6)=4,6
g(7,7)=3,5
g(7,8)=2,4
g(7,9)=1,3
g(7,10)=2

g(8,1)=1,2,6,7,9,10
g(8,2)=1,2,3,5,6,7,9,10
g(8,3)=2,3,5,6
g(8,4)=9,10
g(8,5)=2,3,5,6,8,9,10
g(8,6)=1,2,3,5,6,8,9
g(8,7)=1,2
g(8,8)=5,6,8,9
g(8,9)=1,2,4,5,6,8,9,10
g(8,10)=1,2,4,5,9,10

g(9,1)=3,5,9
g(9,2)=2,6,8,10
g(9,3)=1,9
g(9,4)=6
g(9,5)=1,5,7,9
g(9,6)=2,4,6,10
g(9,7)=5
g(9,8)=2,10
g(9,9)=1,3,5,9
g(9,10)=2,6,8

g(10,1)=1,3,5,7,8
g(10,2)=7,8,9
g(10,3)=1,3,5,6,8,9,10
g(10,4)=5,6,7,9,10
g(10,5)=1,3,4,6,7,8
g(10,6)=3,4,5,7,8,10
g(10,7)=1,2,4,5,6
g(10,8)=1,2,3,5,6,8,10
g(10,9)=2,3,4
g(10,10)=3,4,6,8,10
------------------------------------------------------
将所有灯不亮的格子的n,m值代入g(n,m)中，将它们全部相加，若某个数字出现偶数次，将它全部消除；若出现奇数次，保留一个。这样得到的结果就是最少步数解法。它比前面的解法少了第一步，可以直接得到结果。
这种方法适用于电脑解答，金眼睛可以将它整合进他的点灯程序中。
         (可以用10位2进制数表示g(n,m)，用异或运算表示不同的g(n,m)相加，计算结果非常快）

yang_bigarm

原帖由 superacid 于 2009-7-3 15:19 发表
可以编程搜索，就1024种情况嘛

您在开玩笑吗？怎么是1024种情况呢？应该是2^1024种情况吧。

原帖由 sokoban 于 2009-7-4 12:26 发表
就是解一个线性方程组，可以参考这个：

http://mathworld.wolfram.com/LightsOutPuzzle.html

我原来就思考过这个问题，后来在mathWorld上看到了答案，确实不能盲目搜索啊，要
靠解一个0-1矩阵的方程，我是用mathematica解的，自己编比较麻烦。但是mathWorld
上面只是给了方程，然后就是让你求逆举证，可是如果你直接调用mathematica求逆矩阵
可能求不出来，但是如果回到求逆矩阵本源的方法——高斯消元法，就可以得到正解。

注意这个0-1矩阵的方程可能无解，按照线性代数书上的判别准则，初始条件构成的0-1矩阵
和原来的0-1矩阵构成的叫增广矩阵，增广矩阵的秩大于方程矩阵的秩，那就无解了。

关于点灯游戏，我知道的大概也就这么多了，如果对于更大规模的问题，比如20x20方格的
点灯游戏，直接求解方程也是很慢的，但是高斯消元法有并行的算法，即在多个CPU上运行
的算法，用这个方法可以求解规模稍微大一些的问题。这个问题的算法复杂度是O(n^4)  
（求矩阵的逆是 n^2， 矩阵的规模又是 n^2）。