点灯游戏的解法讨论

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
上述公式的记忆方法可以这样：
  1.   距边1个格子的地方，只有1个加数，
        距边2个格子的地方，只有2个加数，
        距边3个以上格子的地方，有3个加数。
2.     第一个加数是 该格子往中间方向行2个格子的值。若还有第二、第三个加数，那么每个加数都是往边上行2个格子。
      若加数的个数是奇数，则需加上1。
---------------------------------------------
比如B8，8往中间方向行2个格子，就是A6，因为总共3个加数，依次加上A8，A10（往边方向行每次行2格），奇数个加数再加1。
    所以B8=A6+A8+A10+1

金眼睛

呵呵，其实没有那么麻烦，无论是n*n的方阵，还是m*n的方阵，都可以采用倒推的方法解决。

开始的时候设定灯都是亮的，对最下面一行的灯采用各种点击方式（如本例共有1024种点击方式），然后倒推到前两行，记录下第一行将第二行的灯都打亮的操作以及最后第一行灯的状态即可。

这里最后一行的状态及操作，还有第一行的状态及操作是一一对应的。
例如：最后一行状态（固定为：1111111111），最后一行操作（取1024中的一种，例如：000000001）

          倒推到第一行：
          第一行状态（对应为：1010111010—698），第一行操作（对应为：1101010101—853）

可以看到这与lulijie提供的表中的数据是一致的，其实它们都来源于倒推的第一步操作000000001。

当所有操作的结果都获得了以后，就可以按图索骥了。

最后鉴于noski提供的Flash中存在小bug，而且没有全开全关也不便研究，我重新编了一下。

时间仓促，如果有什么错误或者好的建议就留言吧，我好进行更正，o(∩_∩)o...

[ 本帖最后由 金眼睛 于 2009-7-5 15:35 编辑 ]

Cielo

楼上两位真厉害，我来学习一下！

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方框。

金眼睛

呵呵，你的提议很好啊，多谢多谢！

明天上班，没时间弄了，先弄了一版没提示的，本着娱乐精神，加入了一些好玩的功能，哈哈！

sokoban

金眼睛兄的新版本很好用，我十分喜欢。

superacid

新版本某些功能蛮有趣的。

noski

lulijie在20楼的解法很不错，用此法可一举解决点灯问题，在步数和时间上有个平衡，可玩性好。。
在理解了这个解法之后就可以更直观一些，不用记任何公式。比如对于距边3个格子以上的地方（N，1），只要看（N-2，10）、（N，10）、（N+2，10）这三个位置亮灯的个数，如果亮的灯是偶数，就需要点击一下。

金眼睛的小程序也很赞，还有击缶功能

ggglgq

　　
　　
  
    这是一个典型的“交换群”，因此它可以用“线性方程组”来解决。
  
    看到 sokoban 的发言，使我想起 “三陪集 正六面体四轴二阶魔方”(Skewb) 。
  
相关讨论请大家参考：
  
    Skewb 中的一些理论问题  http://bbs.mf8-china.com/viewthread.php?tid=18112
  
那么什么样的魔方是“三陪集魔方”、“ N 陪集魔方”呢？请大家参考：
  
  奇偶差异性魔方的拓展推广  http://bbs.mf8-china.com/viewthread.php?tid=7532&page=1#pid109484