月归档:八月 2012

两个有推木桶元素的益智游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=660 简单说说最近玩的两个推箱子类益智游戏。我把这类游戏称为推箱子类真是恰如其分,因为大多都有推箱子元素。今天说得这两个当然都有推箱子元素。除此之外,还有不少类似的地方。首先就如标题所说的,还有推木桶,木桶和箱子不同的地方在于木桶只要推一下,就一直滚下去了,直到碰到障碍。另外,这两个游戏的画面中,关卡都是悬浮在背景上。 虽有类似的元素,但其他不同的元素给这两个游戏带来不同的特质。 一、Save the puppies 这是一个Android手机游戏,由德国的Handy Games出品。之前介绍的四只小猪的游戏《Aporkalypse》也是这个公司出品。和大多数Android游戏一样,有免费和收费版本。免费版地址是:https://play.google.com/store/apps/details?id=com.hg.savethepuppiesfree 《Save the puppies》的任务是引导主角解救关卡中被困的小狗。主角是一条1 x 3的大狗,能转弯。吃香肠能变长,吃剪刀变短。游戏还有另外三个非玩家配角:见到主角就跑的1×1小猫;趴在地上睡觉的1×4嗜睡狗,任何物品压在嗜睡狗尾巴上,它的头会抬起来让出一格通道;还有就是被拴在大石上的恶狗,见到小猫会拉动大石上前一步。这就是游戏的核心机制。利用这套规则,游戏提供了100个有趣的关卡。 和《Aporkalypse》,游戏是在一个固定的前45度俯视的视角的三维世界展开。我估计这两个游戏基于同一个引擎,当然后出的《Save the puppies》有不少改进的地方。 我玩的是免费版,有步数限制。虽然游戏中有不少能获取步数的设计,但是还是不太够用。到了最后二十关只能依靠游戏设定的一分钟送一步的机制来获取步数了。 关卡不算难,为了提供一定的挑战性,除了救出小狗外,每关都还有两个额外的可选任务:吃掉关卡中的骨头,还有尽可能用较少的步数。完成后面两个额外要求,才能获得三颗星的评价。 二、Professor Fizzwizzle 这款游戏有两部。分别是2005年出的《Professor Fizzwizzle》和2007年出的《Professor Fizzwizzle and the Molten Mystery》。游戏由加拿大温哥华的Gruddy Games 出品,Gruddy Games于2009年被基于美国西雅图的Big Fish Games收购了。 这两款游戏在Steam上有售,但在Big Fish Games网站上卖的更便宜些,所以我在Big Fish上买了第一部。 游戏是建立在一个侧视的2维世界,有重力。每一关都是要引导我们的主角教授同志走到出口。除了本文开头提到的推箱子、推木桶之外,还有磁铁,开关,弹床,滑轮升降机等等一些特色要素。关卡设计也还不错,是一款比较好的侧视视角的推箱子类游戏。 教授同志可以从关卡边缘掉入无尽深渊,这让我想起了前面博文介绍过的《Puzzle Moppet》。

发表在 游戏 | 留下评论

判断推箱子关卡是否有解的多项式空间的算法

