lgblkj的个人博客分享 http://blog.sciencenet.cn/u/lgblkj

博文

“点灯游戏”类似问题的理论分析

已有 5874 次阅读 2013-11-4 11:53 |系统分类:科研笔记| 游戏

“点灯游戏”类似问题的理论分析

 

 0.简介

 

有一种很流行的益智游戏叫“点灯游戏”,这在类游戏中,一般是有个方阵的灯排布,初始时有些灯亮有些灯暗,玩家要通过一些按钮将其全部点亮,这些按钮的作用就是一次性使其控制的那几盏灯同时“取反”,所谓“取反”就是使其控制的那几盏灯中亮着的灯变暗,暗的灯变亮。由于,按钮与其控制的灯位置之间关系的多样性,这类益智游戏也是千变万化的,可以有多种设计方案。也正是由于按钮与灯不是一一对应,这种游戏的难度有时候可以很大,使玩家顾及这盏灯,忘了那盏灯。但是,这样的问题往往是可以从数学角度看得很清楚的。

对于这类点灯游戏,本文发展了一套理论,可以得到所有可解“点灯游戏”的解决方案。在这套理论中引入了一种新的代数规则,它有可能等价于抽象代数的某个分支,由于笔者对抽象代数不是很了解,推导过程中也就不硬将其归入抽象代数的某个分支了。

 

1.代数理论

 

在这套“点灯理论”中,定义一个数空间,其中只有两个元素0和1,表示为{0,1}。这两个元素与“点灯游戏”的对应规则是,0对应于灯暗或者按钮不按下,1对应灯亮或者按钮需要按下。在这个数空间中定义了加法运算,运算符号为“+”,并且满足交换律,其运算规则为,1+1=0,1+0=1,0+0=0 。并且定义了乘法运算,元算符号为“*”,可以用任意十进制的数字与元素1或者0 相乘,相乘结果只是相当于若干个元素相加,所以乘法运算只是一种连加的简写方式。这样,可以将这个数空间中的运算性质做如下总结:

 

1.a+b=b+a;
2.
                                                           (式中x为{ai}序列中“1”元素的个数);
3.a+b=a-b;
4.
$x*a=\begin{cases} a & \text{ if } x=odd \\ 0& \text{ if } x=even \end{cases}$
 
 
   

2.一个实例

 

如今,安卓系统下的软件五花八门,当然也少不了各种益智游戏了,本文就以笔者遇到的一个点灯游戏为例,应用上述点灯理论。虽然,各种点灯游戏都可以通过编程解决,但是很多算法都不是最优的。本文介绍的点灯游戏的规则为:有一个3*3的方阵灯泡,初始状态为有些亮着,有些暗着。有九个按钮,每个按钮上画有九盏灯,相对位置与方阵中一一对应,其中有些为亮着,有些暗着,亮着的部分为此按钮控制的那几盏灯对应位置的那几盏灯。

 

 

     如上图所示,左边为灯的面板,有些亮着,有些暗着,它收右边的按钮面板控制,例如右边的左上角的按钮按下去使得右边左上角的四盏灯亮的变暗,暗的变亮。那么,游戏任务就是组合这些按钮使得左边面板的等全部点亮。

 

首先,对上图中的小灯和按钮进行如图编号。

 

 

 

基于以上对小灯和按钮的标记,a为1代表小灯初始时刻是亮着的,a为0说明小灯初始时刻是暗着的。S为1说明此按钮应该按下,S为零说明此按钮不需要按下。那么此问题就变成了已经一组系数a,求解另一组系数S的问题了。可以如下建立方程组。

 

 

 

先让我们来看看这个线性方程组对应的矩阵形式,感受一下其美妙的对称性。

 

式中

 

 

这个方程组的解为:

 

 

利用第一部分的代数理论可以将以上按钮的解向量S化简,以便看出这个问题中的对称性。化简结果如下:

 

 

