《百川归海》系列关卡的诞生

cjcjc

200期比赛开始前4天，群里在讨论《百花齐放》。那关是100期比赛时，an版主所作的特别关卡，挂在推箱子网站主页8年，还没有人解开，也包括我。我对这种orimaze关卡一直没找到窍门，研究了几次都没有进展，所以就丢下了。书归正传，an版主问我要不要做一个200期的特别关卡？我当时什么想法都没有，何况按我的经验，如果编一个主关级别难度的关卡，少说要几个星期，多了几个月可能都不止，而且白天需要工作，只有晚上几个小时用来编关，所以我只是说试一试，没觉得能做出一个像样的关卡。
之后我在思考，怎么样才能做出一个有意思的特别关卡呢？当天晚上，我突然想到了0空位腾挪，0空位腾挪顾名思义就是在一个局部的腾挪里，不仅没有整位，连一个半位也没有。在03大师、xian兄、伞兄等人的一些关卡中，就有0空位腾挪的局部，不过只是作为关卡中很小的一个元素，这部分的腾挪通常也不复杂，我自己也研究过0空位腾挪，有一点经验，但是没有应用到编关中。半位关卡中，经常会“天然”地出现一些0空位腾挪，就是并非作者故意设计，而是凑巧出现这样的局部。不过我当时还没有见过一个大关卡中，从头到尾整体都是0空位的（后面我问了下an版主，他说他之前也没见过类似的关卡）。那如果能设计出这么一个大关卡，关卡整体没有空位，全程都是0空位腾挪，岂不是很有意思？
因为时间紧迫，手动设计肯定是来不及了，于是我想到，可以用电脑，随机生成一个规整的0空位初始盘面，在不死锁的前提下随机乱推若干步，说不定就可以生成一个比较难的关卡了，后期我也可以在此基础上手动做一些调整，增加点难度（实际上生成的关卡太大了，想要手动做调整增加难度不知道该如何下手，所以最后就把这步省掉了:p）。于是我立刻开始动手，在DeepSeek辅助下，于比赛开始前3天完成了代码。为了方便实现随机生成关卡的功能，我加了一些限制：初始盘面是正方形，关卡内部的墙都是1*1大小的，墙与墙的距离都是1。生成初始盘面，我用的算法是：从左上角C3内墙开始，找到相邻的内墙，然后随机挑其中一个用箱子连起来，直到把所有内墙都连起来为止，就好像有很多河流，最后汇在一起，形成了一张复杂的网络一样。于是，我就给当时还未成型的关卡先定好了名字——《百川归海》。后面随机打乱时，也用了类似的算法，这里就不具体说了，有兴趣的朋友可以看看代码。
这样随机生成一个初始局面，再随机打乱若干步，把打乱后的局面作为结束局面，就得到了一个随机的0空位关卡。这个关卡一定是有解的，随机打乱的步骤就是关卡的答案，我又抄袭了一下愉翁兄推箱快手的代码，写了一个把打乱步骤翻译成lurd格式答案的功能，经过一番调试之后开始第一次运行，生成了一个99个箱子，随机打乱10万步的关卡，发给了an版主。这个关卡随机打乱的步骤翻译成lurd之后有400万步，当时我手边的电脑内存比较小，优化不下去，我估计那关的最优步数在10000步以内，甚至可能只有一两千步。我手动推了一下这个关卡，当时没什么经验，又比较晚了，脑袋转不动了，觉得这关难的离谱，转来转去完全找不到过关的方法。推起来的感觉有点像orimaze关卡，又有点像以前出现过的moves=pushes关卡，还有点像魔方，总之是挺有意思的。于是决定就这样，生成一个尺寸更大的、打乱步骤更多的关卡作为最终的版本。
我设置成48*48-1=2303个箱子，随机打乱100万步，开始运行程序，跑了一天一夜，到比赛前2天晚上还没跑完。经过一番调试发现是把打乱步骤翻译成lurd的代码运行太慢了，于是后面改成把打乱步骤保存成点推，运行快了很多。我的代码还是效率太低了...
同时，我又有了一个新的想法。按上面的规则生成的《百川归海》类型的0空位关卡（简称b型关卡），箱子只能在同一行或者同一列中运行，这一点群里的朋友关山月也指出来了。如果把内墙改成两个1*1的墙对角摆放，整体还是0空位，但是箱子就可以运行到相邻行列了，变化的可能性增加很多。于是我按新的想法修改了代码，在比赛前1天晚上完成了修改，生成了《万丈深渊》型0空位关卡（简称w型关卡）。当时我以为这样生成的关卡会比《百川归海》难度高一个档次，《百川归海》已经难的离谱了，那这关岂不是压根不是人类能解开的关卡？我觉得《百川归海》如果是100，那这关至少也是10000吧，所以取名叫《万丈深渊》。
于是我有点得意忘形了，批量生成了一大堆关卡，也就是分享在群里的《百川归海集合》，分享给了an版主。其中：《潭池》是24箱子，随机打乱1000次生成的，这20关难度基本都是0；《溪流》是48箱子，随机打乱1万次生成的，这20关有一点难度，但是经过思考还是能过关；《湖泊》是99箱子，随机打乱1万次生成的，这20关已经很难了，我当时试推了一关，完全没找到方法；《江河》是224箱子，随机打乱1万次生成的；《海洋》是399箱子，随机打乱10万次生成的；《百川归海》是899箱子，随机打乱100万次生成的，这一关就是最终的版本，这关的关卡尺寸和箱子数量都和100期的特别关卡《百花齐放》差不多；《百川归海(恐怖版)》是2303箱子，随机打乱100万次生成的；《万丈深渊(轻松版)》是99箱子，随机打乱10万次生成的；《万丈深渊》是399箱子，随机打乱300万次生成的，这关和《百川归海》的尺寸保持一致；《万丈深渊(恐怖版)》是1023箱子，随机打乱300万次生成的。随后比赛开始当天，我把这个关卡集分享在了群里。
完成比赛关卡后，我开始推《百川归海集合》。虽然这个集合中的关卡在生成时把答案也保存下来了，但是我没有实际推过。推了一上午搞定了前40关和《湖泊》中的一关，基本了解了关卡的特点，也掌握了这类关卡的腾挪方法，发现没有我想象中的那么难，完全达不到“难的离谱”这个级别，不过我觉得难度可以达到9.0分。我也试推几个了w型关卡，也发现比想象中简单很多，之前的评价“压根不是人类能解开的关卡”过于夸张了。因为虽然箱子可以运行到相邻行列，变化的可能性提高了一个数量级，可是相应的腾挪也更加自由了，有的时候打乱的步骤很复杂，但是可以用简单的方式还原回去。另外，因为内墙形状比较复杂，所以相同尺寸的w型关卡比b型关卡箱子数量少很多。不过w型关卡还有一个特点，就是结构太花了，对人类眼睛不太友好，总之我觉得难度大概也是9.0分。虽然这两关难度没有我想象的那么高，不过至少是创新的，而且是有趣的，作为特别关卡也挺合适，至于名字，也懒得重新起了，将错就错吧。
最后把随机生成关卡的程序分享给大家，用java写的，运行时需要有java环境。运行命令是 java -jar sokoban.jar w 10 1000，其中第一个参数是生成关卡的类型，w是生成w型关卡，b是生成b型关卡，第二个参数代表关卡尺寸，生成关卡的箱子数量等于第二个参数的平方减去一，第三个参数代表关卡的随机打乱步数。生成关卡的尺寸不能超过100*100，换言之w型关卡第二个参数最大是32，b型关卡第二个参数最大是48（也就是恐怖版两关的尺寸）。理论上，随机打乱的步数越大，生成的关卡就越难，但是到一定步数之后再打乱难度就变化不大了，所以第三个参数也不需要设置太大。参数数量和参数值不对会提示错误，如果正常运行会生成一个文本文件，里面有关卡的xsb格式和点推格式答案。这一系列的关卡就到此为止了，以后我不再用程序随机生成这种关卡了，感觉没什么意义了。