作者:杨超 本文地址:http://sokoban.ws/blog/?p=630 之前写过一篇博文介绍了一系列具有递归关系和指数长度答案的推箱子关卡。本文给出判断推箱子关卡是否有解的多项式空间的算法。这两篇博文结合起来,可以对计算复杂性理论里面的PSPACE问题的概念有比较直观的理解。推箱子游戏是一个非常好的PSPACE问题的例子。 一、P, NP和PSPACE 先定义推箱子问题。本文中说的推箱子问题,是指如下的一个判断性的问题:给出一个推箱子关卡,这个关卡是否有解?注意这里只判断是否有解,也就是说只要回答“是“或“否“,如果回答“是“,也不需要给出一个具体可行的lurd答案。 判断一个推箱子关卡是否有解,是一个PSPACE完全(PSPACE-complete)问题。PSPACE-complete问题是计算复杂性理论里面的一个术语。PSPACE-complete 所讨论的是推箱子问题的空间复杂度。简单地说,空间就可以理解为计算机的内存。我们假设一个推箱子关卡宽度为w,高度为h,则我们称这个推箱子关卡的大小为n=w*h。显然,一个关卡越大,我们用程序去计算关卡是否可解时,需要的内存就越多。PSPACE-complete 有两层意思。第一层意思是推箱子问题存在多项式空间的算法,也就是说存在一个算法A,这个算法对大小为n的推箱子关卡,最多使用$ n^k $(k是某一个与关卡无关的常数)的大小的内存就能回答出这个关卡是否可解。当然,所用的时间没有限定。第二层意思是推箱子问题是所有多项式空间可解的问题里面最难的一类。PSPACE表示所有多项式空间可解问题的全体,PSPACE-complete是PSPACE 的一个子集,是里面最难的那些问题的全体。这里“最难“是有严格的数学定义的,在此我们直观地认为从空间复杂度考虑最难就可以了。 计算复杂性理论的完整的理论体系建立于20世纪的70年代(1970年代)。而推箱子最早被证明是PSPACE-complete问题是在上世纪90年代末。就像我们前面解释的那样,证明推箱子问题是PSPACE-complete问题有两个要点。一是要说明推箱子是多项式空间可解的。二就是说明推箱子问题是多项式可空间可解问题里面最难的。其中第一点比较容易,本文的目的是给出一个判断推箱子关卡是否有解的多项式空间的算法。注意,这个算法只是理论上有意义,不适宜用来实际求解。在实践中,大多推箱子求解程序使用大量的内存,往往是随推箱子关卡大小呈指数增长。 在具体讨论算法之前,先说些题外话。前些年,媒体曾热炒过“庞加莱猜想”,这是Clay数学研究所(Clay Mathematics Institute)于2000年悬赏100万美元的七个尚未解决的数学问题之一,每个100万美元。其中“庞加莱猜想”最近已经被解决了。2010年,这个百万大奖授予俄罗斯数学家佩雷尔曼(Grigoriy Perelman)。但佩雷尔曼拒绝接受这个奖项和奖金。 在其他六个尚未解决的价值百万美元的问题中,有一个是属于理论计算机科学里面的问题,更具体地说是关于计算复杂性理论的问题:即 P vs NP问题。 我们用P来表示所有能用多项式时间(注意是时间,不是空间,区别于PSPACE)算法解决的判断问题全体。用NP表示所有所有能用“非确定性(Non-deterministic)”多项式时间算法的判断问题全体。可以证明,任何一个P问题都一定是NP问题,也就是说P是NP的子集。但是现在尚未确定的是,究竟P是NP的真子集,还是P=NP?这就是所谓的P vs NP问题,七个百万问题之一。 P和 NP都是从时间复杂度上考虑的,而PSPACE是从空间复杂度上考虑的。大家很自然会问,有没有NPSPACE问题?也就是说是否有“非确定性“多项式空间算法问题的全体呢?有的。但是作为著名的Savitch定理的一个推论,可以证明PSPACE=NPSPACE。即两者实际上是同一个集合,因此一般只提PSPACE。 Savitch定理是由Walter Savitch 于1970年证明的。我搜索了一下他的主页,发现他主页(http://cseweb.ucsd.edu/users/savitch/) 上照片似乎是在中国照的,大家可以去看看。这里提到Savitch定理的一个重要原因是下面介绍的算法是基于Savitch定理(参看[1])的证明设计的。 (图片来自Walter Savitch的个人主页) 可以证明,凡NP问题都是PSPACE问题,NP是PSPACE的子集。那么究竟NP是PSPACE的真子集,还是NP=PSPACE?这也是一个悬而未决的问题。多数数学家和理论计算机学家都倾向于认为P,NP和PSPACE三者,前一个都是后一个的真子集,也就是可用下图示意: 二、判断推箱子关卡是否有解的多项式空间的算法 下面开始讨论算法。 我们知道一个大小为n的关卡,实际有效的格子实际上是小于n的,但我们不妨设就是n。每个格子要么是箱子,要么是人,要么什么也没有,所以所能形成的不同的局面不会超过$ 3^n $种(事实上$ 3^n $高估了所有可能的局面数,但从数量级上是基本一致的),其中有一个局面是初始局面,有一个是目标局面。所以,如果一个关卡是可解的,一定在$ … 继续阅读

