论坛 › ★ 推箱子 (Sokoban) › 解法步数随关卡大小成指数增长的关卡

xxx821006 发表于 2009-7-23 15:15:48

我个人不喜欢这个类型的关卡，将推箱子变成了体力活！
其实适当简化一下，表达出关卡的难点和原理就可以了。

sokoban 发表于 2009-7-23 15:22:05

说的有理，这类关卡很少有人能真的动手解一遍。解个简化版就足够了 :lol

不过这类关卡拿来分析，计算一下步数和箱子数之间的关系，倒有点意思。

skyivben 发表于 2012-4-21 16:31:17

非常有趣的关卡。学习了。

sokoban 发表于 2012-7-31 14:52:37

把34楼 Fibo 系列关卡和它的变形的分析写成了一篇博客文章：

http://sokoban.ws/blog/?p=430

yyhandsome 发表于 2015-2-12 23:16:47

我是慕名而来的~
借帖求问高手是否可能设计单个箱子情况下
推箱子的解法步数和关卡大小可以是指数关系？

只看到jinyou提供的步数大约是平方关系

sokoban 发表于 2015-2-17 12:50:46

yyhandsome 发表于 2015-2-12 23:16 static/image/common/back.gif
我是慕名而来的~
借帖求问高手是否可能设计单个箱子情况下
推箱子的解法步数和关卡大小可以是指数关系？
...

一个箱子不可能是指数关系。

shamy 发表于 2015-3-10 11:02:48

sokoban 发表于 2015-2-17 12:50 static/image/common/back.gif
一个箱子不可能是指数关系。

2个箱子可以吗？

sokoban 发表于 2015-3-13 09:17:20

shamy 发表于 2015-3-10 11:02 static/image/common/back.gif
2个箱子可以吗？

不能限制箱子数目。因为箱子数目限定了的话，比如只有不超过k个箱子（k是一个常数，比如2），关卡大小是n个格子。那么总状态数是 n^k 数量级，也就是说顶多是n的一个多项式步长，不可能达到指数步长。

查看完整版本: 解法步数随关卡大小成指数增长的关卡