点灯游戏的解法讨论

lulijie

楼主所谓的最乱状态，无非指最少步数最大的状态。
最少步数最大的就是每个格子都点击一次。
应该是将全亮的状态每个格子都点击一次形成的状态，如下：
        

noski

顶，分析得漂亮！
我发现一个有意思的地方：
你11楼这个图，是从灯全亮状态下每个格点击一下，一共点击了100下得到的。
我按照你前面的解法来解这个图，先从下至上把灯全部点亮，除了最顶行，这用了42步；
查得状态633：204，然后从上至下把灯全部点亮，用了58步，加起来恰好是100步！

还有，lulijie贴出的1024表格挺有用的，但是玩起游戏来还要查表，就不那么容易了，谁也记不住啊，呵呵！

另外1楼游戏的小BUG：在一个格子里狂点三四下，这几格的灯就全亮或全灭了-_-

superacid

谢谢sokoban，看来这样的问题就是要解一个矩阵方程，长见识了。

superacid

不过好像如果阶数再大一点，电脑会算爆掉的

noski

回复sokoban：
回复superacid：
sokoban发的链接中的方法直接可以解出最终结果，对于10*10的游戏，要解一个100维的非齐次线性方程组。
这样看来，“最少步数”“最乱状态”什么的就都可以靠穷举搜索出来。

看看能不能找到一个可玩性好点的策略，让这个游戏除了查表、解方程组之外，不只是碰运气-___-，这样没事还可以玩一玩。。
就像平时玩魔方，我们不是对于每个乱的魔方，都去全空间搜索它的最短路径来还原它，而是有一系列的方法，比如层先、CFOP等。。

今夜微凉

点灯可以用~~层先法~~~呵呵~~所以只需要最后一层的公式即可~~情况也不多~~

lulijie

先将一般状态转化为基本状态S，解决方法为P：
那么S和P的关系可以：
1.   查表法。
2.   可以用表达式法。
    S=A1A2A3A4A5A6A7A8A9A10   （十位二进制）
    设 P=B1B2B3B4B5B6B7B8B9B10  ，那么
    B1=A1+A3+A5+A7+A8+1                            这里的加法是模2加法（也就是总和除以2，取它的余数。)
    B2=A7+A8+A9+1
    B3=A1+A3+A5+A6+A8+A9+A10+1
    B4=A5+A6+A7+A9+A10+1
    B5=A1+A3+A4+A6+A7+A8

    B6=A3+A4+A5+A7+A8+A10
    B7=A1+A2+A4+A5+A6+1
    B8=A1+A2+A3+A5+A6+A8+A10+1
    B9=A2+A3+A4+1
    B10=A3+A4+A6+A8+A10+1
  十条公式，其实只要记忆前面5条就可，（1-5 与10-6 公式是对称的。）
---------------------------------------------
用这些式子的好处是不用进行进制的换算。
直接根据第一行灯的亮灭情况写出 A1A2A3A4A5A6A7A8A9A10 ，
然后运用公式得到B1B2B3B4B5B6B7B8B9B10。
根据B1B2B3B4B5B6B7B8B9B10，就可以直接进行第一行灯的点击操作，非常方便。

今夜微凉

原帖由 lulijie 于 2009-7-5 09:28 发表
先将一般状态转化为基本状态S，解决方法为P：
那么S和P的关系可以：
1.   查表法。
2.   可以用表达式法。
    S=A1A2A3A4A5A6A7A8A9A10   （十位二进制）
    设 P=B1B2B3B4B5B6B7B8B9B10  ，那么
    B1=A1+ ...

楼上的十分详细啊~~看来已经完全解决点灯问题了~~呵呵

lulijie

公式法，跟楼主所推崇的魔方解法很类似。
第一步：层先法  ，最后只剩最上面一层。
第二步：运用公式，只要记忆5个（或10个）公式，比魔方的公式少多了，而且公式很简单。
第三步：返层。完成。

lulijie

前面所说的公式法，在第二步，运行公式的时候，由于点击的格子会影响灯的亮灭状态，所以不能边点击边计算公式，必须10个公式一次性计算完毕，才能开始点击，影响了速度。
    我现在把解决方案P的点击不放在第一行，而是放在最下一行，这样可以边点击边运用公式计算结果，速度加快。
这样重新计算，得到计算公式如下，非常简洁：
    S=A1A2A3A4A5A6A7A8A9A10   （十位二进制）
       设 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+1           B7 =A9+A7+A5+1
              B5 =A3+A5+A7+1           B6 =A8+A6+A4+1
-------------------------------------------------
这样，解法步骤如下：
第一步：从下往上逐渐点亮每行的所有灯，只剩第一行，
             转化为基本状态  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+1           B7 =A9+A7+A5+1
              B5 =A3+A5+A7+1           B6 =A8+A6+A4+1
         Bi=1表示点击最下面一行的第i个格子的灯，Bi=0表示该格子不点击。
第三步： 从下往上依次点亮每行格子的灯。
-------------------------------------------------------------------------------------
我觉得非常完美了，公式非常好记，楼主应该够满意了吧。