猫史档案馆

-----------------------------------------------------------分割线------------------------------------------------------

介绍：“点灯游戏”是一款很经典的数学游戏，此帖针对“点灯游戏”展开数学讨论。

实验工具（赶着做的，UI不太好，能用就行）：

话题1：讨论初始状态为全黑色的“点灯游戏”的通用解法。

解释说明：运用数学方法，计算a*b点灯游戏的点灯步骤（初始为全黑色）。

话题2：讨论随机初始状态下是否一定可以通关（即全点成白色）。

解释说明：如任何情况均可以通关，求出至多步数；

如存在不能通关的情况，请列出此情况（或多个情况）。

作者在评论区和你们一起讨论~

橘生淮北则为枳

这玩意怎么搞啊 emotion_雷电猴_疑问

呵呵哒的小小李

来简单说两句，这种题我也只是见过几次，没有太多详尽的了解，下述内容仅供参考。

首先，对于开关灯游戏有三个很显然的结论

1. 每个灯只会被点击0次或1次，一定不会被点击2次及以上

2. 点击灯的顺序不影响结果，也就是点击灯可以用操作集合表示，而不一定是操作序列

3. 将某些特定的灯打开所需要的操作集合和将这些灯还原（重新关上）的操作集合完全相等，即点灯操作符合异或性质

考虑到点灯序列和最终亮灯状态形成映射关系，且一种点灯序列显然仅对应一种亮灯结果，加之两者在n * m的矩阵中均只有2^(喵)种不同状态，因此会有一个比较trivial的结论：如果点灯序列和状态不形成一一对应的映射关系，则一定存在无法通关的初始情况，证明显然。

不过这的确是trivial的，毕竟我们都知道确实存在一些情况下的灭灯游戏无法通关。例子可以自己画画，这里不加赘述。

下面考虑对于初始状态已给出，目标为全白色的数学+信息学解法

考虑将灯的状态用0和1表示，则点击的操作可视为二元域下的加法运算，或单纯的模2意义下加法，又或是异或操作，都可以。

因此可以将初始状态用一个n*m大小的向量表示（当然，要先给格子编号），我们称其为初始状态向量，设为B（begin简写）

每一个格子点击后都会对一些格子造成状态改变，我们通常称其为状态转移。令一个n*m的行向量上每一位对应一个格子的状态是否会因为当前考虑的格子被点击而改变，改变为1，否则为0，这样每个格子都对应一个行向量，这些向量被称为状态转移向量，设为T（transform简写）。

所以我们的任务变成了从所有转移向量中挑选一些，满足B+∑T=0，这里的0表示0向量，即每一位都是0的向量。

由于这一加法运算是在二元域下进行的，一定满足B+B=0（在二元域下，0+0=1+1=0），因此两边同时加上B，即要求满足∑T=B。

但是怎么知道我们要选哪些T呢？这就是方程的作用。对于第i个T，设其为Ti，定义xi为这个Ti选还是不选，由于一开始我们就说过的结论：每个格子至多点击一次，因此xi也只会是0或1，所以我们最终就是求：

x1*T1+x2*T2+···+x(n*m)*T(n*m)=B

这个n*m元1次方程组的解。将n*m个行向量按顺序拼接为(n*m)*(n*m)的状态转移矩阵，最终就是求这个矩阵左乘（x1, x2, x3, ···, x(n*m)）这个列向量等于B（也是n*m大小的列向量）的解（这里的解还是求x1到x(n*m)，只是换了一种形式）

然后你就会注意到这个东西的形式非常好，可以直接高斯消元，对于n*m比较大的可以LU分解来做，不管怎么说这些就都是计算机的工作了。如果该向量无解，就表示该初始状态下没有可行解。需要注意的是做消元运算的时候也要时刻注意这是在二元域意义下的运算，或者说模2意义下，千万要注意1+1=0这类东西。

这样就解决了对于给定初始状态的n*m矩阵点灯问题，对于给定初始状态且给定终结状态的问题，只需要直接把两者异或一下，就转化为了只给定初始状态，终结状态就是全白的点灯问题，就不多说了。

时间复杂度上Gauss-Moore可能复杂度过高，LU分解比较复杂，建议直接调np.linalg.solve()解决一切问题（bushi，对于其默认按正常运算而不是模意义下运算的问题，可以引入Numpy支持的含GF2的其他库解决，这里就不多说了，毕竟我也没真正搞过二元域这东西。

差不多就这样，希望可以帮到你。

囧仙_official

不能通关情况

黑白

囧仙_official

#include<bits/stdc++.h>
using namespace std;
int n,m; 
int ans = 0;
int pos_to_num(int x,int y){
	if(x < 0 || y < 0 || x >= n || y >= m)
		return -1;
	return y*n+x;
	
}
pair<int,int> num_to_pos(int num){
	return {num/n,num%n};
}
const int dirx[] = {-1,0,0,0,1},
		  diry[] = {0,-1,0,1,0};
bitset<300> t[300];//线性基

void insert(bitset<300> a){
	bitset<300> p = a;
	for(int i = 299; ~i; i--){
		if(a[i]){
    		if(t[i].none()){
				t[i] = a;
				ans++;
				return;
				
			}
			a^=t[i];
		}
		/*if(!a){
			flag = 1;
			break;
		}*/
	}
	return;
}
void init(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
		 
			bitset<300> b;//待插入 
			
			for(int k = 0; k < 5; k++){
				int x1 = i+dirx[k],
					y1 = j+diry[k];
				int numb = pos_to_num(x1,y1);
				if(numb > -1 && numb < n*m){
					b[numb] = 1; 
				}
			}
			insert(b);
		}
	}
}//初始化线性基
bool check(bitset<300> a){
	 for(int i = 300-1; ~i; i--){
		if(a.test(i)){
    		if(t[i].none()){
				//t[i] = a;
				return 0;
			}
			a^=t[i];
		}
		/*if(!a){
			flag = 1;
			break;
		}*/
	}
	return 1;
}//试着插入 
int step(bitset<300> a){
	for(int i = 300-1; ~i; i--){
		if(a.test(i)){
    		if(t[i].none()){
				//t[i] = a;
				return 1;
			}
			a^=t[i];
			auto cur = num_to_pos(i);
			cout<<cur.first<<" "<<cur.second<<"\n";
		}
		/*if(!a){
			flag = 1;
			break;
		}*/
	}
	return 0;
}
signed main(){
	//scanf("%d%d",&n,&m);
	n = 8,
	m = 8;
	init();
	bitset<300> mat;//黑板
	for(int i = 0; i < n*m; i++){
		mat[i] = 1;
	}
	//cout<<ans<<"\n";
	cout<<check(mat)<<endl;
	//step(mat);//仍需修改 
return 0;
}

猫史档案馆

【话题讨论】点灯游戏 | 数学好的请进

回复