解法步数随关卡大小成指数增长的关卡

xxx821006

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

sokoban

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

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

skyivben

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

sokoban

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

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

yyhandsome

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

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

sokoban

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

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

shamy

sokoban 发表于 2015-2-17 12:50
一个箱子不可能是指数关系。

2个箱子可以吗？

sokoban

shamy 发表于 2015-3-10 11:02
2个箱子可以吗？

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