点灯游戏,又称变色方块,是一种规则简单的游戏,有一N行N列的灯,开始时全部是灭的,当你点击其中一盏灯时他的上下左右(若存在的话)状态全部改变,将全部的灯点亮即为胜利。
来自:http://yanhaijing.com/inverter/当N相对较小的时候还比较好解,然而当N较大时就无从下手了。是否有一种方法,无论N多大都能解呢?我们可以观察发现:当点击一个格子的次数为偶数时,棋盘状态一样,奇数次时同理。
并且,点击格子的先后次序并不影响最终棋盘的状态,先点击(1,1)后(2,1)和先点击(2,1)后(1,1)结果是一样的。
也就是说,每个格子只需两种状态便可描述整个棋盘状态,游戏的解至多可在个格子状态中找到。并且,由于对称轴和对称中心的存在,还可在更少的格子状态中找到解。
2*2格子的所有状态(对称的被截去),红色勾中格子点击了奇数次那么还有没有别的方法呢?下面将介绍一种使用线性方程组解出答案的方法。
上面提出格子只需两种状态描述,而每个格子的亮暗也可由来描述。找出格子点击数与翻转数之间的关系是解决问题的关键。
以2*2格子为例,共4格,其中格子i翻转次数:,与格子i点击次数:可以由以下方程组确定:
而我们的目标就是找到一组使得都为奇数,这里为了方便取,便得到,即四个格子各点一次。
根据之前奇偶次的讨论应有:和
之后可以得出更一般的形式:
其中为点击翻转矩阵,为翻转次数向量,为点击次数向量,根据一般规则,全为1,是我们需要求的向量。以下展示部分矩阵:
尽管在上面给出的一般形式中有同余符号,但我们也可以当作一般的处理,无非是求逆,去分母,模2。然而,,解可能不只一个,或者没有解,求解最好还是用高斯法。
最后总结一下如何解点灯游戏:
根据要求设定翻转向量
根据点击与翻转的关系设定点击翻转矩阵
使用高斯法求出的一个解,去分母,模2
使用以上方法可以解决所有类似问题,包括一些点灯游戏的变种,如形状改变,初始条件改变下的点灯游戏。