发表在 推箱子, 数学 | 留下评论

Chrome 扩展: Sokoban.WS Tools

作者:杨超 本文地址:http://sokoban.ws/blog/?p=618 昨天的博文写了我是如何编写Firefox的扩展Sokoban.WS Tools的。在写的过程中,我注意到相似图片搜索TinEye网站不光是有Firefox的扩展,还同时有Chrome、Opera等其他浏览器的扩展。我就装了TinEye的Chrome扩展,和它的Firefox扩展一样,实现同样的功能:在图片上方点击右键,通过右键菜单快捷搜索。于是我就琢磨着如何把Firefox上的推箱子扩展也移植到Chrome浏览器上。 为了实现这个目的,还是浏览官方的技术文档和通过著名的编程技术问答社区StackOverflow来学习Chrome扩展的编写方法。经过一番了解,发现Chrome的扩展也是用JavaScript来编写的,但是具体实现方案又和Firefox的扩展不一样。首先,Firefox是用特有的XUL格式来描述扩展的界面的。但是Chrome没有专用的界面描述语言,而是和网页一样,用HTML5来描述。比如,选项对话框在Chrome的扩展里面就是一个本地的网页在新标签中打开,而不像Firefox那样是一个弹出的对话框,和网页有明显区别。而右键菜单项的更改则是在JavaScript代码中调用Chrome提供的API函数来实现。其次,Firefox扩展的JavaScript代码可以同时和扩展的界面控件以及当前浏览的网页中的各种要素对话。而Chrome扩展的JavaScript代码分成background和content两类。Background代码只和扩展自身的对象打交道,如右键菜单、本地选项页面、扩展在地址栏上的图标等等。要获取当前浏览的页面的内容,只能由Content类代码完成。Background和Content两类代码是相对独立的,要完成有用的扩展功能,两者必须交流。于是Chrome就设计了一种Message机制,通过在Backgournd 和Content代码之间请求和回应Message来让Background代码间接地获取当前浏览的页面的信息。主要就是这两点不同。这导致的结果就是Firefox扩展的表现力更强,而Chrome扩展被有些人戏称为就是本地的HTML+JavaScript应用,和浏览器的结合度相对较弱。 不管如何,要实现我想要的推箱子扩展功能,Chrome的扩展技术还是可以办到的。于是又用了大半天时间,完成了Chrome上的扩展Sokoban.WS Tools。因为和Firefox上的扩展是完成一样的功能,核心的逻辑(即把XSB格式关卡转换成SokoPlayer HTML5能识别的URL参数的几十行JavaScript代码)是一样的,这部分代码可以直接重用,所以我给扩展起了同样的名字:Sokoban.WS Tools。下面是Chrome上该扩展的截图: 做完了Chrome的扩展之后,很自然的就想能否再移植到其他浏览器上。所以我就继续考察了另外一个浏览器Opera的扩展。考察方法还是先安装相似图片搜索工具TinEye的Opera扩展。令我颇感意外的是,TinEye的Opera扩展用了一种不太好的方法来实现。右键菜单不再使用了。取而代之的是在Opera地址栏最右方出现一个TinEye的图标,点击该图标,会弹出一个悬浮框显示当前页面的所有图片,再点击想要搜索的图片进行搜索。这种方法相对右键菜单来说,明显是一种较差的方案。所以我有理由相信,Opera扩展所能提供的功能较弱,扩展是无法修改浏览器的右键菜单的。于是我就没有继续研究了,浏览器扩展的探索大概到此也告一段落了。

发表在 推箱子, 编程 | 留下评论

Firefox 扩展 Sokoban.WS Tools