关卡类型	参数1	参数2	参数3
《百川归海》型(b型)	b	不大于48，生成关卡尺寸为(2n+3)*(2n+3)	打乱步数
《百川归海-扩展版》型(e型)	e	不大于48，生成关卡尺寸为(2n+3)*(2n+3)	打乱步数
《万丈深渊》型(w型)	w	不大于32，生成关卡尺寸为(3n+3)*(3n+3)	打乱步数
《百舸争流》型(g型)	g	不大于32，生成关卡尺寸为(3n+3)*(3n+3)	打乱步数
《百川归海-特别版》型(s型)	s	不大于47，不小于7，建议选择8-15，生成关卡尺寸为(2n+3)*(2n+5)	打乱步数

4.7 关卡生成器v1 + 百川归海集合.xsb
4.10 关卡生成器v2 + 百舸争流.xsb
4.13 关卡生成器v3
4.17关卡生成器v4 + 百川归海集合.xsb

sokoban.zip (55.4 KB, 下载次数: 35)

2025-12-12 16:24:06 上传

下载次数: 35

5.8关卡生成器v5 + 百川归海集合.xsb（上传日期12.12）

cjcjc

之后为了补上漏洞，我对这个设计进行了一些调整，在出口的同一边的另一端增加了一小块区域，减少了一个不靠外墙的箱子，代码也进行了修改，新的程序随机生成S型关卡。根据我的推测，生成的关卡都可以作为双向通道。
命令是：java -jar sokoban.jar s 15 10000
经过我的计算和测试，这种关卡的尺寸最小是17*19，也就是第2个参数最小是7，最大是47。但是选7很大概率会报错，因为这个尺寸有点极限，可能会随机出来无法打乱到预定状态的初始局面。选8是比较安全的。选15运行大概需要10-20分钟（经过an版主测试，是我的电脑配置不太高，其实可以更快点）。没有尝试生成过更大的关卡。根据我的经验来看，这种关卡尺寸比较小的时候腾挪难度比较高，尺寸比较大的时候腾挪繁琐程度比较高，但是难度比较低。原因是小尺寸关卡箱子在关卡外围靠墙的部分的比例比较大，中间部分箱子比例比较小，每行和每列的箱子数也比较少，腾挪限制很大，难度比较高；反之中间部分每行和每列的箱子数比较大，腾挪难度低一些。我的建议是第二个参数选择8-15是比较合适的，不过可能有极少数情况下会失败。第二个参数超过15会非常慢，有兴趣的朋友可以研究一下更好的算法，或者可以根据Brian和Matthias的思路优化一下。

