月归档:七月 2012

一系列具有递归关系和指数长度答案的推箱子关卡

作者:杨超 本文地址:http://sokoban.ws/blog/?p=430 一 推箱子的其中一个很重要的魅力来源于推箱子求解问题在计算复杂性理论里是一个 PSPACE 完全问题。在这里不对什么是 PSPACE 完全问题作出解释,但是推箱子的一部分美妙之处可以认为正是来源于它的计算复杂度达到了 PSPACE 完全问题的级别。具体表现就是可以设计出很多不同模式的关卡,而且我们目前所涉及到的模式只是一小部分,还有很广阔的空间等待我们去探索。另外一个表现就是存在一系列具有指数长度答案(相对与关卡的大小)的关卡,这一类关卡就是推箱子关卡众多模式里面非常有趣的一类,也是本文要讨论的对象。 二 2009年6月8日,我曾在魔方吧论坛发贴子介绍了一类指数长度答案的关卡。无独有偶,约一个月后的2009年7月5日,Matrix67的一片博客文章也介绍了这一关卡。我的贴子和 Matrix67 的博文介绍的关卡都是基于2000年国外的一个关于推箱子问题的解答。 对这个关卡的具体分析这里就不再重复了,简单的说它就是由一个个的“房间”构成,上图是三个房间的情况。要过关,最左侧一个房间要进入2次,但要进入左一房间1次,就要进入左二房间2次,所以左二房间一共要进入4次。同理,左三房间就要进入8次。一般的,若有n个房间的话,第n个要进入2^n次,于是答案长度便成指数增长了。 这个关卡设计巧妙,让人感受到推箱子的美。下面我们要介绍一个更美的更简洁紧凑,但同样也是具有指数长度的答案的系列关卡。 三 这个更漂亮的系列关卡也是在推箱子玩家里面流传了很长时间了,有很多变化形式,其中最经典的可能是如下图所示。 这是 Aymeric du Peloux 2001年设计的 Picokosmos 第17关。David Holland 在2002年曾分析过这个关卡。Dries De Clercq 在这个基础上作了名为 Fibo 系列的变形关卡。上图所示的经典形式不只是一个关卡,而是一系列关卡,关卡可以纵向任意伸长(同时箱子也增加),只要保持箱子总数是偶数个就行了(奇数的时候关卡无解)。若用n表示箱子的数目,随着n增大,答案步数以n的指数函数增长。 没有玩过这一关的朋友可以点击此链接在线玩。先提前警告,虽然只有8个箱子,要解出来不太容易。 我是2009年在魔方吧发了前面提到的贴子之后,才注意到这个关卡,当时没有看到 David Holland 的分析文章,独立地研究了这一系列关卡的步数。下一节将简要的介绍一下我的计算方法。 四 上一节提到,这一系列关卡只对偶数个箱子有解。为了便于建立递推关系,我对箱子位置作了以下微妙调整,使得对奇数也有效。主要有两处改动:一是最下方一个箱子连同目标移动了一格;二是最上方一侧的箱子移下一格(哪一侧由奇偶性确定)。如下面所示,分别是4到8个箱子的情形(注意本节的图和上一节的图左右反了)。 本关在线游戏链接 … 继续阅读

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

推箱子软件简史

作者:杨超 本文地址:http://sokoban.ws/blog/?p=384 三年前我在魔方吧论坛发过《推箱子简史》的贴子。之后我又千方百计的尝试运行了更多的推箱子软件,涉及的平台包括 Linux 和 Mac 系统、功能手机、智能手机和数字电视机顶盒等等,所以我打算重新梳理一下推箱子的历史,主要着重在软件的发展。 一、源于日本 1981春,今林宏行编写出世界上第一个推箱子程序“仓库番”,并于1982年商业发行《仓库番》[1]。这个版本有20关,其中只有前10关是标准的推箱子关卡[2]。后来84年发行《仓库番2》,89和91年分别发行《仓库番Perfect》和《仓库番Revenge》。日本国内发行的各种版本很多,但是有国际影响的主要是这几款,因为被移植到其他国家了。 推箱子诞生在个人电脑迅猛发展的初期,最初的《仓库番》是运行在 NEC PC-8801系统。 二、传遍世界 推箱子最早是由 Spectrum Holobyte 公司获得授权把“仓库番”移植到 DOS 平台在欧美地区发行。Spectrum Holobyte 发行的名为《Soko-Ban》的软件主要基于日本的《仓库番2》,有50关。这款软件在美国的发行面市时间估计在1988年,因为有两本杂志,《Computer Gaming World》和《Dragon》,都是在这一年介绍了《Soko-Ban》[3,4]。 而最早把推箱子介绍到中国的,应该是台湾的大宇公司了。很多老推箱子迷都是最先接触到大宇1990年发行的 DOS 版《仓库世家精彩篇》。这是一款带颜色的游戏,就是过几关出一张照片那种。后来95年大宇又正式代理发行了《仓库番之史上完美篇》和《仓库番之玩家复仇篇》[5]。 三、自由时代 最初的推箱子游戏主要以游戏公司商业发行推广的形式出现。但最迟从1992年起,推箱子软件逐渐地由个人开发的自由软件、共享软件和免费软件等占主导地位。主要原因我想有这么几个:推箱子规则简单但又让人上瘾,个人程序员有能力又有强烈的愿望编写自己的推箱子程序;而游戏公司则更在乎开发和发行大型的更能赚钱游戏。 独立开发者们基本形成了一个跨越推箱子软件的较弱的标准:xsb 关卡格式和 lurd 答案格式,有利于推箱子的交流和发展。也是这些独立开发者们把推箱子软件的功能发展到极致。 这一时期比较有影响的推箱子软件有以下一些,这些程序大都可以追溯到2000年左右或更早。 Unix/Linux 平台 XSokoban: Andrew C. Myers 编写的 … 继续阅读

发表在 推箱子 | 留下评论