小游戏 Lights Out (关灯) 的求解 —— 异或方程组

时间:2021-04-23 00:45:16
Author : Evensgn 
Blog Link : http://www.cnblogs.com/JoeFan/
Article Link : http://www.cnblogs.com/JoeFan/p/4338003.html
 

游戏介绍

Lights Out (关灯)是一款据说在20世纪90年代就已经被设计出的小游戏,游戏的玩法十分简单。

首先,给定一个 n 行 m 列的矩形方格阵,每个格子上都有一盏灯。

初始时,有些灯是开着的,有些灯是关着的。

玩家每次进行一次操作,选中一盏灯,点击一下它,就会将它和与它相邻的灯的状态改变,即开着的灯变为关闭,关着的灯变为开启。

最后的目的是关闭所有的灯。

这里给出一个网页版的链接:关灯

还有博客园一位博友DIY的一个类似的游戏,蓝色拼图。这个蓝色拼图与 Lights Out 实质上相同,只是初始状态固定了是所有的灯都是开启的。

Lights Out 的游戏规则就是这样简单,然而到了后面的几关,方格增多,情况复杂,人工找出解法对于我来说是十分困难的。

因此,我们考虑用程序求解这个游戏。

求解方法

首先我们要将这个游戏的过程转化为数学模型。

显然地,对于一个方格,会影响到它的方格只有它本身和与它相邻的 4 个方格(对于边界的方格来说,相邻的方格不足 4 个)。

并且很容易发现,每一个方格我们要么不点击,要么点击 1 次,因为点击一个方格两次及以上是没有任何意义的。每点击两次就相当于没有点击。

对于方格 i ,我们用 0 表示不点击它,用 1 表示点击它,记作 Si 。

每盏灯的状态只有开或者关,我们用 0 和 1 表示方格 i 状态,方格 i 的初始状态记为 Mi 。

可以看出,每盏灯 i 的最终状态只与 Mi + Si + Sk1 + Sk2 + .... + Skp  (k1 ... kp 是枚举与 i 相邻的所有方格)的奇偶性有关。

既然只与奇偶性有关,我们就可以用异或运算来表示它。

也就是说,对于每盏灯 i ,我们都可以得到一个方程       Mi xor Si xor Sk1 xor Sk2 xor ... xor Skp = 0 。

等式右边的 0 表示最后每盏灯的状态都是关闭的。

这个方程其实也就等价于        Si xor Sk1 xor Sk2 xor ... xor Skp = Mi 。

我们得到了 Tot 个这样的方程(Tot 是灯的数量,即 Tot = n * m),共有 Tot 个未知数(即 Tot 个 Si),就是一个异或方程组。

由于游戏给定的初始状态一定有解,所以我们是一定可以求出这个异或方程组的一组解的。

那么下面的问题就是:怎样求解异或方程组?

显然,我们要使用高斯消元来求异或方程组的解。

这个过程与使用高斯消元求解普通的线性方程组相似(如果不了解高斯消元可以看一下Wikipedia-高斯消去法),只是每次在一个方程中消去一个未知数的时候,不是将这个方程乘上一个系数后与另一个方程相减,而是将这个方程的系数与另一个方程的系数进行异或运算,两个方程右边的数也要一起进行异或。

这样就可以求出 Lights Out 的解了。

代码如下,因为代码非常简单所以没有添加注释:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; const int MaxL = 10 + 5, MaxN = 100 + 5;
const int Dx[5] = {0, 0, 1, -1}, Dy[5] = {1, -1, 0, 0}; int n, m, Tot;
int A[MaxN][MaxN], Map[MaxL][MaxL], Ans[MaxL][MaxL]; inline bool Inside(int x, int y)
{
if (x < 0 || x >= n) return false;
if (y < 0 || y >= m) return false;
return true;
} inline int Get_Index(int x, int y)
{
return x * m + y + 1;
} struct Pos
{
int x, y;
}; inline Pos Get_Pos(int Num)
{
Pos ret;
ret.x = (Num - 1) / m;
ret.y = ((Num % m - 1) + m) % m;
return ret;
} void Get_Equation(int x, int y)
{
int Id, Id2, xx, yy;
Id = Get_Index(x, y);
for (int i = 1; i <= Tot; ++i) A[Id][i] = 0;
A[Id][Tot + 1] = Map[x][y];
A[Id][Id] = 1;
for (int k = 0; k < 4; ++k)
{
xx = x + Dx[k]; yy = y + Dy[k];
if (!Inside(xx, yy)) continue;
Id2 = Get_Index(xx, yy);
A[Id][Id2] = 1;
}
} inline void Swap(int p, int q)
{
int Temp;
for (int i = 1; i <= Tot + 1; ++i)
{
Temp = A[p][i];
A[p][i] = A[q][i];
A[q][i] = Temp;
}
} void Gauss()
{
int Tj;
for (int i = 1; i <= Tot; ++i)
{
Tj = i;
for (int j = i + 1; j <= Tot; ++j)
{
if (A[Tj][i] == 0 && A[j][i] == 1)
{
Tj = j;
break;
}
}
if (A[Tj][i] == 0) continue;
if (Tj != i) Swap(Tj, i);
for (int j = i + 1; j <= Tot; ++j)
{
if (A[j][i] == 0) continue;
for (int k = i; k <= Tot + 1; ++k)
A[j][k] ^= A[i][k];
}
} Pos Pi;
for (int i = Tot; i >= 1; --i)
{
Pi = Get_Pos(i);
Ans[Pi.x][Pi.y] = A[i][Tot + 1];
for (int j = i - 1; j >= 1; --j)
if (A[j][i]) A[j][Tot + 1] ^= A[i][Tot + 1];
}
} int main()
{
scanf("%d%d", &n, &m);
Tot = n * m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
scanf("%1d", &Map[i][j]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
Get_Equation(i, j);
Gauss(); printf("Solution:\n");
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
printf("%d", Ans[i][j]);
printf("\n");
}
return 0;
}