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

cjcjc

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

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

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)

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)

复制代码

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 ...

感谢分享！

cjcjc

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

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

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

cjcjc

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

cjcjc

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


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

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型关卡和其他结构配合还可以起到额外的效果，未来可能有一个关卡会发出来。