为了体现s型关卡双向通道的作用，拼了一个20603大师的指数关卡，就是下面的《蜗牛》。之所以起这个名字，是因为s型关卡的部分像一个蜗牛壳，而且s型关卡内部需要一个箱子一个箱子地腾挪，进度非常慢，像蜗牛一样。

############################
#-.-*-*-*-*-*-*-*-*-$-######
#-#-#-#-#-#-#-#-#-#-#.######
#-$-$---.-.-.-$-------*-####
#$#-#-#-#$#$#$#-#.#*#*#-####
#-.-.-*-$-$---*-*-------####
#*#$#.#*#.#.#$#*#-#$#*######
#---$-*-$-*-.-$-.-.---#-.-##
#*#.#-#-#-#-#$#.#-#$#*#-*$##
#---.-$-.-.-$---$-*---#-.-##
#*#$#.#*#.#*#*#$#-#.#*#-*$##
#-------.---$---.-$---#-.-##
#*#-#$#-#$#$#*#*#-#.#*#-*$##
#---.-*---*-*-----$---#-.-##
#*#.#$#*#.#-#.#-#*#-#*#-*$##
#-----.-*-.-$-*-$-*---#-.-##
#*#-#*#$#$#.#.#*#-#-#*#-*$##
#-----*-$-.-*-$---.---#-.-##
#*#-#-#.#-#-#.#*#$#-#*#-*$##
#---*-$-.-$-------*-.-#-.-##
#.#-#-#-#-#-#-#-#-#-#$--*$##
#-$-*-*-*-*-*-*-*-.---#**-@#
##################-###-----#
##################-----#--##
############################
Title: 蜗牛
Author: Zou Yongzhong(20603) + cjcjc

这关肯定是有解的，就是答案太长了，我在设计出来之后的几个月内都没有解开，近期刚刚解开，用了大约500万步完成，建议有兴趣的朋友试试比赛用的简化版即可。