作者:杨超 本文地址:http://sokoban.ws/blog/?p=609 我大概是从2010年春起使用 Firefox 作为我的常用浏览器。Firefox有很多性能都比IE强。比如地址栏所支持的URL长度至少8000字符以上,远远大于IE的大概2000字符的限制。Firefox 对HTML5的支持较好,我编写的网页程序SokoPlayer HTML5有些功能就只能在Firefox下使用。后来又发现Firefox有很多好用的扩展(extensions/add-ons)。我必装的扩展主要有:显示网站服务器所在国家等信息的Flagfox,显示网站全球排名的Alexa Sparky,网页截图工具Abduction!,等等。 前些天,我使用TinEye的相似图片搜索工具时,发现他们也提供一个Firefox扩展。安装该扩展后可以在任何一个网站图片直接点击右键,选择Search Image on TinEye直接搜索,十分方便。于是,我产生了给推箱子写一个插件的想法。推箱子迷们常常在论坛(如魔方吧推箱子版)和邮件中交流和分享新的关卡。大家交流时都是用标准的XSB文本关卡格式,这种格式被所有主要的推箱子软件支持,只要复制粘贴就可以了。我编写的在线推箱子程序SokoPlayer HTML5 也支持读入这种格式。即便如此,还是需要点击好几下鼠标才能把网页中的XSB格式关卡读入程序。如果能在选中XSB文本后直接用右键菜单把关卡载入在线的SokoPlayer HTML5程序,就可以节省好几步操作。而且SokoPlayer HTML5已经具备了从URL中读入关卡信息的功能,剩下的就看Firefox扩展如何编写了。 于是我花了些时间查阅了网上的Firefox扩展的技术文档和快速入门。我发现Firefox的扩展从技术上并不复杂,原来也是用 JavaScript编写的。简单地说,Firefox扩展主要由两部分构成。第一部分是扩展的界面。Firefox的扩展可以以右键菜单,地址栏,状态栏(扩展栏)或者选项对话框等标准形式出现。扩展可以采取其中的一个或者多个作为界面,而界面是用基于XML语言的XUL格式来描述的。第二部分就是扩展的代码。用户在通过上述各种形式的界面调用扩展时,扩展如何处理。这一部分就是用 JavaScript 语言来编写了。这和HTML+JavaScript的工作原理类似。最后,把这两部分加上一些额外的描述文件一起压缩成一个ZIP文件,把文件后缀由.zip改为.xpi,一个扩展就制作完成了。这就是Firefox扩展的原理。 知道了Firefox扩展的基本框架,我再查阅了Copy As Plain Text, JiaThis, TinEye等扩展的代码。在这基础上,我用了大概一天多的时间,完成了一个简单的Firefox插件,实现了我前面提到的想法:在页面中选中XSB关卡,然后调用右键菜单在新标签中打开SokoPlayer HTML5在线程序,并直接载入XSB关卡到程序中去。我把扩展命名为 Sokoban.WS Tools,虽然目前只有一个功能,但以后有新功能的想法还可以继续添加。 这个扩展我已经提交到Mozilla Add-on for Firefox了,可以从以下地址安装:https://addons.mozilla.org/en-US/firefox/addon/sokobanws-tools/ 下面分别是扩展使用时和选项对话框的截图。 右键菜单: 选项对话框:

发表在 推箱子, 编程 | 留下评论

Berusky 系列游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=596 在介绍了来自捷克的《Crystal Cave》和《Fish Fillets》两个系列游戏之后,今天再次推荐一个来自捷克的系列益智游戏《Berusky》。在我介绍过的为数不多的益智游戏中,就有三个系列是来自捷克,不知道是巧合,还是捷克人民比较热爱益智类游戏。 Berusky 有两部作品,分别是1999年正式发布的《Berusky》和2004年发行的《Berusky II》。Berusky 是传统的俯视2D,而 Berusky II是真正的3D游戏。虽然两部的维数不同,但共享一些共同的元素。比如,每关都是要引导1到5个小臭虫走到出口;都有一种能爆炸的箱子,若把爆炸性的箱子推向一个普通箱子,两者就会炸没了,但反过来把一个普通箱子推向一个爆炸性箱子,则不会起反应;可以在关卡中捡到锄头,锄头可以敲碎泥块;等等。 两部作品比较,第一部2D的相对比较平庸,存档还采取密码这种繁琐的方式。第一部如今已经完全开源,并移植到Linux等平台了。 第二部则亮点较多。首先3D的益智游戏就不多见,之前我玩过的只有《Puzzle Moppet》算是比较好的。Berusky II的3D呈现和渲染还算不错,和Puzzle Moppet基本持平或者稍微差一些,视角转换的操作性不如Puzzle Moppet。至于关卡设计,则比较出色。除了Tutorial关卡集是为了介绍游戏中的各种元素比较容易之外,正式的关卡都相当有难度。我颇费功夫才过了两个正式关。游戏基本达到用较少的元素设计出较难和有一定迷惑性的关卡。稍有遗憾的是我玩的Demo试玩版只有捷克文的界面。还好但对益智类游戏来说,问题不算太大。第二部也在北美发行英文版叫《Bugs Escape》,但毕竟益智类游戏有点市场不太大,发行的渠道似乎也不是什么大的发行商,所以这个2004年有点年头游戏我今天才好好地体会了一把。 同是3D推箱子类益智游戏,Puzzle Moppet 和 Berusky II 的规则有些有意思的不同点。如 Berusky II 不能从台阶的边缘掉到下一层去,Berusky II 的升降机的规则也和 Puzzle Moppet 不同,除了升降机外Berusky II 还有斜坡,等等。 最后还是贴两张截图。  

