分类目录归档：推箱子

  作者：杨超 本文地址：http://sokoban.ws/blog/?p=3757 量子计算机常被大众媒体描述得十分神奇，甚至有科学家也添油加醋，如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗？我在读了David Deutsch的书后，对此问题颇感兴趣。这个月，阅读了不少相关文献，找到了答案。答案是否定的。 首先，制造出通用的量子计算机仍然有极大的工程技术困难。 第二，再看看理论上，量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法，这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出（Shor因此获得哥德尔奖Godel Prize），历史也没有太长。想要知道这一算法与传统计算机算法有何不同，可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年，才36岁，是德州大学奥斯汀分校的教授，在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律，量子算法恰恰能更好地利用这一规律，一定程度上避免了暴力穷举。 要注意的是，整数分解并非特别难的问题。在基于传统计算机（图灵机）的计算复杂度理论中，整数分解被认为不属于P，但也只是比P问题略难一些，介于P和NP-Complete之间，且更靠近P。因此，量子算法能快速分解大数也只是情理之中。 知道量子算法是怎么做的，能做什么，就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话，澄清大众对量子计算的误解： If you take just one piece of information from this blog: Quantum computers would … 继续阅读 →

  本文地址：http://sokoban.ws/blog/?p=2330 作者：杨超 这个月，2016年3月，Google 的 DeepMind 团队开发的围棋程序 AlphaGo 在韩国首都以 4:1 战胜世界冠军围棋九段李世石。早在近20年前，IBM 的国际象棋程序“深蓝”就已经战胜人类冠军。而围棋棋盘比较大，人们普遍认为人类对计算机程序的优势在围棋项目还可以保持比较长的时间。而这次 Google 团队的胜利，证明了其实开发一个战胜人类的下围棋程序并没有那么难，而是开发这样的程序没有太大的直接收益，哪怕是国际象棋和围棋这样就有悠久历史传统和广泛的群众基础和关注度的棋类。 围棋究竟有多难？我们拿它和推箱子来比较一下。恰好我刚刚完成了用三篇博文来介绍推箱子问题的计算复杂度：推箱子是PSPACE完全问题。 为了从计算复杂度方面和推箱子问题比较，我们需要准确地定义一下什么叫围棋问题。 虽然人们常说围棋的变化很多，但是无论变化有多少，终究是一个有限的数。所有有限步内能分出胜负的、没有隐藏信息、也没有运气成分的二人棋类游戏，一定有一方有必胜策略（或者必和策略）。打个比分说，19路围棋按照中国的贴目规则也许是先手有必胜策略。那么我们所说的围棋问题，就是对于任意的n x n棋盘上下的围棋，如何设计一个算法来确定究竟是先手必胜还是后手必胜？或者等价地说，先手究竟有没有必胜策略？（即这是一个回答“是”或者“否”的问题）通常的19路棋盘围棋是围棋问题的一个实例。要回答这个问题，除了穷举所有的对弈变化之外，人们暂时还没能找到其它规律来判断谁有必胜策略。对围棋而言，穷举所需要的时间随着棋盘 n 的增大，是成指数增长的。事实上，已经有文献证明，按日本规则，围棋问题是EXPTIME完全问题（见［1，2］，该文章作者猜测，若按中国规则，围棋问题可能更难，成为指数空间完全问题）。也就是说，在指数时间可解的问题里面，围棋问题是最困难的其中一个。除了围棋，其它一些棋类问题如国际象棋、西洋跳棋（checkers）都被证明是EXPTIME完全问题。其中8×8棋盘的西洋跳棋在使用计算机花了近20年的穷举计算后，在2007年被证明双方都采取完美策略一定是和棋。 所以，从计算复杂度来看，包括围棋在内的许多棋类游戏比推箱子要难一个层次。计算复杂度的几个概念（EXPTIME、PSPACE、NP、P）的关系可用下图表示。虽然还没有从理论上严格证明，但是一般认为，从内到外，这四类问题的计算复杂度是严格地越来越难。 更有甚者，围棋问题的一些子问题，如征子能否成功问题在文献中被证明是PSPACE完全问题［3］。而围棋残局收官问题，则是PSPACE难的［4］。也就是说围棋问题的某些子问题就已经和推箱子问题一样难了。 那么，为什么比推箱子更难的围棋都已经开发出能战胜人类的程序，但是比围棋还容易一些的推箱子，我们却没有看到优秀的推箱子求解程序能够解出较大的、箱子数目较多的关卡呢？我想主要有以下这么一些因素。 首先，开发推箱子求解程序比开发下围棋程序更加无利可图。目前看到的一些求解程序基本都是个人单打独斗编写的，运行在个人电脑上，而且都是作为业余兴趣进行的。尚未看到有软件类企业或者研究团队投入较大资源来开发。作为对比，Google的AlphaGo程序投入了至少20人的开发团队，和李世石对战时动用了上千个CPU和GPU同时计算。 其次，AlphaGo虽然战胜了人类，但是并没有回答我们前面所定义的围棋问题，也就是说并不知道是否先手必胜。战胜人类并不需要穷遍所有变化，比判断19路围棋谁有必胜策略稍微容易一些。而一个推箱子关卡求解程序从某种意义上必须回答出推箱子问题，一般来说，必须穷遍所有路经才能判断一个关卡无解。而找到一个答案，除了穷举剪枝之外也还没有见到有人提出新的算法思路。 比较令人好奇的是，如果投入更多的人力和计算机运算资源，计算机求解推箱子能达到一个什么样的水平呢？能解出多大的关卡？解大关卡能比人解得更快吗？ 第83期推箱子比赛，我们也借着这个机会，由麦英兄设计了一关AlphaGo关卡。这一关计算机能解出来吗？ ［参考文献］ 1.  J. M. Robson, The complexity of Go, Proc. IFIP (1983) … 继续阅读 →

  本文地址：http://sokoban.ws/blog/?p=2254 作者：杨超 本文是两篇博文《 一系列具有递归关系和指数长度答案的推箱子关卡》 和《 判断推箱子关卡是否有解的多项式空间的算法》 的续篇。这三篇博文构成推箱子与PSPACE问题三部曲。 一、什么是PSPACE完全问题（PSPACE-complete problems） 前两篇文章已经提过，PSPACE问题指的是：相对于实例（instance）的大小，存在多项式空间算法的判断性问题（decision problem）。 而PSPACE完全问题是PSPACE问题中最困难的一类。即一个问题A能够被称为PSPACE完全问题，如果问题A满足：对任何其他的PSPACE问题B，都存在一个多项式时间的方法把B的实例转化成A的实例，使得这两个实例在这两个问题中有相同的答案（都是“是”或者都是“否”）。由此定义，只要能给出某个PSPACE完全问题的快速算法，那么这个算法就可以用来解决所有的PSPACE问题。 我们这里所说的推箱子问题（SOKOBAN），指的是给出一个推箱子关卡（即实例），如何判断这个关卡是否有解。 无论从实践到理论，都有证据表明推箱子是非常困难的。 实践中，我们举办了好几年的MF8推箱子网络比赛，尚未见到有人或者组织能够用计算机快速解出我们的比赛主关。 在计算复杂性理论中，推箱子问题也被证明是一个PSPACE完全问题。本文的目的就是简单介绍一下这些证明。要证明推箱子问题（或者其他问题）是PSPACE完全问题，要论证两个方面： 一是推箱子首先是PSPACE问题。因为存在很多问题，其难度甚至超出PSPACE的范围，我们需要说明推箱子没有超出这个范围。这一点的证明较为容易，已经在三部曲的第二篇文中说过了。 二是证明推箱子是PSPACE问题里面最难的。这又有两种常用的方法，第一种方法是按照定义，描述一种方案把任何一个PSPACE问题的实例转化为推箱子实例。第二种方法就是，描述一种方案，把某一个已经被证明的PSPACE完全问题的每个实例转化成推箱子的实例。 无论是用那种方法证明，其技术性都是比较高的，比较依赖于巧妙的构思。 二、PSPACE完全问题的例子 已经有许许多多的问题被证明是PSPACE完全问题。这些问题可以被用来证明其他问题也是PSPACE完全问题。这里介绍两个比较有代表性的。 第一个是TQBF问题（True Quantified Boolean Formula）。这个问题的一个实例就是一个每个变量都带有量词（存在、任意）的布尔逻辑公式。公式中的每个变量只能取值“真”或者“假”。 如：(任意x)(存在y)(存在z) ((x或者y)并且z) 我们需要判断这样的一个公式是否总是“真”的。 第二个是LBA问题，即线性空间自动机（Linear Bounded Automata）。这个问题的一个实例是：给出一个线性空间自动机和一个输入，该自动机是否接受该输入。 这个问题的PSPACE完全性证明非常简单。因此利用此问题证明推箱子问题是PSPACE完全问题，和直接用定义证明推箱子问题是PSPACE完全问题，几乎没有多大区别。 除此之外，推箱子和滑块类游戏也是PSPACE完全问题的有趣例子。 三、推箱子是PSPACE完全问题 Dorit Dor和Uri Zwick在1996年写文章［1］研究了推箱子问题的计算复杂度，但未能证明推箱子是PSPACE完全的。加拿大阿尔伯特大学的Joseph C. Culberson看到该文后，在1997年就证明了推箱子是PSPACE完全问题［2］。 … 继续阅读 →

  作者：杨超 本文地址：http://sokoban.ws/blog/?p=1133 随着第57期MF8（魔方吧）推箱子比赛结束，我们这个在线的推箱子比赛足足举办了五周年。这是一件值得高兴的事情，借这个时机总结一下这五年中比赛的发展变化。比赛能够举办五年，主要原因我想是推箱子爱好者们在编关和解关中得到了乐趣。anian、stopheart、荆先生、20603、zhenying、西北天狼、laizhufu、zhouxh、风过了无痕、(捷克)Přemysl Zíka、shamying、tengxi、Many illusions等都为比赛贡献过关卡。参加比赛的朋友就更多无法一一列出了。每期一般少则十来人，多则近三十人提交答案。参赛者来自中国、德国、法国、西班牙、保加利亚、阿鲁巴、丹麦、巴西、比利时、美国、俄罗斯等十多个国家或地区。我对编关和解关参与得较少，主要负责比赛的后勤工作。关于编关解关中故事，有待其他朋友来讲述，在此我说说比赛是如何办起来的，以及这五年中比赛网站、形式和奖品等的变化。 一、比赛的由来 比赛是借助魔方吧论坛这个平台办起来的，所以叫MF8推箱子比赛。魔方这个上世纪80年代风靡一时的智力玩具在2006年后又开始变得越来越流行了。究其原因，很重要的一个是有个民间组织叫WCA（世界魔方协会World Cube Association）在全球各地举办了越来越多的魔方竞速比赛。在这股潮流下，我也弄到了以前比较少见的四阶五阶魔方，并且于2007年夏天在MF8论坛注册了账号，而我注册的账号是sokoban。到了2009年，也跟MF8论坛的站长cube_master混了个脸熟。 2009年4月初，可能是由于老封关掉了他的推箱子论坛，MF8站长cube_master在魔方吧论坛里开增设了一个推箱子版。我马上毛遂自荐担任了推箱子版版主。可能是看到魔方的各种竞速比赛举办得红红火火，我很自然地也想在新成立的推箱子版搞一个在线比赛。于是开版才几天，第一期的MF8推箱子比赛就仓促开始了。 最初提交答案的方式极为麻烦。参赛者把答案加密打包在论坛回复，并站内私信把密码发给我。我再人工验证答案。比赛以这种很原始的方式运行了一年多，才得到改进。 前几期的比赛关卡也是由我从现有关卡中选取或是由我随意编的，质量不高。幸运的是，anian很快就加入比赛关卡的编排组织工作中，之后stopheart、荆先生和更多的朋友都为比赛提供了精彩的关卡，保证了比赛关卡的质量。 二、比赛网站 比赛的第一年，提交答案的方式的确很繁琐，很不友好。到了2010年6月，我学习了一些简单的PHP网站编程后，便利用国外的免费虚拟主机 http://sokoutil.orgfree.com 建立一个简易的在线提交和验证答案系统，简化了答案提交的流程。 比赛网站建立不到半年，由于不可抗拒的原因，中国大陆无法直接访问。于是把比赛网站整体迁移到另一国外的免费虚拟主机 http://sokoban.zzl.org 。搬家才两个月，中国大陆又无法访问了。一气之下，我便从国内的互联网服务提供商租用了虚拟主机，把网站再次迁移，从国外搬到了国内的服务器。同时依照工信部的规定，于2011年初通过了备案，成为一个合法的网站。 为了使比赛网站看上去更像一个正式网站，2010年底，注册使用了域名 sokoban.ws。2012年5月后，中国互联网信息中心（CNNIC）重新开放个人注册.cn域名，同年11月，我们又成功注册了 sokoban.cn 域名。 下面贴几个不同时期的比赛网站截图： 2010年10月 2011年11月 2012年4月 2014年3月（手机版截图） 三、比赛形式 我们一直希望吸引到更多的朋友参加到比赛中来，为此比赛形式做过一些调整。 第三十一期设立的围观答案，参赛者可以提交n-1个箱子归位的答案。到了四十三期，取消了围观答案，取而代之的是每期设立一主一副两个关卡。副关较为容易，降低参赛的门槛。事实上我们的比赛一直是完全公开的，不设任何门槛，参赛者甚至不需要在比赛网站注册账号，就可以参赛。 四、比赛奖品 我们的比赛虽然开始得比较仓促，但从第一期起就提供了奖品。 头两期的奖品是我厚着脸皮向MF8论坛的一位版主“七夜”要的，七夜没好意思直接拒绝，便赞助了两期铭浩之魔方。后来鬼手魔方也有意赞助我们的比赛，从第三期起到第五十五期，期间除了第三十期庆祝魔方吧论坛开坛八周年由大烟头赞助了宝石魔方，鬼手连续赞助了四年多。 从第三十四期到第四十八期，荆先生非常慷慨地赞助了幸运话费奖一年半。 比较遗憾的是目前比赛暂时没有了赞助，若有企业有兴趣赞助，我们非常欢迎。