这种S型关卡和其他结构配合还可以起到额外的效果，未来可能有一个关卡会发出来。

cjcjc

但是事实上这个结构是不成立的。因为0空位腾挪的特点，当第一行全部箱子往左移动1格之后，红色方块的位置一定是一个箱子，这个箱子不可能推走，所以最右一列的箱子没办法向上推。为了解决这个问题，我把最右一列的一个内墙改成不直接和外墙连接了。同样地，我把最下一行的一个内墙改成不直接和外墙连接了。这样一共有3个内墙不直接和外墙连接，所以通道入口和通道出口可以同时是畅通的，这样产生了一个漏洞


ps用类似的方法分析，可以看到最终完成的版本，是不存在同时把出口和入口同时打开的推法的。

cjcjc

其实最理想的情况是：只有一个内墙不直接和外墙连接，这里作为通道入口，离这个墙最远的墙作为出口，这样想要把出口的箱子挪走，需要依次把所有靠外墙的箱子按蓝色箭头的顺序挪一遍

cjcjc

分享一个新的零空位关卡：

#########################
#@$-*-*-*-*-*-*-*-.---###
#.#-#-#-#-#-#-#-#$#-#$###
#-------$-.-*---$---.-###
#*#*#$#.#.#$#$#-#*#.#*###
#-----*---$---.-$-.---###
#*#$#-#-#-#.#*#.#*#-#*###
#---.---*---$---.-$---###
#*#-#.#*#*#$#*#-#.#-#*###
#---$-.-*-*-*-.-$-----###
#*#-#*#-#-#-#$#.#*#*#*###
#---$-.-$---$---.-.---###
#*#$#$#$#*#-#*#*#$#-#*###
#---*-.-.-$-*---$-----###
#*#.#.#*#-#.#.#*#*#-#*###
#-----$-.-*-*---------###
#*#-#.#-#$#-#.#$#*#-#*###
#---*-*-------$-.-------#
#$#.#$#-#*#-#*#$#.#$#*#-#
#-*---$-$-.-.---*-----*-#
#-#-#-#-#-#-#-#-#-#-#.###
#-.-*-*-*-*-*-*-*-*-$-###
#########################
Title: 百川归海(特别版)
Author: cjcjc

209期比赛正在进行，主关的主要部分是一个特别的E型零空位关卡（简称S类关卡），下面我介绍一下这类新关卡。为了编程方便，我对关卡做了一些旋转和镜像的操作，本质是一样的，下面提到的方向请按示例图的结构来看。
思考下面的问题：零空位关卡这个结构可以起到什么作用？
我的思路是：可以做一个双向的通路。于是调整了一下随机生成关卡的代码，对E型关卡增加了一些限制。特点是：1.最外层的内墙几乎都直接和外墙连接，2.中间每行每列都至少有2个箱子，3.随机打乱时，从入口旁第一个箱子开始，把它往逆时针方向推一个位置，按顺时针顺序，把所有直接和外墙连接的箱子都逆时针推一个位置，直到把最后一列最下面的箱子往上推一个位置。这样就形成了一个大号的双向通路。

cjcjc

MatthiasM 发表于 2025-5-1 20:08
At the end of the file "YASGEN-cjcjc-b.Common Lisp.lsp" (part of the zip-file) there is a descriptio ...

感谢分享！

MatthiasM

At the end of the file "YASGEN-cjcjc-b.Common Lisp.lsp" (part of the zip-file) there is a description how to compile and start the program.
It's necessary to install a Lisp compiler first (for instance: https://sourceforge.net/projects/sbcl/files/sbcl/2.5.4/).

Then it's possible to start the compiler with: sbcl.exe
At the command prompt the program must be loaded:

1. (load "YASGEN-cjcjc-b.Common Lisp.lsp")

复制代码

Then the generator can be started, for instance with this command:

1. (make-puzzles  5 10000 60 1 "C:\\Temp\\" false)

复制代码

MatthiasM

Hi.

Brian Damgaard, the author of the program "Sokoban YASC", has written a generator for B-type levels in LISP.
With his permission, I'd like to share his email here on the forum.
Here it is:

Hi Matthias,

- Programs are poetry written for computers!

