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


想必许多使用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。

然后将含有最大系数的这一行翻转到第当前需要消元的这一行上。

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

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

以下是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((h*w)^3)

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注