以上按钮向量S告诉我们,每一个按钮Sij是否需要按下完全取决于初始时刻小灯的亮暗情况,并且每个按钮对应固定的几个小灯,Sij可由这几个小灯的亮暗值之和求出。而根据第一部分的代数理论第二条,几个数的和完全取决于这几个数中“1”的个数,若有奇数个“1”则结果为1,偶数个“1”结果为零。对应在“点灯游戏”中就是,若按钮Sij对应的那几个小灯中,有奇数个亮着,那么这个按钮需要按下,偶数个亮着就不需要按下,对于按钮S00情况相反,因为S00表达式里除了小灯以外还多出一个“1”。以下举例说明,由对称性关系可知,按钮中只有三类按钮,这里选取S11,S12和S00作为例子。

对于S11,又以上S的解可知,S11=a00+a23+a33+a34,也就是S11这个按钮是否需要按下取决于a00, a23, a33,h和a34这四盏灯中的亮暗情况,这四盏灯中亮的个数为奇数,则需要按下,反之不需要。按如图距离不需要按下。

 

 

对于按钮S12,又以上解可得S12=a00+a11+a12+a22+a23+a41这就说明,a00,a11, a12, a22, a23,和a41这六盏灯中,亮的个数若为奇数则需要按下,反之不需要。

 

 

 

对于按钮S00,又以上解可得S12=a11+a22+a33+a44+a00+1这就说明,a00,a11, a22, a33,和a44这五盏灯中,亮的个数若为奇数则不需要按下,反之需要。

 

 

 

实际,操作中S00不需要这样判断,因为其他按钮的操作判断简单,而S00是一个全局取反的按钮,使九盏小灯全部取反。若我们先判断操作完其他按钮,所有小灯要么就是全亮,要么就是全暗了,这时候我们更容易判断是否需要按下S00按钮。

 

 

 

 

3.深层讨论

 

   以上已经成功地将第一部分的代数理论应用到“点灯游戏”中了,那么关于这个结论的操作性也许有人会问,由于每个按钮是否需要按下完全取决于初始时刻小灯的亮暗情况,那么是不是需要在一开始就记住这九盏小灯的亮暗情况呢?答案是不用的,这是因为这些按钮操作都是对易的,与次序无关。

   首先,假设根据以上条件需要按下S12按钮,因为S12按钮对应的几盏灯中亮灯个数为奇数。按下S12之后,S12对应的几盏小灯中的亮灯个数必然为偶数。这是因为可以将现在的这个状态看成是初始状态,由于这些操作是自身与自身互逆的,也就是说,连按两次S12等于什么都没做,站在这个初始时刻去判断S12是否需要按下得到的结论应该是不需要,所以这时候S12对应的小灯里面亮灯个数必然为偶数。

   再次,不同的按钮按下不会对其他按钮对应的小灯的亮灯个数的奇偶性造成改变。这是由于这些操作对易导致的,这里就不加以数学证明。通过尝试也会很快感受到这一神奇的现象。

于以上两条性质,在实际操作中并不需要一次性记清楚初始时刻小灯的亮暗状态,因为后续操作是相互独立的,一个按钮的按下并不会改变另一个按钮按下的必要性。这样,实际操作时我们只需要独立判断每个按钮是否需要按下,按下需要按下的再以得到的新的状态为初始状态来判断下一个按钮是否需要按下,这样继续判断下去,无需回头或重复。这样就解决了这个看似复杂的问题。

   本理论可以延伸至其他种类的点灯游戏和满足这种双态对易操作的一切系统,对于不同的问题只是所需要求解的线性方程组不一样,而核心思想完全一样。将本理论应用于类似于“点灯游戏”的物理或数学问题中,能够使这个问题的对称性本质显现出来,使问题变得简单明了。

 

 

 

 



http://blog.sciencenet.cn/blog-787628-738883.html

上一篇:关于悬浮弹簧的理论分析

2 柳林涛 李泳

该博文允许注册用户评论 请点击登录 评论 (3 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-4-13 06:21

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部