I always love saying that, and I enjoy writing miniature programs because they can beautifully demonstrate this. My cjcjc-b puzzle generator program is such a miniature program, and I enjoyed polishing it to really make it shine as "poetry".

I'd like to show you what I've made, hoping that you'll find it a bit entertaining. Attached to this email you'll find the program and its output: a puzzle file mimicking cjcjc's original puzzle file with 20 puzzles of each of the sizes 5x5, 7x7, 10x10, 15x15, and 20x20, plus a 30x30 and a 48x48 puzzle.

The file doesn't contain the underlying puzzle solutions because that would make the file impractically large. But the program is, of course, capable of producing puzzle solutions in LURD format together with its generated puzzles.

You're welcome to show the program, the puzzles, and this email to Anian and cjcjc. My hope is that they can use the material for learning and as inspiration.

________________________
Puzzle solution length

My program is much faster than cjcjc's original program, but more importantly, it generates substantially better puzzles in the sense that it – on average – produces puzzles with longer shortest solutions, counting both pushes and moves.

The difference is most pronounced for small 5x5 puzzles. Here, the difference can be as high as 84% longer puzzles (874 pushes for 20 puzzles compared to only 474 pushes).

The difference is much smaller for larger puzzles like 10x10. The difference is notable but dwindles to around 10%. I haven't been able to figure out why this is the case. I would expect my selection strategy always to be significantly better.

___________________________
Puzzle selection strategy

After making all its random pushes, cjcjc's program selects the last seen box configuration as the target. There's no inherent reason to assume that this last seen configuration has the longest puzzle solution. For instance, in theory (though highly improbable in practice), the random pushes could cycle back to the starting configuration.

My program uses a different strategy. During the random pushes, the target configuration is selected by tracking the game state that is farthest away from the initial box configuration. Again, there's no guarantee that this is the optimal selection strategy, but experiments show that it greatly increases the probability of finding puzzles with longer shortest solutions.

Furthermore, operating with the metric "farthest distance to the starting box configuration" allows the program to offer a "minimum threshold" feature. If a puzzle candidate doesn't meet this minimum threshold, it's rejected, and the program tries again with a new candidate.

______________________________________
Underlying puzzle creation algorithm

In his program description, cjcjc didn't use the technical term "minimum spanning tree" (MST), but this is actually the technical basis of the method used in the program for creating the starting box configuration.

The inner walls on the board are arranged in a grid-like pattern. Then, a random MST is generated to connect all the inner walls, and boxes are placed along the edges of the MST.

https://en.wikipedia.org/wiki/Minimum_spanning_tree

cjcjc's original program uses a home-made algorithm to generate the random MST. I preferred using the elegant Kruskal's algorithm, which is fundamentally based on a "disjoint-set" data structure.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

________________
Solver program

The big and unanswered question is whether an efficient solver program can be written for this puzzle type. There doesn't seem to be any viable strategy that can reduce the branching factor in a search algorithm to a manageable size.

____________
Conclusion

I find it interesting that this is the second time we've seen Sokoban puzzles with a surprising background. First, there were the Orimaze-based puzzles, where puzzles from a completely different game could be transformed into Sokoban puzzles. Now, we see that Sokoban puzzles can also be created from minimum spanning trees.

I wonder if there are more such welcome surprises in store for us, and for the Sokoban game!

Best regards

Brian

Sokoban Puzzles of Type cjcjc-b - Puzzles and Tools.zip (77.68 KB, 下载次数: 14)

2025-7-4 03:20:43 上传

下载次数: 14
B-type level generator Brian Damgaard (03.07.2025)

cjcjc

sokoban 发表于 2025-4-20 10:22
百川归海系列的确很有创意。内墙和箱子形成一棵支撑树（spanning tree）。目标状态又是另一棵支撑树。解关过 ...

确实是支撑树，我拿deepseek写代码的时候，ai给出了的几个算法都是支撑树的生成算法。不同类型的关卡，只是箱子运行规则不一样。例如，最简单的b型关卡的运行规则，就是箱子只能在一行或一列上运行，不能转弯，不能换行换列。

sokoban

百川归海系列的确很有创意。内墙和箱子形成一棵支撑树（spanning tree）。目标状态又是另一棵支撑树。解关过程就是两棵支撑树之间的转化。