分类目录归档：推箱子

  本文地址：http://sokoban.ws/blog/?p=5352 到2021年4月，每四周一期的推箱子比赛已经举办了整整十二年。 十二是一个特殊的数字。最近刚好比较关注航天，这是因为木星绕太阳一周刚好大概12年，古人很早就注意到这个现象。因此，我国古人把木星称为“岁星”，用于纪年。 如，《荀子·儒效》写到武王伐纣： 武王之诛纣也，行之日以兵忌，东面而迎太岁。 在1978年出土的西周初年的青铜器利簋，在其内壁底部有铭文，亦描述了武王伐纣当天木星的位置： 武王征商，唯甲子朝，岁鼎，克昏夙有商，辛未，王在阑师，赐有事利金，用作檀公宝尊彝 。                                                       利用包括上述两条在内的古籍和出土文物的铭文中关于木星等天象记载，夏商周断代工程把武王伐纣的日期考证为公元前1046年1月20日。所以，西周利簋也被列入2002年国家文物局印发的《首批禁止出国（境）展览文物目录》。 虽然我国古人早就掌握了金木水火土五大行星在天空中的运行规律，但近距离观测行星直到今年才实现。目前，我国的天问一号探测器正在绕火星轨道上观测工作，下个月便会放出火星车软着陆火星表面。下图便是国家航天局3月初发布的天问一号拍摄的火星表面近距离高清照片。 那么，我国的探测器会不会造访木星呢？ 这事也早已排上日程了。不光要造访木星，还要在建国100周年之际（2049年），飞到太阳系的边界（100个天文单位左右）。为此，要飞掠木星，借木星的巨大引力加速。下图截取于2021年3月《宇航学报》北京空间飞行器总体设计部的田百义等《太阳系边际探测飞行任务规划》一文。 … 继续阅读 →

  本文地址：http://sokoban.ws/blog/?p=4392 为了庆祝比赛十周年，20603先生在122期为比赛设计的《十年树木》关卡。我在博文中借此谈了一下“十年树木，百年树人”的出处。 而在之前的121期，20603先生则为比赛设计了两个二维码关卡《推箱之家》和《推箱驿站》，并为此设计专门的皮肤。此两关若使用专门为二维码设计的皮肤，可以直接扫一扫打开比赛网站。 赛后，20603先生又放出了用于关卡设计的原始二维码，并指出了最后的关卡对原始的二维码作了改动。主关的原始二维码如下： 之所以可以改动二维码，其原因是二维码利用了一种可纠错编码 Reed-Solomon 码来进行编码。 仔细对比了一下主关的二维码，有6个位置黑白发生变化（其中有一个大概会被扫码器无视）： 另外五处刚好改变了5个格子（黑变白，或白变黑）。 根据二维码的标准，21×21规格的二维码一共有26个字节（Byte 一个字节8位，即8个黑白格），如下图： 邹兄设计的主关所用二维码采取的是有19个字节是记录真正的数据（实际上此二维码的内容，即网址 http://sokoban.ws 一共17个字节，加上字符串长度等额外信息，刚好用完19个字节）。 另外7个字节是用于纠错，能够发现和纠正3个字节的错误。二维码用的是 Reed-Solomon 纠错码。 按照上图26个字节的分布，几个黑白改动的地方分别属于3个字节，刚好达到这个（26，19）纠错码的纠错能力极限，还是能够正确地扫码打开我们的比赛主页。 给定了二维码设计推箱子关卡，这是难度非常高的“命题作文”，为了达到必要的难度，邹兄不得不改动二维码。但是二维码是用 Reed-Solomon 纠错码编码的，能够容许少数改动（错误）而还能正确解码。这算得上纠错码理论在推箱子中得到应用的一个非常妙的例子吧。 此外，在邹先生的提议下，我们颁发了比赛十周年纪念奖。邹先生为此又额外设计或发布了几个二维码关卡，其中一个用于作为荣誉证书的“章”，另外两个印刷成不干胶贴纸，随证书发放给十周年奖的获奖者。      

  本文地址：http://sokoban.ws/blog/?p=4325 MF8推箱子比赛五周年和第100期的时候，都写了博文。如今转眼已经是十周年第122期了，博文好像也写不出什么新东西了。感谢大家一直对推箱子保持热情，不断编新关卡和参与比赛，我们的队伍在平稳中也略有增长。九周年时我们在第109期作了一期四关的尝试，20603先生向我们展示了几乎一样的关卡可以有完全不同的过关路径。stopheart先生总是在群里不遗余力地引导新人入门。愉翁先生开发的安卓系统《推箱快手》功能之强大令人叹服。20603先生最近更是发表了半位理论的文章，是关于推箱子编关解关难得的深度研究。20603先生还为十周年比赛主关命名为《十年树木》，语出《管子·权修第三》： 一年之计，莫如树谷；十年之计，莫如树木；终身之计，莫如树人。 这句话大概是家喻户晓，用到我们的比赛关卡上，表明了20603先生的良好希望，祝愿我们的比赛能办到一百年以上。同时也表达了，通过推箱子比赛不断培养人才，是我们比赛能持续办下去的关键。 下面就截取不同版本的《管子》中“十年树木”一页的图来祝贺比赛十周年吧。 明万历十年赵用贤本，哈佛燕京图书馆藏。 《管子榷》明朱长春，明万历四十年张维枢刻本，哈佛燕京图书馆藏。 文渊阁四库全书，台北故宫藏。 1922年，上海商务印书馆，四部丛刊初编，景印常熟瞿氏铁琴铜剑楼藏宋刊本。据巩曰国<宋本《管子》的收藏与流传>，图书馆理论与实践，2009(2)，此宋孤本后被中国国家图书馆藏。 2004年，中华书局【新编诸子集成】《管子校注》，黎翔鳳。 现存最古老的《管子》，杨枕宋刻本，藏于中国国家图书馆。来自2002年启动的“中华再造善本”工程。2018年，国家图书馆出版社又出版了基于“中华再造善本”影印的《宋本管子》三册。

  作者：杨超 本文地址：http://sokoban.ws/blog/?p=3853 通常我们玩的推箱子关卡都是有限大小的，一般不超过50×50。因为最近读了不少关于不可判定（undecidable）问题的文章，很自然就问这样一个问题：我们已经知道有限大小的推箱子问题是可判定的，且知道其计算复杂度为PSPACE-complete；若考虑无限大小的推箱子关卡，即关卡占据整个平面，允许有可数无限个（countable）箱子和目标点，那么问题是不是也变成了不可判定的？ 比较著名的不可判定问题有： 图灵机的停机问题； 希尔伯特的Entscheidungsproblem问题，即一阶谓词逻辑系统的判定问题； 王浩瓷砖（Wang Tile）问题； 希尔伯特第十问题，即判定丢番图问题是否有解； 计算Busy Beaver数； 元胞自动机（Cellular Automata）的可逆性； ……等等。 现在，我们可以给这个列表又添加一个新问题：无限大小的推箱子问题。这个结论，早在1997年，Culberson证明推箱子是PSPACE完全问题时，就顺带指出了。因为Culberson的证明就是用推箱子关卡来模拟图灵机，从而把LBA问题（线性空间的图灵机）归约为推箱子问题。在往前走一步，自然任何一个潜在无限长纸带的图灵机也可以用占满整个平面的无限大小的推箱子关卡来模拟，从而把停机问题归约为推箱子问题。 这就证明了关卡无限大的推箱子是不可判定的。Culberson甚至指出，若限制只有有限个箱子没有归位（其余可数个箱子一开始都处于目标点），问题仍然是不可判定的，或者说是不可计算的。 这从另外一个方面也体现了推箱子有多难。      

  作者：杨超 本文地址：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=3720 我们的推箱子比赛举办了第100期，可喜可贺。为此，anian特别邀请20603设计了主关，副关也是丹麦DrFogh为100期特别设计的。 除此之外，anian还另外特别设计了《百花齐放》关卡。关卡发到sokoban.org， 长期有效，欢迎大家提交答案。这个关卡代表了一种特殊的类型，就是用推箱子来模拟另外一个orimaze的游戏，且模拟得相当紧凑。 我又邀请了青年漫画家小矛为100期画了新的墙纸。小矛在2012年也为我们设计过一张墙纸。两张墙纸都可以在这里下载。

  本文地址：http://sokoban.ws/blog/?p=3627 作者：杨超 接触推箱子这个游戏已经近20年，发起在线推箱子比赛至今已8年有余。比赛每月一期，现在正进行第100期。由于这个比赛，使得我业余持续地关注推箱子游戏，并且推箱子游戏也持续地给我带来很大的乐趣。趁着第一百期之际，谈谈推箱子是什么，以及推箱子给我所带来的精神上的快乐。 一、推箱子是什么？ 推箱子是一种成本极其低的智力消遣活动。早在推箱子出现之前，姜长英在1949年《论消遣》一文就分析过平民化的科学消遣的好处。最近看到《三联生活周刊》特约作者“土摩托”袁越在新浪微博问答中也表达了类似的观点：“……精神追求的成本越来越低了……我觉得这才是人类的未来，因为这是一种低成本满足所有人的唯一方式……”。 所以，以推箱子为爱好的朋友是非常幸福的，这玩意几乎不需要花钱。因为推箱子是一款纯软件产品。只要一个计算机系统足够开放和普遍，它上面一定会出现优秀且免费的推箱子软件，如Windows系统，如安卓系统。即便比较封闭的系统，如掌上游戏机、电子词典、电视机、机顶盒等等，都会出现推箱子。 我们举办网上的推箱子比赛的服务器成本也相当低。两个域名（sokoban.cn 和 sokoban.ws）加上租用服务器虚拟空间，平均每个月只要约28元，只相当吃一顿快餐。这么低的成本就可以把分散在全国乃至全世界各地的顶尖推箱子爱好者聚在一起，举办全世界水平最高的推箱子比赛，可算奇迹了。 这主要还是得益于电子计算机和互联网的快速发展。就最近来说，触屏式的智能手机只用了不到十年，就发展得非常成熟了，几乎取代了台式电脑，成为人们上网的主要设备。就我自己而言，微信等APP已经成为我获取信息的最重要渠道之一。很多跑步活动的信息我都是最先从微信获得，甚至就在微信中完成报名的。 因此，2014年7月，比赛网站也开通了微信订阅号，主要推送比赛开始等相关信息。继《推箱子加加》之后，愉翁又为安卓平台发布了《推箱快手》这款功能强大的APP。而苹果手机因系统较为封闭，虽是智能手机的引领者，却一直未见优秀的推箱子软件出现在该平台。 二、推箱子给我带来的快乐 下面罗列一些在推箱子中得到的快乐，其中很多事情做成了之后当时能高兴好几天。 为了测试各种平台下的推箱子，尝试了不同的操作系统。特别是编译运行了早期Linux平台下的XSokoban。为此至少连续使用了三年Linux的一个发行版Ubuntu作为平时工作生活的主要桌面系统。近三四年又以苹果的macOS X为主要的工作系统，因此对三大桌面系统Windows, macOS, Linux都算是比较熟悉了。甚至连PC-BSD, Solaris等非主流系统都安装试运行过几次。有了在不同的操作系统下的使用经验，对什么是操作系统的理解，比以前只会使用Windows时有了更深的认识。最近anian又告知有一款相当不错的Linux下KDE桌面的推箱子Sokoban SG，尚没有时间和精力测试。 学习并使用了多种编程语言。使用得比较多的语言是C、JavaScript、PHP。比较满意且花的功夫比较多的是用C编写的USokoban，用JavaScript编写的HTML5浏览器平台下的SokoPlayer HTML5，以及用服务器端编程语言PHP编写的比赛网站sokoban.cn以及关卡分享平台sokoban.org等。其它还尝试过写Firefox浏览器插件，用Python也写了一个简单的推箱子等等。后来因跑步和小孩出生，没有太多业余时间写程序了，但有些程序至今还时不时需要维护，如在第99期比赛时，还修正了比赛网站的一个bug：对副关的答案没有做“至少一推”的检验。 学习使用LAMP技术建设网站。LAMP是比较成熟的开源建站技术，租用服务器建站成本和技术难度都不算高。但是工信部对个人建立网站的管理时紧时松，为了比赛顺利进行，我还是在2011年初按工信部规定为比赛网站备了案。一开始只注册了sokoban.ws这个差强人意的域名，后来又注册到sokoban.cn和sokoban.org两个域名真是喜出望外。对整个互联网是如何运转的也有了些更深的认识。 琢磨了一些推箱子相关的算法。写USokoban时，实现了一个简单的解关器，掌握了解关器的一些基本算法。后来为了优化SokoPlayer HTML5推一个箱子的提示和寻径，想到了运用图论中找割点的算法，大大提高了计算的速度。 研究了推箱子及其变种的计算复杂度。计算了一系列具有指数长度答案的关卡所需要的精确步数。搞明白了推箱子问题的计算复杂度为什么是PSPACE完全的，还证明了推箱子的一个新变种也是PSPACE完全的，发表在学术期刊Theoretical Computer Science上面。 此外，关于推箱子的编关和解关，我几乎没有太多研究，还有许多宝藏有待今后挖掘。可见，推箱子是可以作为一生的爱好，不断地给人带来欢乐。  

    本文地址：http://sokoban.ws/blog/?p=3690 昨天，在海信智能电视上安装了第三方APP，测试了安卓版《推箱子加加》。今天，2017年6月21日，进一步测试在安卓电视上安装网页浏览器。我国的有线电视生态比较特殊。之前虽然没有电视，也从新闻中隐约知道，广电总局多次打压网络机顶盒。如在2015年，广电总局发布《关于依法严厉打击非法电视网络接收设备违法犯罪活动的通知》，禁止网络机顶盒提供视频聚合类APP或硬件服务（必须有全国牌照才行，如华数、上海文广、CIBN等。我的海信电视也是通过华数提供的牌照，提供预安装的视频聚集点播服务）。于是我对智能电视系统的封闭程度如何，能否随意安装第三方APP等不是特别乐观。经过一番网络搜索调研，发现《电视家浏览器》看上去还不错。于是，便和昨天一样，通过u盘和ES文件管理器，成功安装《电视家浏览器》，访问了比赛网站 http://sokoban.cn ，并运行了《SokoPlayer HTML5》，通过遥控器上下左右控制光标，可以完美地进行游戏。下面是一些图片。 注：发现最近对比赛网站首页微调后，在 Windows 10的默认浏览器Microsoft Edge中，右侧微信和QQ二维码和中栏有覆盖重叠。没想到在这个安卓TV版《电视家浏览器》中有同样的问题。在Firefox中则显示正常。此问题有待修正。（补充：2017年7月8日，修正了这个bug，把第二栏和第三栏交换）