作者：杨超 本文地址：http://sokoban.ws/blog/?p=843 在博文《推箱子游戏的一个箱子推动路径搜索算法》中，我介绍了推箱子游戏如何用鼠标双击或拖放来进行推箱子操作。我知道的大概有十多个甚至二十多个推箱子软件都实现了这一功能。最近，anian告诉我，他通过用20603兄的《一箭十万》关卡测试了多个推箱子软件，发现《YSokoban》的速度最快，点击箱子，瞬间程序就给出了所有能被推到的格子的提示。而我编写的《SokoPlayer HTML5》则需要约2秒。经过和anian兄的讨论，我们改进了算法，大幅度提高的效率，使得《SokoPlayer HTML5》也能瞬间给出提示（约3毫秒）。下面简单介绍一下我们如何作出改进的。 在一个箱子推动路径搜索过程中，要反复判断人是否能从箱子的一侧自由移动（即不推动箱子情况下）到箱子的另一侧。这个不难判断，用简单的广度和深度优先搜索都能在线性时间内得到答案。但是箱子推动过程中，箱子位置在变化，要在不同的位置都作出判断。假设涉及到的格子有n个，每判断一次要O(n)时间，但箱子最多也可能出现在n个不同的格子，要做n次这样的判断，所以总的时间复杂度是O(n^2)。当关卡比较大时，如《一箭十万》是50×50的关卡，不算墙体，格子也上千，导致计算时间比较长。 后来，我们发现判断各种位置下人能否从箱子一侧自由移动到另一侧，可以用一个线性时间算法完成。这可以用图论里的割点（Cut Vertex）和块（Block）的理论和算法来帮助我们。举一个具体的例子来说明什么是割点和块。割点把关卡区域分割成不连通的小区域，称为块。下图关卡中，黄色格子为割点，共有10个块，分别用数字1到10标记。 我们若能把推箱子地图所对应的图中的割点和块全部标记出来，那么回答人能否从一侧移动到另一侧就很简单了。可以用这两步来判断：（1）先看箱子是否在一个 割点上。若不是割点，则人一定能从箱子一侧移动到任意的另一侧。若是割点，则还要进行第2步判断。（2）看该箱子这两侧的格子是否属于同一个块。若是，则 能移动。否则不行。 如上图中，若箱子在割点G6位置，人能从箱子左侧(F6)移动到上侧(G5)，因为属于同一个块3号。但不能从左侧(F6)移动到右侧(H6)。又若箱子在H4位置，由于H4不是割点，人可以从一侧移动到任意的另一侧。 标记图的所有割点和块，有一个线性时间算法。这是一个基于深度优先搜索（Depth First Search）的算法。在深度优先搜索过程中，对每个结点记录两个参数。一个是结点的深度depth，另一个是结点的低位数（low point）。一个结点v的低位数是这样计算的，取下面三者的最小值：（a）v自身的深度，（b）v的所有邻点（DFS树中的父结点除外）的深度，（c）DFS树中v的所有子结点的低位数。 在实现中，通常用递归函数来进行深度优先搜索，于是计算低位数可以这样处理。每发现一个新结点v时，把低位数初始为该结点的深度（即a）。对v的每个邻点，若是父结点，不管；若是父结点以外的已访问结点，且若该结点的深度较当前的低位数小，重新赋值v的低位数为该结点的深度（即b）；若是未访问结点，那么找到了一个子结点，于是递归调用搜索函数进行下一层搜索，返回时，若该子结点的低位数较小，则用它的更新v的低位数（即c）。 下面两幅图给出了一个例子，给出其DFS树（红色边），每个结点的深度和低位数。括号内为低位数，黄色结点为割点。 有了深度和低位数，如何判断割点和块呢？ 对于割点，判断条件很简单，若结点v有某一个子结点的低位数大于等于v的深度，则v是割点。 搜索的根结点比较特殊，它是割点的条件是在DFS树中有至少两个子结点。 对于块的标记可以按如下方法实现。首先注意到割点同时属于多个块，其他点则恰属于一个块。在深度搜索过程中，每从一个子结点返回，并且由子结点判断出其父结点v是割点时，就意味着找到一个新的块了。此时，把v及其所有子孙都标记为同一个块。标记之后，在DFS树中，把v的所有子孙删掉，但保留v。这样v的子孙就不会被重复标记。而v是割点，还可能属于另外一个块。 以上文的图为例。2(2)是个割点，从子结点3(2)返回是能判断出来，同时能发现一个块。而从子结点3(3)返回时也发现2(2)是割点，于是2(2)在另外一个块中也被标记了。 [后两个图用LibreOffice Draw制作] 2013年12月22日补充：关于寻找割点算法，可参看用深度优先搜索(DFS)确定图的割点。

