《求解关灯游戏》源码分析之二

还是这个代码


http://blog.163.com/prevBlogPerma.do?host=simplesource&srl=10341406200981362416959&mode=prev


这几天对代数计算部分的源码研究了一下。代数都忘光了，重新看了些矩阵的知识，总算对算法有了个大概的了解。


=====================================


如下是原文：


吧上面的矩阵看成一个m*n的向量X=(x1,x2,...,x(m*n))

　　对于位置k上的开关，它将变化最多5个位置的开关，对应一个向量

C(k)=(0,0,...,1,0,....,1,...,0)

　　其中开关状态改变的位置为1，开关状态不改变的位置为0

对于初始向量X=(x1,x2,...,x(m*n)),使用了开关C(k)后，状态会变成

X+C(k) (mod 2)

　　所以对初始向量X,我们需要选择一系列的k1,k2,...,ks使得

X+C(k1)+C(k2)+....+C(ks) (mod 2)=O=(0,0,0,...,0)

　　我们可以同样构造一个0,1向量Y,使得，如果位置k出现在k1,k2,...ks中，那么Y

在位置k的值是1，不然是0，这样，我们就可以将上面公式写成矩阵形式

X+Y*C (mod 2)=O

　　其中C=(C(1)' C(2)' .... C(m*n)')'

　　也就是C是由这m*n个行向量构成的矩阵，第k行就是向量C(k)

　　最二阶域上，加和减是相同的，也就是上面的方程等价于

Y*C (mod 2)=X

　　其中C,X已知，求Y.

　　由于(mod 2)运算是一个域 （关于乘除加减封闭，加减是mod 2加减，还满足结合率，交换率）

所以我们可以直接在二阶域上用高斯消元法求解（注意加减是mod 2的，对应计算机上的异或运算）

其中，如果C可逆，解是唯一的，如果C不可逆，解可能不存在，也可能不唯一。


=====================================


这个代码写得很清晰。我大概描述一下吧：


>>也就是C是由这m*n个行向量构成的矩阵，第k行就是向量C(k)

1、获得 C，放入矩阵 m_switch 里；

2、求出  C 的 逆矩阵，放入 m_trans;

3、X*(C-1)，求得 Y，即 m_recorder。


然后验证一下，正确的话，即代表解是对的。



这个代码也从 c 移植成 java 了。


=====================================


其实，对于低阶的，还有一种查表算法，貌似更快。改天我写写看。


另外，这里还有个 applet 程序

http://www.anarkasis.com/rafa/



嗯，直接在这里可以运行

http://www.anarkasis.com/rafa/luces/lights.htm



这里给出的解比较多。一个图有四个解。



这个也是开源的。被收入在 wikipedia.org 里。

评论

1 楼 zwhc 2010-07-13  

http://topic.csdn.net/t/20050119/10/3737122.html

这道题就是经典的关灯游戏。题目中已经给出了提示，暗示我们可以一行一行或是一列一列的将灯关掉，通过在第i+1行上按键关掉第i行的灯，或通过在第 i+1列上按键关掉第i列的灯。我们采用一列一列关灯的方法。经过思考，我们可以得知，当第一列的按法确定后，后面每一列的按法就确定下来了：若第i行第 j列的灯是亮的，则需要在第i行j+1列按一下。在最后一列按完后，结果也定了。若结果是最后一列的灯全部关掉，则此按法是一个符合题意的解。因此，我们只需要枚举第一列的按法，然后进行模拟，一列一列的关灯，判断最后一列是否全部关掉即可。矩阵的规模非常小，仅5×6，算法复杂度为O(2^5   *   5   *   5)，不需任何顾忌。

========================================

昨天，我说：其实，对于低阶的，还有一种查表算法，貌似更快。改天我写写看。

基本思路和上面的贴子一样。

因为各种情况，都可以简化成最后一行。那么，将所有的情况列出，按最后一行的不同进行保存在一个对应表里。
求解时，也简化成最后一行，从对应表里进行查找。再将按了两次的开关取消，就得到解了。