发表在 游戏 | 留下评论

DROD 系列游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=571 DROD 是 Deadly Rooms of Death 的缩写,它包含了一系列游戏。目前主要有4款,姑且称之为1,2,3,4这四代。这系列游戏被Ed Pegg Jr.称为是最好的益智游戏。DROD的确是一款非常好的益智游戏,但说是最好的恐怕评价过高。我之前介绍的《Toki Tori》和《Fish Fillets II》两款游戏都比《DROD》更好一些。 DROD 1代由Erik Hermansen开发,1997年由Webfoot Technologies公司发行。后来Erik让Webfoot把DROD 1开源,并成立独立的工作室继续维护。这个版本称为《DROD 1: Architects’ Edition》。Erik 的Caravel Games工作室重新编写了DROD游戏引擎,分别于2005年、2007年和2012年开发了DROD的续作《DROD 2: Journey to Rooted Hold》、《DROD 3: The City Beneath》和《DROD 4:Gunthro and the Epic Blunder》。其中还出了DROD的RPG版本,因为不是益智类,这里就不介绍了。1代也被移植到新的引擎来,称为《DROD: King Dugan’s … 继续阅读

发表在 游戏 | 留下评论

Fish Fillets 系列游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=550 前几天介绍了一个源自捷克的制作相当精良的游戏《Crystal Cave》。今天再介绍一个同样来自捷克的推箱子类益智游戏系列《Fish Fillets》。Fish Fillets 由 ALTAR 公司1998年制作,四年后2002年变为免费软件,2004年以GPL协议把源代码也公开了。于是有爱好者便用SDL库把这款游戏从Windows系统移植到 Linux, Mac OS X等其它操作系统。这个移植版名字叫 Fish Fillets Next Generation (Fish Fillets NG),以区别原作,关卡除了原来的之外,还新制作了10关。 2007年,ALTAR公司出了续作 Fish Fillets II,也是只在Windows平台发行。Fish Fillets NG 版本我之前就玩过10来关,感觉非常不错。于是今天在 Steam 上购买了 Fish Fillets II,也是玩了10多关后觉得物有所值,值得推荐。 游戏有下面几大特色。首先,图像和声音效果的非常好,还有真人语音台词,增加了游戏的趣味性。在益智类游戏里面,图像音效算是顶级的水准了。其次,作为经典的益智类游戏,规则有新意。游戏是由两条鱼合作过关。一大一小的两天鱼通关移动水中的物品开辟道路,走到出口过关。金属管类物体只有大鱼才有足够的力气移动。物品有各种各样不规则形状,包括凹的多边形,这时同类游戏少见的。一二两代游戏中,鱼能够移动物体的规则稍微不太一样,简单地说就是二代规则更宽松一些。最后,就是关卡的设计非常巧妙,有的相当难,具有一定隐蔽性和误导性,增大了过关后的成就感。可以想象关卡是经过反复推敲和测试的。 下面放两张截图,分别来自 Fish Fillets NG 和 Fish Fillets … 继续阅读

发表在 游戏 | 留下评论

