如何快速解关灯游戏-高斯消元

想必许多使用gnome桌面环境的用户都玩过一个自带游戏，那就是Lights Off，中文名叫关灯。

在这个游戏中，界面由2种状态的矩阵组成，用方格的亮与暗代表灯的开与关，当鼠标点击一个方块时，与它有公共边的方块和这个方块本身都会改变状态，由开变关或由关变开，相当于二进制中的异或运算。

那么，这个问题如何编程解决呢？我先从一年前的我什么算法都不会只会打搜索是如何解决这道题的。

首先，我们先确定一个规则，因为一个方块改变2次之后，等于没有进行任何一次改变，所以，我们可以肯定的是，一个方块最多改变一次。

所以，我们只要枚举每个方块被点击与没有被点击两种情况进行枚举，时间复杂度是O(2^(h*w))，h、w分别为矩阵的长宽。

显然，这个时间复杂度是不可接受的。我相信大多数人的智商，解决一个6*6的方格都比用这种方法等待计算机算快得多吧。

然后我们还可以用迭代加深搜索进行优化，从每次枚举1个方格，到每次枚举两个方格，再到每次枚举三个方格，这样的时间复杂度是O(玄学)。但一旦这个关卡所需的最少步数太多，也就无法在短时间内找到答案。

此外，我们可以使用广度优先搜索来取代迭代加深搜索，可以优化时间常数为迭代加深搜索的1/2，但有一个严重的后果，如果你的电脑没有足够的内存，根本无法存储如此多的状态数。我曾经写一个9*9的BFS就把我的16G内存给爆了。

那么，我们还有什么办法呢？剪枝？等待量子计算机帮助我们实现？

实际上，这是一个线性代数的问题。

我们可以采用高斯消元法来解这个异或方程。

对于每个方格的点击，有0和1两种情况，每个方格点击会对自己和周围的方格进行异或(xor)1计算。

那么，对于一个2*2的方格，我们期望从全0变成全1，可以列以下方程，对于方格中的格子，我们采用p(x,y)来表示。对于每个格子是否点击的状态，我们采用b(x,y)来表示。

其中，0为初始状态。

p(1,1)=1=0 xor b(1,1) xor b(1,2) xor b(2,1)

p(1,2)=1=0 xor b(1,1) xor b(1,2) xor b(2,2)

p(2,1)=1=0 xor b(1,1) xor b(2,1) xor b(2,2)

p(2,2)=1=0 xor b(1,2) xor b(2,1) xor b(2,2)

那么，接下来的问题就转换成了如何解决这个方程。

加减消元很简单，初中生都会，那么高斯消元如何做呢？

首先，我们先把它处理成一个矩阵。

其中这个矩阵每行的最后一列数字，代表我们期望的最终状态

matrix[0]={1,1,1,0,1}

matrix[1]={1,1,0,1,1}

matrix[2]={1,0,1,1,1}

matrix[3]={0,1,1,1,1}

每一行最后一列代表每个矩阵格子的最终状态，除最后一列外的每一列相当于控制这个格子的相邻格子的系数。

那么问题来了，如何消元？

我们一列一列来。

首先，如同正常的高斯消元一样，在指定的一列取出一个最大的系数，显然这里就是取1。

然后将含有最大系数的这一行，以下称为x行，翻转到第当前需要处理的这一行上。

如果此时找不到最大系数的时候，即都是0的时候，那么就可以认定这个系数的解是一个自由元。在这个异或方程中，每出现一个自由元，该方程的解方案数*2。

之后，我们遍历矩阵的每一行，如果当前行不是x行，且遍历到的当前消元列系数为1的话，那么我们对这一整行异或x行。之后得到的每一行最后一列的系数，便是这个方程的解。

以下是C语言代码

int gauss() {
    int ways = 0;
    for (int i=0;i<n;i++) {
        int k = i;
        for (int j=i+1;j<n;j++) if (ma[j][i] == 1) k = j;
        int now = ma[k][i];
        if (now == 0) ways ++;
        if (k != i) for (int j=i;j<=n;j++) swap(ma[i][j],ma[k][j]);
        for (int k=0;k<n;k++) if (k != i && ma[k][i]) {
            for (int j=i;j<=n;j++) ma[k][j] = ma[k][j] ^ ma[i][j];
        }
    }
    return ways;
}

最后，这个时间复杂度就被我们优化成了O(n^3)

此外，我的解关灯程序的代码已在GitHub上开源，感兴趣的可以访问https://github.com/cyyself/light-off-game-solver/

你还可以尝试一下POJ 1222这道题，前排提醒数据很弱，写错的高斯消元都能过，你写时间复杂度超级长的搜索也能过。