关灯游戏 Lights out (一)(极速求解)

关灯游戏(Lights 出)

      关灯游戏是Tiger 电子产品在1995发表了每一电视游戏。,Parker 兄弟的们在上世纪70年头发表了比拟的3×3游戏。, Vulcan 电子产品在1983也发生了比拟的游戏。,名字是XL—25。。

      眼前这款游戏的中文名很杂乱,网上可见“接线台灯游戏”、中断游戏、“开灯游戏”、中断游戏、点亮游戏、灯部署兵力游戏、楼层游戏,即使它的意义是两者都的。,而是为了名字决不一致。,触犯学术研究和检索。在维基百科(游戏),这款游戏的英文名称为:“Lights
Out”,可翻译家为“关灯游戏”。
关灯游戏分类特别的复杂,在m×n部署兵力中。,有几盏灯亮着。,点击任何的灯(不拘灯是开启不狂暴的完全关闭),都可以订购。,继灯和灯毗邻的。、下、左、好的的五盏灯将与本人相反。,即,光的消逝。,绝迹获得利益或财富极度的愉快地(鉴于修整的独特性),点击侧灯。,仅有的四元组灯一齐变。;点击困境上的灯。,仅有的三个灯一齐变。。

      游戏的决意是:经过击中灯部署兵力上的少量的灯。,将放入水中急速冷却灯部署兵力上的持有违禁物灯。。

      看一眼wiki的游戏详细规划。:

      前文是每一5×5平方灯部署兵力。,初始公务的正好左上角的当前一亮。;率先点击右下角灯。,右下角的三盏灯都亮了。;次要的次点击右下角,次要的个灯在斜边上。,最末每一举例显示了成功实现的事。,竞赛还没完毕。。

      关灯游戏分类即使复杂,而是竞赛很难。。因而好多猿想用电脑来处理它们。。习俗的处理方法是线性代数。,这是若干算学。。

      线性代数的优点是多方面的。,它不只可以处理M*N恣意部署兵力灯部署兵力。,它还可以处理灯部署兵力的恣意初始公务的。,这是个扭。。不外,线性代数的缺陷是不言而喻的。,指定遗传密码比得上复杂。,工夫错综复杂的状态也没取消法令。,当灯的数量大时,在有限性的工夫内很难求解。。
线性代数解决的规律,互联网网络先前进行。,缺少的这边。。这边,我找到了每一感觉最敏锐的地方算法。,它必要不到一秒钟的工夫来处理511×511光部署兵力。,高速极快!该算法特别的复杂。,只需点击还没有翻开的灯。,无不找到处理办法。。仍然,这种方法的缺陷是不言而喻的。,难以忍受的处理任何的部署兵力成绩等级。。

    指定遗传密码列举如下(C/C):

#include  /*关灯游戏求解指定遗传密码(只求解初始公务的全亮灯阵)*/
#define M 15       M本利之和灯部署兵力的数量。
#define N 31       n本利之和灯部署兵力的数量。
int 主(空)
{/*M、n值不得已是1。, 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, 191, 255, 383, 511…摆放餐具分类
	int a[M+2][N+2]={0},b[M+2][N+2]={0},i,j,k=1;
	while (k)
	{
倾向于(i=0;  i)<=M;)
			for(j=0;++j<=N;)
				if(!a[i][j])b[i][j]^=1,a[i][j]^=1,a[i][j+1]^=1,a[i][j-1]^=1,a[i+1][j]^=1,a[i-1][j]^=1;
		for(i=k=0;++i<=M;)
			for(j=0;++j<=N;)if(!a[i][j])k=1;
	}
	for(i=0;++i<=M;printf("\n"))
		for(j=0;++j<=N;)printf("%2d",b[i][j]);
	return 0;
}

像,装束m=n=11。,次出口是:

      该设计图的处理设计图是用亮度的设定初值来处理光部署兵力。,方灯部署兵力的次可以赢得处理。:

      1, 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287...
为了序列的通式是:A(2n) = 2*2^n - 1,a(2n+1) = 3*2^n - 1
每一正方形灯部署兵力,使臻于完善多个列的次。,可以处理。,旁白,4阶也可以处理。。

      论圆整数序列线大全()网站,号码已被编号。:A052955
特派网站:

     
search?q=7%2C11%2C15%2C23%2C31%2C47%2C63%2C95%2C127%2C191%2C255%2C383%2C511+&sort=number&language=&go=Search
是你这么说的嘛!次也可以处理少量的矩形光部署兵力。,对矩形的边沿家用电器以下断言。:
1、当m本利之和1时,n值本利之和上序列中恣意数量的矩阵可以被求解。;
2、当m和n经过的相干是拥护者分类值时,可以处理M*N矩阵成绩。:

M值 1 3 7 15 31 63 127 255 ...
N值 3 7 15 31 63 127 255 511 ...

      对是你这么说的嘛!次的评论:

      优点:次复杂,高速极快

       缺陷:可是处理特别规范矩阵。,功能有限性。       

no comments

Leave me comment