魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 488092|回复: 47

解法步数随关卡大小成指数增长的关卡 [复制链接]

Rank: 7Rank: 7Rank: 7

积分
5262
帖子
3216
精华
19
UID
13140
性别

论坛建设奖 八年元老

发表于 2009-6-8 20:11:49 |显示全部楼层
在最坏的情况下,推箱子的解法步数和关卡大小(或者箱子数)的可以是指数关系。

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

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

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

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



1.jpg



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

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

b.jpg


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

Rank: 4

积分
1843
帖子
1468
精华
1
UID
79281
性别

四年元老

发表于 2009-6-8 20:14:36 |显示全部楼层
没研究过这个,应该可能有多项式时间算法吧

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5262
帖子
3216
精华
19
UID
13140
性别

论坛建设奖 八年元老

发表于 2009-6-8 20:16:28 |显示全部楼层

回复 2# 的帖子

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
2010
帖子
1577
精华
3
UID
91928
性别
保密

超级搬运工 六年元老

发表于 2009-6-8 23:46:58 |显示全部楼层
可能是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 编辑 ]

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
2010
帖子
1577
精华
3
UID
91928
性别
保密

超级搬运工 六年元老

发表于 2009-6-8 23:55:00 |显示全部楼层
如果将关卡改变一点就没有问题了:

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

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5262
帖子
3216
精华
19
UID
13140
性别

论坛建设奖 八年元老

发表于 2009-6-9 08:12:26 |显示全部楼层
这个失误主要在我。原文是只有一个房间,没有什么问题。但是把多个房间拼起来,就有问题了。

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

使用道具 举报

红魔

管中窥豹

Rank: 4

积分
1403
帖子
1109
精华
4
UID
802
性别

魔方破解达人 超级搬运工 十四年元老

发表于 2009-6-9 13:35:27 |显示全部楼层
很妙,像九连环似的,每加一个环,步数加倍。

使用道具 举报

Rank: 8Rank: 8

积分
1918
帖子
588
精华
5
UID
145
性别

魔方破解达人 八年元老

发表于 2009-6-10 22:58:21 |显示全部楼层
三个房间结合的新题目,和对应答案能上传吗

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
2010
帖子
1577
精华
3
UID
91928
性别
保密

超级搬运工 六年元老

发表于 2009-6-10 23:25:45 |显示全部楼层
三个房间结合的新题目答案:

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
2010
帖子
1577
精华
3
UID
91928
性别
保密

超级搬运工 六年元老

发表于 2009-6-10 23:49:52 |显示全部楼层
我对《老封推箱子》的历史认识不多,尤其是v1.85版本之前的。
不知道金优兄说的“同期”是指那一年。

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 22:03

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部