三款Flash益智小游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=534 在我的博客第一篇文章介绍十款优秀的益智游戏里面,十款游戏有六款是Flash游戏。在那之后的一年,又发现了几款相当不错的基于Flash技术的益智游戏,合起来介绍一下。这几款游戏都可以在Flash游戏网站Kongregate在线玩。我闲时有时会登录Kongregate查看Puzzle类的最新更新,被归入Puzzle类的游戏五花八门,平均可能二十个才有一个是我所说的推箱子类益智游戏,其中制作精良的就更少了,所以一年下来,也就发现这个几个。当然也不排除我有时太忙错过了一些优秀的。 一、Monster Bark 地址:http://www.kongregate.com/games/ArmorGames/monster-bark 作者:Joey Betz来自美国加州,在另一个主要的Flash游戏网站Armor Games任职。 游戏特点:五个人物合作过关。五个角色各有特点,1号跑得快,能穿过小洞;2号能尖叫吓呆怪物;3号能推箱子和跳过地上的坑;4号力气大,能踩动开关,还能打碎大石;5号高瘦,能穿过狭缝,并且能修复电线。五人协作,收集齐散落在关卡中的物品过关。 二、Frost 地址:http://www.kongregate.com/games/Qaziro/frost 游戏特点:游戏规则比较简单,是克隆了日本92年的一个NES游戏叫Fire ‘n Ice。游戏中只有火与冰两个元素,需要游戏的主角利用冰把所有的火灭了过关。主角能走上一级台阶,推冰块,并且有在下前方生成或消去冰块的技能。 三、Ninja Mushroom 地址:http://www.kongregate.com/games/dennatolich/ninja-mushroom 游戏特点:除了主角之外,游戏中的物品能自主左右移动,或自由下落。这一点和我博文两款无主角的益智游戏里面介绍的《花之难题》有点类似。游戏的目的是为我们的主角蘑菇搭建一条到终点金色树桩的路。其它的六种元素是: 泥块:最普通的要素了,可左右移动自由下落 石头:不能左右移动,但可自由下落 普通树桩:完全不能动 冰块:自由下落和被砸会碎,可左右移动自由下落 栅栏:蘑菇不能站在上面,可左右移动自由下落 炸弹:自由下落或被砸会爆炸,炸掉周围8个格子,可左右移动自由下落

发表在 游戏 | 留下评论

Boulder Dash 和 Crystal Cave

作者:杨超 本文地址:http://sokoban.ws/blog/?p=510 本文主要介绍一款具有 Boulder Dash 特征的纯逻辑推箱子类游戏 Crystal Cave。 Boulder Dash 是由 Peter Liepa 和 Chris Gray 在1983年共同设计编写,1984年在 Atari 800 上发行。根据2005年对 Peter Liepa 的采访[1],Boulder Dash 的设计受到稍早些的日本游戏 The Pit 的影响。Boulder Dash 的各种克隆版本很多,比较有名的有 Rocks’n’Diamonds。网络上 Boulder Dash 的爱好者网站也很多,如 bd-fans,网站上有各种主要克隆版本的详细资料。若你不太清楚 Boulder Dash 的游戏规则,试试这个比较忠实于原作的 JavaScript 在线版本。 … 继续阅读

发表在 游戏 | 留下评论

