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

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

YASGEN-cjcjc-b.zip (32.29 KB, 下载次数: 2)

昨天 02:51 上传

下载次数: 2
B-type level generator Brian Damgaard

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)

复制代码