Sokoban Competition
The 104th MF8 Sokoban Competition [魔方吧推箱子比赛]
第100期比赛特别关卡：
《SokoPlayer HTML5》
（作者：Zika）
你是从哪一年开始玩推箱子的？
1990年之前
2011年以后
手机扫一扫二维码关注本站微信公众号。
QQ推箱子群：
July 14, 2017 To celebrate the 100th competition,
a new wallpaper is created by Xiaomao. Click
to download the wallpaper.
July 4, 2017 To celebrate the 100th competition, we present a SPECIAL level -
- at http://sokoban.org.
May 24, 2017 更新到版本5.71，并且已经开源。感谢愉翁先生为大家提供了如此优秀的推箱子程序。
May 4, 2017 我的一篇与推箱子相关的学术论文《SNOWMAN is PSPACE-complete》5月2日正式发表，
从发表日起50天内（至日）
可在Elsevier网站上免费下载：
April 24, 2017 《推箱快手》更新到版本5.61。《推箱子加加（Soko++）》更新到版本1.21。
April 3, 2017 愉翁开发的更新至版本5.39。
March 27, 2017 One of the organizers of the MF8 Sokoban Competition, Dr. Chao Yang,
has just published an academic article about the computational complexity of a Sokoban-like puzzle,
in the journal Theoretical Computer Science.
for more information.
友情链接 |
Sokoban Web Site [sokoban.ws]
Sokoban CHINA []
Copyright &
Chao YANG and friends||||操作：//点击控制机器移动，将箱子推到指定的地方。操作说明：//点击控制机器移动，将箱子推到指定的地方。如何开始：点击“点击开始”。游戏介绍：这个推箱子游戏有非常非常多的关卡，多达4667关。而且其中4100关带答案，对于刚刚学习的你们非常有帮助。一起来玩玩吧~大小：1.2MB游戏目标：成功地将所有的箱子推到指定位置即可过关！游戏评论：104939388485写这个程序是因为在看《Java并发编程实战》书的时候，提到过用多线程来解决推箱子游戏，感觉挺好玩的，于是就开始写啦！！
先介绍一个推箱子网站（主页）：
在这个网站你在它的规则（格式）下，也可以轻松获得推箱子地图、验证答案。
规则、格式：
推箱子地图获取、答案验证：
详细使用可以看下面的运行介绍
对于不复杂的图（地形不大、箱子不多或者求解比较复杂）的图，大部分可以完成任务，但对于太复杂的地图，时间很长，而且最终有可能会导致OutOfMemory异常，而解不出来。（后面有几个解决的想法）
多线程比单线程速度快，但是多线程时间不稳定，起伏较大。
简单来说，就是使用深度遍历所有路径，直到找到解决的路径或者找不到退出。
其中，有多线程版本和单线程版本
程序主要分为3部分：
2.人的移动
3.路径搜索
保存地图信息，以及提供关于地图的基础功能：地图检查、修改地图信息
坐标点：x，y
创建后便不可修改
MapSymble：
指定地图信息用什么字符表示：墙壁、普通地板、站在目标点上的人、目标点、箱子、人、地图行间分隔符（整个地图用一个String存储时）、在目标点上的箱子
MapDirection：
地图方向：上下左右
SokobanMap：
创建后便不可修改
保存地图及相关信息：
1.地图信息
2.人的坐标点
3.长度，宽度
4.达到当前地图信息人所走过的路径（如果解决后，最后输出的结果）
提供地图相关功能：
1.获取某坐标的字符
2.指定将某坐标的字符替换成指定字符，然后返回新的SokobanMap对象（不是返回当前对象）
MapChecker：
检查地图是否有效，标准为：
1.地图必须为长方形的规整图形
2.不能存在无效字符（不在MapSymble没有的字符）
3.WALL必须封闭
4.必须有且仅有一个人
5.不能存在无效行（整行都是GROUND）
检查WALL是否封闭方法：
采用深度搜索，选定起始墙壁（通常为第一行中出现的第一个WALL），然后沿着墙壁遍历没走过的墙壁（只走墙壁），如果最后返回起始点则表明这墙壁是封闭的。
不能检查出是多个闭环还是只有一个闭环
人的移动部分
用于执行人的上下左右的移动，提供移动后的地图。
其中移动会有两种操作：
1.普通的移动，由地板到另一个地板（目标点）
2.推动箱子的移动，移动方向上有一个箱子
其中移动有可能会有两种结果，能否移动，其中，导致不能移动的原因有：
1.遇到了墙壁
2.遇到箱子，但箱子贴着墙壁
3.遇到箱子，但是箱子又贴着另一个箱子
IMapMoveRule：
运行规则，决定一个字符移动后地图的变化（目的地点以及原地点的变化）
包含两个方法：
1.当字符A移动到字符B后，字符B的坐标上应该显示什么字符
2.当字符A移动后，原来字符A的坐标上应该显示什么字符
DefaultMapMoveRule：
实现IMapMoveRule
下面列举的是方法：2.当字符A移动后，原来字符A的坐标上应该显示什么字符
public Character getCharOfGoalAfterMove(char goalChar, char moveChar) {...}
* 返回moveChar移动后原来所处的位置应该显示的字符
* moveChar 移动的字符（只能为人和箱子，只能为MAN,BOX,MAN_ON_GOAL,BOX_ON_GOAL）
* 移动后原来地点应该显示的字符
* MapSymble
public Character getCharOfMoveAfterMove(char moveChar) {
Character res = null;
if (moveChar == MapSymble.MAN_CHAR || moveChar == MapSymble.BOX_CHAR) {
res = MapSymble.GROUND_CHAR;
} else if (moveChar == MapSymble.MAN_ON_GOAL_CHAR || moveChar == MapSymble.BOX_ON_GOAL_CHAR) {
res = MapSymble.GOAL_CHAR;
ManMover：
返回人往指定方向移动一格后的地图（返回的地图是新对象），如果不可移动直接返回原来的地图。
* 如果往该方向移动一格是合法的移动，则返回移动后的SokobanMap，否则返回原来的SokobanMap，使用默认的移动规则DefaultMapMoveRule
* direction
public static SokobanMap moveOneStep(SokobanMap map, int direction){
return ManMover.moveOneStep(map, direction, new DefaultMapMoveRule());
public static SokobanMap moveOneStep(SokobanMap map, int direction, IMapMoveRule mapRule) {
switch (direction) {
case MapDirection.UP:
return ManMover.up(map, mapRule);
case MapDirection.DOWN:
return ManMover.down(map, mapRule);
case MapDirection.LEFT:
return ManMover.left(map, mapRule);
case MapDirection.RIGHT:
return ManMover.right(map, mapRule);
return null;
* 每次移动一格，修改传入的地图参数，返回新的地图
* movePoint
* direction
private static SokobanMap move(SokobanMap map, int direction, IMapMoveRule mapRule) {
SokobanMap resMap = null;
Point movePoint = map.manP
Point nextPoint = ManMover.getTargetPoint(movePoint, direction);
Point nextNextPoint = ManMover.getTargetPoint(nextPoint, direction);
else if(goalChar == MapSymble.GROUND_CHAR || goalChar == MapSymble.GOAL_CHAR){
resMap = map.modifyPoint(movePoint, mapRule.getCharOfMoveAfterMove(moveChar));
resMap = resMap.modifyPoint(nextPoint, mapRule.getCharOfGoalAfterMove(goalChar, moveChar));
resMap = new SokobanMap(resMap.getMapList(), resMap.path + MapDirection.getPath(direction));
路径搜索部分
深度搜索，直至发现解决问题的路径
ISokobanSolver：
包含一个方法：
1.传入初始地图，然后开始搜索
2.返回解决了的SokobanMap，如果没有则返回null
包含3个方法
1.判断地图是否已经解决
2.判断地图是否已经走过（如果走过了，如果当前的路径比存储的路径短，则更新路径）
3.清空缓存
DefaultJudger：
实现了IJudger，其中用Set来保存遍历过的地图信息
private Set&String& paths = new ConcurrentSkipListSet&String&();
public boolean isSolved(SokobanMap map) {
if(! map.mapStr.contains(MapSymble.GOAL) && ! map.mapStr.contains(MapSymble.MAN_ON_GOAL)){
return true;
return false;
* 判断当前地图情况是否之前已经出现过，如果没有则将添加当前地图情况，返回false，
public boolean isPathed(SokobanMap map) {
if (!paths.contains(map.mapStr)) {
paths.add(map.mapStr);
return false;
return true;
ViolentSingleSolver：
单线程的暴力（深度搜索）求解程序
ViolentConcurrentSolver
多线程的暴力（深度搜索）求解程序。
线程数量固定为电脑的cpu核数，每条线程负责搜索一条路径，直到该路径解决问题，当该路径已经无法继续走时，结束当前线程。在别的运行中的线程，开出一条新线程来执行新路径的搜索。
程序唤醒机制：
采用唤醒机制，来使主线程等待路径搜索线程执行完任务
if (this.solvedMap == null) {
executeIterateFindPath(map);
synchronized (lock) {
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
if (this.judger.isSolved(nextMap)) {
//检测到nextMap已经解决
//保存结果地图
this.solvedMap = nextM
//唤醒主程序
synchronized (lock) {
lock.notify();
多线程执行部分：
而且要让线程保持在指定的数量
这里采用了固定的线程池以及信号量来完成
private ExecutorService pool = Executors.newFixedThreadPool(POOL_SIZE);
private Semaphore aliveThread = new Semaphore(POOL_SIZE);
然后执行中，通过信号量来限制是创建新线程来执行该路径的遍历，还是继续在当前线程中执行遍历
private boolean executeIterateFindPath(final SokobanMap map) {
if (aliveThread.tryAcquire()) {
pool.execute(new Runnable() {
public void run() {
iterateFindPath(map);
aliveThread.release();
return true;
return false;
private void iterateFindPath(SokobanMap map) {
Stack&SokobanMap& maps = new Stack&SokobanMap&();
maps.add(map);
while (!maps.isEmpty()) {
map = maps.pop();
SokobanMap nextMap = this.getNextMap(map);
while (nextMap != null && this.solvedMap == null) {
if (this.judger.isSolved(nextMap)) {
this.solvedMap = nextM
synchronized (lock) {
lock.notify();
if (!executeIterateFindPath(nextMap)) {
maps.add(nextMap);
nextMap = this.getNextMap(map);
运行介绍：
ISokobanSolver solver = new ViolenceConcurrentSolver(new DefaultJudger());
SokobanMap map = readMap();
if(MapChecker.isValidMap(map)){
solver.solve(map);
SokobanMap resMap = solver.getSolvedMap();
if(resMap != null){
System.out.println(resMap.path);
System.out.println("can not find the way to solve the SokobanMap");
System.out.println("this is not valid sokoban map");
1.获取地图，输入地图：
1.打开上面给的网址
2.在红框1中选择好关卡
3.点击红框2中的输出关卡
4.在红框3中会有该关卡的地图信息
5.复制地图信息到程序中，再在下一行输入end
2.进行求解，获取结果
刚点击enter后，会显示开始时间，过一会后，会出现解决结果，如果比较复杂的图（地形大、箱子多），可能会等很久或者解不出来
3.开始验证答案
1.将之前输出的结果复制到红框2中
2.再点击红框1中的载入答案，然后它就会自己运行答案
程序优化方案（未实现）
目前代码中有一个判断地图是否已经遍历过，其中用的是set来存储是否已经走过，其中走的路径越多，存储的地图也越多，因此解决部分复杂地图的时候，就会导致OutOfMemory异常。
这里有些可以改烧解决这方面问题的想法：
存储优化：
遍历过的地图信息不再保存在内存中，而是保存在本地中（数据库、文件），用空间换时间来进行优化。
可结合加上当前存储方法，对简单地图使用内存保存，复杂方法转向本地保存。可以增加存储的限额，当到达限额后，不再保存在内存中，而是保存到本地中。
路径选择优化：
目前是上下左右4个方向都回进行遍历，但实际上部分路径是没有意义的路径，考虑是否通过对路径的筛选，来进行优化
多线程、单线程版本时间比较
多线程版本和单线程版本采用的都是迭代的深度搜索
long time = 0;
final int count = 100;
int successCount = 0;
SokobanMap map = readMap();
for (int i = 0; i & i++) {
ISokobanSolver solver = new ViolenceConcurrentSolver(new DefaultJudger());
if (MapChecker.isValidMap(map)) {
solver.solve(map);
} catch (Exception e) {
e.printStackTrace();
SokobanMap resMap = solver.getSolvedMap();
System.out.println("Time: " + solver.getSolvedTime());
if (resMap != null) {
time += solver.getSolvedTime();
successCount++;
System.out.println(resMap.path);
System.out.println("can not find the way to solve the SokobanMap");
System.out.println("this is not valid sokoban map");
System.out.println("Average: " + time / successCount);
多线程版本100次平均耗时：3700ms
单线程版本100次平均耗时：6251ms
多线程版本100次平均耗时：431ms
单线程版本100次平均耗时：828ms
本文已收录于以下专栏：
相关文章推荐
导读： 　　推箱子游戏的自动求解 　　 　　简介 　　推箱子，又称搬运工，是一个十分流行的单人智力游戏。玩家的任务是在一个仓库中操纵一个搬运工人，将N个相同的箱子推到N个相同的目的地。推箱子游戏出现在...
用java的swing实现的推箱子小游戏，并且有地图自动生成程序。（即游戏关卡自己创建）
也可进Q群五四二1九一七9，共享里下载源码。
下载地址：/m...
Android应用程序入门 推箱子游戏开发（一） surfaceView 实现动画效果
SurfaceView是View的子类，常用于实现游戏中的动画效果。SurfaceView最大的特点就是：从主线...
Android应用程序入门 推箱子游戏开发（二） 键盘事件监听 角色在屏幕上移动
先看一下效果图。
        我们的目标是：通过键盘按键，控制人物在屏幕上自由移动。要实现这个目标，只要完成下面...
他的最新文章
讲师：AI100
讲师：谢梁
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)|||||推箱子-含300关全部答案 V2.5绿色版
您的位置：& > &推箱子-含300关全部答案 V2.5绿色版
推箱子-含300关全部答案 V2.5绿色版
网友评分：
软件大小：797KB
软件语言：简体中文
软件类型：国产软件
软件类别：益智游戏
更新时间：
软件授权：特别版
官方网站：
运行环境：Win9x/Me/NT/2000/XP/2003
4.096MB/简体中文/7.5
1.607MB/简体中文/6.7
33.30MB/简体中文/7.5
93.2MB/简体中文/7.1
624KB/简体中文/7.5
记得几年前，《推箱子》在PC机上刮起了一股不小的益智类游戏的旋风，现在许多资深玩家也都对《推箱子》赞不绝口，可见有深度的益智类游戏是非常受大家欢迎的。
推箱子游戏出现在计算机中最早起源于1994年台湾省李果兆开发的仓库世家，又名仓库番，箱子只可以推, 不可以拉, 而且一次只能推动一个，胜利条件就是把所有的箱子都推到目的地。
推箱子游戏是一种老少皆宜的益智游戏，既可以开发青少年学生的智力，又可以防止老年痴呆症，全家一起攻关还可以促进家庭和睦，何乐而不为？
由蒋祥刚开发的《推箱子》游戏，有如下几个特点：
·关卡多而不重复。·画面精彩，操作方便，功能齐全，是这类游戏中的佼佼者。·可以撤销，最多可以悔100步！·可以选关，自动记录答案，可以载入答案。·有动听的背景音乐，还可以载入你喜欢听的MP3，等音乐。·尤其当你通过了一个比较复杂的关卡后，回过来再载入答案欣赏一下过关的乐趣，实在是过瘾得很啊！如果你在载入答案时按住 N 键不放，相信会让你捧腹大笑！·该游戏还可以自动显示中英文界面，如果您的计算机操作系统是英文，则游戏显示英文界面，否则显示中文界面。
软件无法下载或下载后无法使用，请点击报错，谢谢！
请描述您所遇到的错误，我们将尽快予以修正，谢谢！
*必填项，请输入内容
本类下载排行查看: 839|回复: 17
最后登录在线时间60 小时阅读权限20注册时间积分215帖子精华1UID1303898性别男
蓝魔, 积分 215, 距离下一级还需 385 积分
积分215帖子精华1UID1303898性别男
我写了一个程序，可以从推箱子的解答步骤还原关卡地图。可以访问以下网页： 在线使用该程序。
其算法可以参见我的博客：
总评分:&经验 + 40&
最后登录在线时间321 小时阅读权限20注册时间积分429帖子精华0UID1276025性别保密
蓝魔, 积分 429, 距离下一级还需 171 积分
积分429帖子精华0UID1276025性别保密
哈哈，楼主的程序和之前金优兄的程序有得一比，非常类似，试了一关，还原的地图和金优的那个一样。很好，我不懂程序，支持你！
最后登录在线时间60 小时阅读权限20注册时间积分215帖子精华1UID1303898性别男
蓝魔, 积分 215, 距离下一级还需 385 积分
积分215帖子精华1UID1303898性别男
再来一幅图片：
最后登录在线时间60 小时阅读权限20注册时间积分215帖子精华1UID1303898性别男
蓝魔, 积分 215, 距离下一级还需 385 积分
积分215帖子精华1UID1303898性别男
回复 2# 的帖子
谢谢您的支持。
如果您有什么意见和建议，请在这里提出，或者到博客园中我的博客中提出，以便我改进程序。谢谢！
最后登录在线时间60 小时阅读权限20注册时间积分215帖子精华1UID1303898性别男
蓝魔, 积分 215, 距离下一级还需 385 积分
积分215帖子精华1UID1303898性别男
继续给出图片：
最后登录在线时间2780 小时阅读权限100注册时间积分1883帖子精华3UID91928性别保密
积分1883帖子精华3UID91928性别保密
感谢分享!& && &
魔方吧版。推箱子QQ群：
最后登录在线时间4973 小时阅读权限100注册时间积分4936帖子精华18UID13140性别男
积分4936帖子精华18UID13140性别男
非常好的在线工具，添加到sokoban.ws的友情连接了
最后登录在线时间60 小时阅读权限20注册时间积分215帖子精华1UID1303898性别男
蓝魔, 积分 215, 距离下一级还需 385 积分
积分215帖子精华1UID1303898性别男
非常感谢 anian 和 sokoban 朋友的支持！
最后登录在线时间2780 小时阅读权限100注册时间积分1883帖子精华3UID91928性别保密
积分1883帖子精华3UID91928性别保密
skyivben兄， 你的程序有个bug。 (和XhtXsb.exe有同样的bug)
请试试这个LURD： (这个LURD是我以前用来测试 LURD2XSB程序的)
UlLLUuuluLlDlldddrRRRRRRRRRRdrUllllllllllllulldRRRRRRRRRRRRRuRRlDllllllluuululldDDuulldddrRRRRRRRRRRdRRlUllllllluuulLulDDDuulldddrRRRRRRRRRRuRDllllllluuulluuurDDuullDDDDDuulldddrRRRRRRRRRRRRlllllllluuuLLulDDDuulldddrRRRRRRRRRRRldR
13:24:17 上传
魔方吧版。推箱子QQ群：
最后登录在线时间60 小时阅读权限20注册时间积分215帖子精华1UID1303898性别男
蓝魔, 积分 215, 距离下一级还需 385 积分
积分215帖子精华1UID1303898性别男
anina 兄您好，您给出的解法步骤中前六步是：UlLLUu。问题就出在第六步，因为第五步是“U”，表示推着箱子往上走一步，而第六步是“u”，表示不推箱子往上走一步，而这是不可能的，第五步中推着的箱子到哪里去了？我在“[/url]”这篇文章中“解法步骤不合法的情况”小节作了说明：
上面三幅关卡地图分别是从“LURD”、“Rrr”和“RL”解法步骤中还原出来的。对于这些不合法的解法步骤，本程序也不报错。本程序只保证合法的解法步骤能够还原出正确的关卡地图。此外，本程序还忽略解法步骤中“lurdLURD”以外的所有字符。
也就是说，我的程序对不合法的解法步骤并不报错(XhtXsb.exe应该也是这样)，只保证合法的解法步骤能够还原出正确的关卡地图。
当然，如果大家认为对不合法的解法步骤需要报错的话，我也可以修改程序。
感谢您的指正。
超级搬运工
论坛建设奖
Powered by