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

sokoban

欢迎37楼的新朋友

sokoban

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

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

sokoban

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

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

sokoban

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

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

sokoban

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

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