作者：杨超 本文地址：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 $高估了所有可能的局面数，但从数量级上是基本一致的），其中有一个局面是初始局面，有一个是目标局面。所以，如果一个关卡是可解的，一定在$ … 继续阅读 →

作者：杨超 本文地址：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=298 推箱子自1981年诞生至今，已经超过30年了。推箱子软件的功能也有了很大的改进。从刚开始的只能用键盘一步一步的移动，到上世纪90年代后期起，用电脑辅助搜索一个箱子的推动路径，从而实现用鼠标两次点击（或是拖放）就能实现一个箱子的任意推动。可以说，电脑辅助路径搜索，已经成为推箱子软件的一个标准功能，使得人们从繁琐的逐步操作中解放出来，在更大一些的关卡中探寻更多的挑战和乐趣。 一个箱子的推动路径搜索并不是一个很难的算法，用最基本的广度优先搜索算法(Breadth-first search)，就可以很快地找到一个推动数最少（但此时移动步数不一定最少）的路径。我2002年春写《Final Sokoban》第一次实现了这个算法，2004年写《M2 Sokoban》又实现了一次。这两次都是用C++或C在Windows平台下写的。2010年后写Java Applet《SokoPlayer》，用C写Linux下的《USokoban》和用Javascript写《SokoPlayer HTML5》，都实现过这个算法。下面简单说一下这个算法的要点。 首先，必须明确搜索的一个结点是什么。我们是考虑选中一个箱子后，不推其他箱子的前提下，把选中的箱子推到一个目的地。于是，在推动这个箱子的过程中，其他箱子可以视为墙体。又我们以推动一步为基本的单位来搜索，不以移动一步来搜索。所以搜索的一个结点由两个要素确定：一是箱子的位置，二是人相对于箱子的方向。这是因为箱子可以把人隔在关卡中不同的区域。 以下面这个简单的关卡为例： (图一) 可以点击下面链接玩这一关。 http://sokoban.ws/sokoplayer/?w=4&h=9&lvl=HHHH|H__H|H__H|H__H|H__H|HH$H|_HaH|_H.H|_HHH 这一关的按广度优先搜索得到的树如下： 在上述搜索树中我们看到，结点a 和结点 f 的箱子位置是一样的，但是由于人的位置不同，所以是两个不同的结点。一般地，当前要推动的箱子最多把关卡隔为四个不同区域（即上下左右，在程序中可以用0，1，2，3或其他常数表示）。所以若关卡大小不超过n*n，则搜索总的结点不超过 4n*n 个。 广度优先搜索通常要用到一个先入先出(First-in first-out)的队列(Queue)来保存搜索过程中的结点。根据前面的分析，每个结点只需保存箱子位置和人相对于箱子的位置。如，结点a可记为[(C, 6) 下]，其中(C, 6)是图一中箱子标尺坐标，“下”表示人相对于箱子的位置。这样，一个结点在搜索队列中用2到3个字节便可以保存。 其次，搜索过程中，结点可能重复出现，我们必须记住哪些结点前面已经访问过了，只把新的结点添加到搜索队列中。比如上面例子中，结点 e 箱子有向上和向下推两种可能。向上推得到新结点g；向下推得到的本质上是结点c，这个在前面已经出现，所以忽略不要。 幸好，我们已经分析过了，总结点不超过4n*n个，我们可以用一个4n*n个单元的数组来记录结点是否已经访问过。初始时，数组全为0，每遇到一个新结点，它在数组上对应的位置改为1，表示访问过了。于是，搜索中，我们每推一步得到一个结点，只需查看该数组的相应位置是0还是1，快速判断这个结点是否新结点。 比如，结点c我们可以记为[(C,4)下]。我们确认它是一个新结点加入队尾时，把[(C,4)下]对应的位置标记为1。注意，同时我们把[(C,4)左]和[(C,4)上]也标记为1，因为这三者本质上是同一个结点。在具体的算法实现上，我们检查一下人能否从箱子下方在不推动任何箱子的前提下，自由地移动到箱子的其他方向。 有了以上的分析，我们可以把总的算法描述如下（假设关卡不超过80 x 80）： (1)初始化准备：建立搜索队列q，把初始结点入队。用数组t[80][80][4] 来记录结点是否访问过，初始化为全为o，然后把数组t中与初始结点对应的位置和与之等价的位置标记为1。 (2) 主循环：根据队列是否为空，分别执行操作(2.1)或(2.2) (2.1) 若队列非空，让队头结点出队。从此结点出发，分别尝试向上下左右推动箱子一格。(如：看是否能向左推动，就是看人能否自由的移动到箱子右侧一格，且箱子左侧一格为空) … 继续阅读 →

