点灯游戏的解法讨论

lulijie

公式法：采用我的20楼的方法。对于n*m方阵，结果如下
------------------------------------------------
4*4、5*5、9*9、11*11、3*2、5*2、7*2、9*2、5*3、8*3、9*4、7*5、8*5、9*5、8*6、8*7、9*8
    无公式解，即某些状态无解。
------------------------------------------------
2*2、4*2、6*2、8*2、10*2
    B1 =A1+1
    B2 =A2+1
------------------------------------------------
3*3
    B1 =A2+A1
    B2 =A3+A2+A1+1
    B3 =A3+A2
---------------------------
4*3、6*3
    B1 =A3+1
    B2 =A2+1
    B3 =A1+1
------------------------
7*3、9*3
    B1 =A2+A1
    B2 =A3+A2+A1+1
    B3 =A3+A2
-----------------
10*3
    B1 =A1+1
    B2 =A2+1
    B3 =A3+1
--------------------------------------------------
4*5、10*5
B5 =A1+1
B4 =A2+1
B3 =A3+1
B2 =A4+1
B1 =A5+1
-------------------
6*4
B1 =A3+1
B2 =A4+A2
B3 =A3+A1
B4 =A2+1
-------------------
7*4
B1 =A4+A3+A1+1
B2 =A4+A3
B3 =A2+A1
B4 =A4+A2+A1+1
------------------
8*4、10*4
B1 =A1+1
B2 =A2+1
B3 =A3+1
B4 =A4+1
----------------------------------
6*5
B1 =A1+1
B2 =A2+1
B3 =A3+1
B4 =A4+1
B5 =A5+1
-----------------------
6*6、10*6
    B1 =A3+A1
    B2 =A4+1
    B3 =A5+A1
    B4 =A6+A2
    B5 =A3+1
    B6 =A6+A4
----------------------------
7*6、9*6
B1 =A4+A3+A1+1
B2 =A5+A4+A3+1
B3 =A6+A5+A4+A2+A1+1
B4 =A6+A5+A3+A2+A1+1
B5 =A4+A3+A2+1
B6 =A6+A4+A3+1
------------------------------------------
7*7
    B1 =A2+A1
    B2 =A3+A2+A1+1
    B3 =A4+A3+A2+1
    B4 =A5+A4+A3+1
    B5 =A6+A5+A4+1
    B6 =A7+A6+A5+1
    B7 =A7+A6
---------------------------------------------
9*7
B1 =A4+A3+A2+1
B2 =A5+A4+A2+A1
B3 =A6+A5+A3+A1
B4 =A7+A6+A4+A2+A1+1
B5 =A7+A5+A3+A2
B6 =A7+A6+A4+A3
B7 =A6+A5+A4+1
----------------------------------------
10*7
B1 =A5+A3+A1+1
B2 =A6+1
B3 =A7+A3+A1+1
B4 =A4+1
B5 =A7+A5+A1+1
B6 =A2+1
B7 =A7+A5+A3+1
-----------------------------------------------
8*8
    B1 =A5+A3
    B2 =A6+A2
    B3 =A7+A1
    B4 =A8+1
    B5 =A1+1
    B6 =A8+A2
    B7 =A7+A3
    B8 =A6+A4
----------------------------
10*8
B1 =A7+A3
B2 =A8+A6+A4+A2
B3 =A7+A3+A1+1
B4 =A2+1
B5 =A7+1
B6 =A8+A6+A2+1
B7 =A7+A5+A3+A1
B8 =A6+A2
--------------------------
10*9
B1 =A7+A3+A1+1
B2 =A8+A6+A4+1
B3 =A9+A7+A1+1
B4 =A8+A4+A2+1
B5 =A5+1
B6 =A8+A6+A2+1
B7 =A9+A3+A1+1
B8 =A6+A4+A2+1
B9 =A9+A7+A3+1
--------------------------------
10*10
    B1 =A3+1
    B2 =A4+A2
    B3 =A5+A3+A1+1
    B4 =A6+A4+A2+1
    B5 =A7+A5+A3+1
    B6 =A8+A6+A4+1
    B7 =A9+A7+A5+1
    B8 =A10+A8+A6+1
    B9 =A9+A7
    B10 =A8+1
-------------------------------------
12*12
    B1 =A9+A7+A5+1
    B2 =A10+A4
    B3 =A11+A7+A3+1
    B4 =A12+A8+A6+A2
    B5 =A9+A7+A5+A1
    B6 =A12+A10+A8+A6+A4+1
    B7 =A9+A7+A5+A3+A1+1
    B8 =A12+A8+A6+A4
    B9 =A11+A7+A5+A1
    B10 =A10+A6+A2+1
    B11=A9+A3
    B12 =A8+A6+A4+1
-----------------------------------
13*13
    B1 =A12+A11+A10+A6+A5+A3+A2+1
B2 =A13+A12+A10+A9+A7+A6+A5+A3+A2+A1
B3 =A13+A11+A9+A7+A6+A2+A1+1
B4 =A13+A12+A10+A9
B5 =A12+A11+A10+A8+A7+A6+A2+A1
B6 =A9+A8+A6+A5+A3+A2+A1+1
B7 =A12+A11+A9+A7+A5+A3+A2+1
B8 =A13+A12+A11+A9+A8+A6+A5+1
B9 =A13+A12+A8+A7+A6+A4+A3+A2
B10 =A5+A4+A2+A1
B11 =A13+A12+A8+A7+A5+A3+A1+1
B12 =A13+A12+A11+A9+A8+A7+A5+A4+A2+A1
B13 =A12+A11+A9+A8+A4+A3+A2+1

lulijie

金眼睛兄的点灯程序还可以优化：
1.状态栏不用手动输入（可以把它从窗口中删除），直接根据左边格子上的灯的状态，给出解法。
2.左边的灯也不要求2-9行灯全亮，任意一般状态，直接给出最少步数解，最少步数解只要给出第一行的解就行。解法的框足够显示，不用扩大。
3.最好设计一个选择项，可以选择n*m方框。

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)相加，计算结果非常快）