图上的熄灯游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=487 一、熄灯游戏 熄灯通常在n*n的格子上玩,每个格子是一盏灯,点击每个格子可以改变格子本身及其上下左右相邻格子的灯的状态。游戏要求把灯从全亮变到全部熄灭。关于熄灯游戏,老杰有一篇博文《熄灯游戏》对此作了非常好的介绍,他的网站还有网页版的熄灯游戏可以在线玩。对熄灯游戏不太熟悉的朋友可以在看老杰的博文之后再继续往下看。 二、推广 老杰的博文提到,对任意的n,初始状态为全亮的熄灯游戏都有解,即可以被全部熄灭。老杰的博文最后还提到熄灯游戏有六边形,3D等形式的推广。 更一般地,熄灯游戏可以推广到任意的图上面。这里所讲的图是若干个顶点和某些顶点对之间的连边构成。如下就是所谓的 Petersen 图,它由10个顶点和15条边构成。熄灯游戏的规则可以不作任何改变应用到一般图上,点击一个顶点,改变该顶点以及和该顶点直接相邻的顶点的状态。 图片来自 Wikipedia, CC-BY-SA协议 并且有趣的是,任意的一个图上以全亮为初始状态的熄灯游戏都有解。这个结论可以用线性代数和线性方程组的求解理论作出证明。但是这个证明需要系统地学习过线性代数才能比较好地理解,一般大学理工科的学生才会学习线性代数课程。下一节,我准备介绍一个纯粹的图论证明,这个证明由 Henrik Eriksson 等人2001年发表在《Advances of Applied Mathematics》杂志上,全文可以在 arXiv 下载。这个证明只用到了数学归纳法,有一定数学修养的高中生都完全有可能自己独立证明出来。这个证明简洁漂亮,很有可能被许多人独立地发现过。 三、证明 本节用数学归纳法证明:任意一个图上以全亮为初始状态的熄灯游戏有解。 对图的顶点个数 n 归纳。n=1 的时候显然有解。 下面进行归纳,假设对n-1个的点的图结论都成立,我们证明n个顶点的图G结论也成立。设这n个顶点的标号为1,2,…,n。为了用归纳假设,我们可以作这样的考虑,把标号为i的顶点删掉(当然这时和顶点i关联的那些边也同时删掉了),那么剩下的还是一个图,但只有n-1个顶点了。根据归纳假设,剩下的这个图是有解的,取定一个解称之为关于i的解,因为图是删掉顶点i得到的。 如果对某个i,关于i的解也是原来n个顶点的图G的解,那么结论对原图G也成立了。所以下面我们只需要考虑这样一种情况:对所有的顶点i,关于i的解都不是原图G的解。具体地说,每个关于i的解作用在原图G上的效果就是顶点i还亮着,其余的顶点都灭了。在这样一种情况下,我们下面分甲乙两种小情况考虑。 甲、n是偶数。此时我们可以把关于1的解,关于2的解,…直到关于n的解依次都在原图G上执行一次。我们分析一下执行的最终效果。对顶点i来说,关于i的解使得顶点i的状态保持不变,而其余n-1个解使顶点i改变状态。因为n是偶数,n-1是奇数,合成的效果就是顶点i的状态改变了奇数次,由亮变为灭了。每个顶点都是这样,所以这n个迭加在一起就是原图G的解了。 乙、n是奇数。这时刚才的方法不管用了,要另辟蹊径。我们取图G中一个度数为偶数的顶点,不妨设为顶点1。本段余下解释为何存在这样一个顶点,熟悉图论的朋友可以跳过直接看下一段。所谓顶点的度数,就是和这个顶点相邻的其它顶点的个数,也就是和这个顶点关联的边的条数,如前面的 Petersen 图每个顶点的度数都是3。一个图的所有顶点的度数加起来一定是偶数,这时因为在计算度数的时候,图的每一条边都会被两个不同的顶点计算了一次,共被计算了两次,于是所有顶点的度数和是边数的两倍,为偶数。还是以刚才的 Petersen 图为例,度数和为30,是边数15的两倍。因为我们的图G的顶点个数n是奇数,若所有顶点度数都是奇数,那么所有顶点的度数和是奇数个奇数相加,还是奇数,这不可能。 把上面取定的顶点1和它的全部邻点构成的集合称为A,那么A一共有奇数个顶点。其余的顶点全体是集合B,且B有偶数个顶点。对原图G,我们执行以下操作,点击一下顶点1,那么A中的点全灭了,B中的点任然保持亮着。之后再对B里面的每个顶点j,执行关于j的解。这里一共有偶数个解,所以A中的点改变状态偶数次,还是灭的状态;B中的点改变奇数次,也由亮变成灭了。于是我们得到原图G的解了。 四、小结 上述证明没有用什么高深的数学,非常简单。但是若是要找出一个具体的解法,还是用线性代数的方法或者结合其它技巧要快一些。老杰的博文提到有人给出 5000*5000 的熄灯问题的解。这相当于一个 … 继续阅读

发表在 数学, 游戏 | 留下评论