关灯游戏

来自计算思维百科
跳转至: 导航搜索
关灯游戏1.png

关灯游戏中有一块正方形面板,上面有行列数量相同的电灯,如果打开或关闭一个电灯,那么与之上下左右相邻的电灯状态也会同时改变,如果知道初始时哪些灯是点亮的,如何关闭所有的灯呢?

解决方案

关灯游戏是数学中线性方程组的一个应用,在计算机学科中,我们利用高斯消元求解线性方程组的方法求解它。我们只是简单介绍一下求解的思想,关于高斯消元算法的具体实现请参见相关词条-高斯消元算法。

主要思想:我们将电灯“亮”记为状态“1”,“暗”记为状态“0”,那么对于右上方四个电灯的面板来说, 将该状态下的面板记作关灯游戏2.png 。假设该状态就是初始状态,我们随意按电灯要将所有的电灯关闭,而无论我们按什么顺序去按电灯,一共四盏,所以只有4种方式。初始状态下,如果我们按第一盏,面板变为 关灯游戏3.png,按第二盏,面板变为关灯游戏4.png ,按第三盏,面板变为关灯游戏5.png,按第四盏,面板变为关灯游戏6.png。也就是说,我们要对初始面板状态关灯游戏7.png进行多次不同状态的累加最终得到面板状态为关灯游戏8.png。假设我们第一盏灯按a次,第一盏灯按b次,第三盏灯按c次,第三盏灯按d次就可以得到最终状态,那么数学描述如下:

关灯游戏9.png

这个式子就是一个有4个未知数的线性方程组

0+a×1+b×1+c×1+d×0=0

1+a×0+b×0+c×1+d×0=0

0+a×1+b×0+c×1+d×1=0

0+a×0+b×1+c×1+d×1=0

这样,我们利用高斯消元就能将该线性方程组未知数a,b,c,d解出来,这也就是我们应该怎样关闭所有电灯的方法。

可以体现的计算思维

关灯游戏的实现过程中,我们将面板抽象成矩阵,然后转化成一个求解线性方程组的数学问题,利用计算机求解,体现计算思维的抽象和转化特点。