月归档:七月 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个箱子的情形(注意本节的图和上一节的图左右反了)。 本关在线游戏链接 … 继续阅读

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