作者：杨超 本文地址：http://sokoban.ws/blog/?p=217 今天成功编译并运行 XSokoban.  XSokoban的下载地址：http://www.cs.cornell.edu/andru/xsokoban.html XSokoban 是早期Unix/Linux下的一个开源的推箱子程序，93年发布3.0版，到97年3.3c版后停止更新，是比较有影响的推箱子程序之一，早在94年就实现了箱子的智能拖放。XSokoban的作者Andrew C. Myers现为康奈尔大学(Cornell University)计算机科学教授，这个程序是他在博士毕业之前的作品。XSokoban用X Window System (又称X11)来处理图像界面，故称XSokoban. 我是在Ubuntu 10.04下编译并运行XSokoban的。因为年代久远，README文件语焉不详，我还是颇费了一番功夫才把这14多年前的代码成功编译。现把其中一些细节记下来备忘。 1. 修改config.h文件并用命令 ./configure –with-CC=cc 生成 Makefile 。其中 config.h里面把WWW设为0，并设定路径(ROOTDIR)，用户(OWNER)和密码(PASSWORD)等信息。可根据命令 ./configure –with-CC=cc的错误提示来修改。 （2013年3月23日补充：系统升级到Ubuntu 12.04后重新编译了一次XSokoban，这里直接运行./configure脚本生成 Makefile即可，默认用gcc编译。另config.h中的目录一定要正确设置，否则编译后也会因为路径不正确在运行中无法创建scores文件而退出） 2. 用命令make编译。编译前，我手动在Makefile里设定了头文件路径INCS = -I/usr/include/X11（头文件xpm.h的路径），并把score.c里的getline 函数重命名为 getline2(和系统函数有冲突)之后才编译成功。 3.运行时要用 ./xsokoban -u <user>来输入用户名，在输入密码正确后才能运行。第一次还要用./xsokoban -c来创建scores文件。用./xsokoban -<xx>选关。 … 继续阅读 →