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

sokoban

在最坏的情况下，推箱子的解法步数和关卡大小（或者箱子数）的可以是指数关系。

下面举一个例子，不知道还有没有别更简单的例子。这个例子是我从别处看来的，原始地址一时找不着了。

我们构造一系列推箱子关卡L(n)，每个关卡的大小(指的是长乘于宽)是S(n)=(10+13n) x 17，然而解答所需要的推数是P(n)=2+12*(2^n-1)，这相对于关卡的大小是成指数增长的。

L(1)如下图所示。我们注意到只有左上角的一个箱子没有归位。而且这个箱子一定只能作为最后一个被归位的箱子，因为归位后，仓库管理员就被困在左上角出不来了。要把左上角的箱子归位，仓库管理员必须经过图中用红箭头指示的三个“门”所围成的“房间”。这个房间里面的箱子都是已经归位了的，所以只能把某些箱子推离再推回原位。

对于仓库管理员来说，只能通过右上角的门进入房间。容易看出，仓库管理员必需两次从右上角进入这个房间。第一次进入后，绕一个大弯把房间里左上角的箱子向左推一格，把中间的箱子归位后，再从下面的门出来。第二次则不用绕弯直接从上面通过房间，然后从左上角的门出去。第一次进入房间要推9下，第二次要推3下。






L(n)就是在L(1)的基础上，把中间的房间复制n份连起来。这样从左到右每个房间分别要进入2次、4次，8次... 2^n次。下图是L(3)。

exp.rar (247 Bytes, 下载次数: 71)

2009-6-8 20:11:49 上传

下载次数: 71

[ 本帖最后由 sokoban 于 2009-6-10 23:34 编辑 ]

yq_118

没研究过这个，应该可能有多项式时间算法吧

sokoban

推箱子是 PSPACE 完全问题，基本不可能有多项式时间算法。

anian

可能是exp关卡设计不是很完善的缘故， 这个关卡的答案不一定如sokoban兄说的那样走。


Solution(pushes 86, moves 795, in-lines 72, changes 55, steps 72):
  uuulllllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuulllllllldddddDDrddlUUdlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllddrddlUU

Solution(pushes 106, moves 743, in-lines 70, changes 55, steps 70):
  uuulllllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuullllllllddddddDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuulllllllldddddDDrddlUUdlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrurrUUUUUUlLdlluRdllluRuullllllllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuullllDDDDDDDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllddrddlUU

[ 本帖最后由 anian 于 2009-6-9 01:15 编辑 ]

anian

如果将关卡改变一点就没有问题了:

#########--###########--###########--############
#-------#--#---------#--#---------#--#----------#
#.#####-####-#######-####-#######-####-###-####-#
#--#-#--*-*--##---#--*-*--##---#--*-*--##--#-#--#
#$-#-#-----#--#---#-----#--#---#-----#--#--#-#-@#
#--#-#####-##-#---#####-##-#---#####-##-#--#-#--#
####-#---#-#--#---#---#-#--#---#---#-#--#--#-####
-----#-#*--#-##---#-#*--#-##---#-#*--#-##--#-----
-----#---###*-#---#---###*-#---#---###*-#--#-----
-----#--*#----#---#--*#----#---#--*#----#--#-----
-----#-#---#--#---#-#---#--#---#-#---#--#--#-----
-----#---#-#####--#---#-#####--#---#-#####-#-----
-----#####-#---#--#####-#---#--#####-#---#-#-----
---------#--*--#------#--*--#------#--*--#-#-----
#############-############-############-##-######
#-----------------------------------------------#
#################################################

[ 本帖最后由 anian 于 2009-6-9 00:00 编辑 ]

sokoban

这个失误主要在我。原文是只有一个房间，没有什么问题。但是把多个房间拼起来，就有问题了。

http://www.stetson.edu/~efriedma/mathmagic/0300.html

管窥子

很妙，像九连环似的，每加一个环，步数加倍。

jinyou

三个房间结合的新题目，和对应答案能上传吗

我喜欢一个箱子。
想当初《老封推箱子》是我找到的，第一个能只搬一下，就自动完成任务的程序。同期洋程序只支持2500步，不能用。
jy2_one_space424.rar (754 Bytes, 下载次数: 64)

2009-6-10 22:58:21 上传

下载次数: 64

anian

三个房间结合的新题目答案:

Solution(pushes 86, moves 973, in-lines 85, changes 64, steps 85):
  uuullllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuulllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuulllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuulllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrrrrrrrrrrrrrrruuuuuuuuuuuuuulllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuulllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuulllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllddrddlUU

anian

我对《老封推箱子》的历史认识不多，尤其是v1.85版本之前的。
不知道金优兄说的“同期”是指那一年。

[ 本帖最后由 anian 于 2009-6-11 00:05 编辑 ]