魔方吧·中文魔方俱乐部

标题: 解法步数随关卡大小成指数增长的关卡 [打印本页]
作者: sokoban    时间: 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, 下载次数: 70)

b.jpg

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

附件: 1.jpg (2009-6-8 20:11:49, 25.43 KB) / 下载次数 113
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ0Mzl8ODU4YmM3MDB8MTcyNzQ1NDQyNnwwfDA%3D

附件: b.jpg (2009-6-8 20:11:49, 56.66 KB) / 下载次数 115
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ0NDB8ODVjMjkyZjJ8MTcyNzQ1NDQyNnwwfDA%3D

附件: exp.rar (2009-6-8 20:11:49, 247 Bytes) / 下载次数 70
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ0NDF8YTcyMDEzOTZ8MTcyNzQ1NDQyNnwwfDA%3D
作者: yq_118    时间: 2009-6-8 20:14:36

没研究过这个，应该可能有多项式时间算法吧
作者: sokoban    时间: 2009-6-8 20:16:28     标题: 回复 2# 的帖子

推箱子是 PSPACE 完全问题，基本不可能有多项式时间算法。
作者: anian    时间: 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 编辑 ]
作者: anian    时间: 2009-6-8 23:55:00

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

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

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

附件: t.png (2009-6-9 00:00:02, 98.06 KB) / 下载次数 158
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ0NTN8ZDRlNTIwNTB8MTcyNzQ1NDQyNnwwfDA%3D
作者: sokoban    时间: 2009-6-9 08:12:26

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

http://www.stetson.edu/~efriedma/mathmagic/0300.html
作者: 管窥子    时间: 2009-6-9 13:35:27

很妙，像九连环似的，每加一个环，步数加倍。
作者: jinyou    时间: 2009-6-10 22:58:21

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

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

附件: jy2_one_space424.rar (2009-6-10 22:58:21, 754 Bytes) / 下载次数 63
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ4NzV8MTI0ZWJhODV8MTcyNzQ1NDQyNnwwfDA%3D

附件: jy_one_11869.JPG (2009-6-10 22:58:21, 54.53 KB) / 下载次数 102
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ4NzZ8NGNjNmE1ODd8MTcyNzQ1NDQyNnwwfDA%3D
作者: anian    时间: 2009-6-10 23:25:45

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

Solution(pushes 86, moves 973, in-lines 85, changes 64, steps 85):
  uuullllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuulllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuulllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuulllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrrrrrrrrrrrrrrruuuuuuuuuuuuuulllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuulllllllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrrrrrrrrrrrrrrruuuuuuuuuuuuuulllldddrddldDrddlUlldlldlluuurrDlluuurrDrruuuluLdrrdddllulldddrrUlldddrrUrrdddrRurrdLddrrruuuuuuuuuuuuuullllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllllddlLdlluRdllluRuullllllddrddlUU
作者: anian    时间: 2009-6-10 23:49:52

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

[ 本帖最后由 anian 于 2009-6-11 00:05 编辑 ]
作者: jinyou    时间: 2009-6-11 08:50:03

《老封推箱子》v1.0 2002年吧
作者: sokoban    时间: 2009-6-11 09:25:24

早期比较强的推箱子程序有一个是瑞典人的 Sokoban 1.5，这是我看到的第一个用鼠标点击然后程序自动推箱子的程序。背景音乐有那首 california dreaming 的midi. 那时不知这首是什么歌，就是觉得不错，印象很深。不知什么时候开始，这个瑞典人把Sokoban 1.5升级成 Sokoban 2，同时变成shareware了，可惜了。原来免费的 Sokoban 1.5 也找不着了。

[ 本帖最后由 sokoban 于 2009-6-11 09:39 编辑 ]
作者: jinyou    时间: 2009-6-11 09:49:50

这类步数随关卡大小成指数增长的关卡，其实每一步都不能变换了（故意浪费不算），
用计算机暴力计算比较容易。
经验证，这是最优解。
作者: 管窥子    时间: 2009-6-11 10:57:01

我觉得金优先生给的关卡不是指数增长，而是线性增长。
作者: anian    时间: 2009-6-11 11:35:03

sokoban兄说的“Sokoban 1.5”应该是“Sokoban For Windows v1.5”。 那是Bjorn
Kallmark的作品。  它自动推箱子的程序不可以拐弯。
现在已经出了“Sokoban For Windows v3”。
如果需要 v1.5， 我可以寄给你或上传到这里。
作者Bjorn说v1.2版本是在十二月， 1996年推出， 当时已经有鼠标点击然后程序自
动推箱子的功能。

如果说自动推箱子的程序(不可以拐弯)， 在1997年Gerald Holler在他的
Sokoban 1997里面也有这个功能。 Gerald Holler也是后来Sokomind的作者。

其实那个时候已经有几个推箱子程序可以自动推箱子(还可以拐弯)。
如金优兄那只有一个箱子的关卡， 只有点击箱子再点击目标， 程序会自动把箱子推到
目标。

其中最流行的应该是这两个：
Sokoban YASC (Author: Brian Damgaard) 是在十二月， 2001年推出。
YSokoban (Author: George Petrov) 也是在十二月， 2001年推出。

我比较喜欢YSokoban。  它体积小， 功能强大,  不需要安装。
它记录着你所有过了关的关卡和答案。  可以避免你再玩已经过了关的关卡，无论那
个关卡是旋转了也可以记住(rotated, mirrored, any of the 8 possible orientations),  答案一目了然。
作者George Petrov写YSokoban有两大原因：
1。 他不想再玩已经过了关的关卡
2。 他觉得其它推箱子程序的路径搜查太慢。

由它推出的那一天开始， 它的路径搜查是我试过的所有推箱子程序最快的。
它的路径搜查有几个：
1。 点击箱子，  点击目标， 程序自动把箱子推到目标。
            (用者可以选择程序用最少移动或者推动步数来完成)

2。 点击“人”， 程序自动显示人可去到那里
          -- 如果再点击其中的一个可以去的地方， 程序自动把人以最少步数
             移到那个地方。

3。 显示人可以推动和不可以推动的箱子。

4。 点击目标(或任何空位)， 程序自动显示所有可以推到那个被点击的地方的箱子，
  如果再点击可以自动以最少移动或者推动步数把最近的箱子移到被点击的地方。
       (据我所知， 目前只有YSokoban 和 Sokoban YASC 支持这个功能。)

[ 本帖最后由 anian 于 2009-6-11 12:22 编辑 ]
作者: anian    时间: 2009-6-11 11:56:51

(接楼上....)
Bjorn的“Sokoban for Windows v3”路径搜查比之前的版本有很大的进步。
它的路径搜查速度很快， 比YSokoban只是慢了少许。
Sokoban YASC的速度路径搜查也很快。

以下这几关都是我用来测验一个推箱子程序路径搜查速度的：


----#--------#--------#--------#--------#--------#--------#--------#--------#----
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
--#---#----#---#----#---#----#---#----#---#----#---#----#---#----#---#----#---#--
-#-----####-----####-----####-----####-----####-----####-----####-----####-----#-
#-------##---------------#-----------#--------------#----#----------#-----------#
-#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#-
--#------------#----#---#----#---#----#---#----#---#----#---#----#---#----#---#--
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
---#--------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
--#---#----#---#----#---#----#---#----#---#----#---#--------#----#---#----#---#--
-#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#-
#-------##--------#---#----#-------##-------#--------#--------#--------#--------#
-#--------#-----#--#-----#--#-----#--#-----#--#--#--#--#-----#--#-----#--#-----#-
--#---#----#---#----#---#----#---#----#---#----#---#----#---#----#---#----#---#--
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
---#-#------#-#------#-#------#-#--------#------#-#------#-#------#-#------#-#---
---#-#------#-#------###------#-#------#-#------#-#------#-#------#-#------#-#---
--#-#-#----#---#----#---#----#---#----#---#----#--------#---#----#---#----#---#--
-#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#-
#--------#-------#--------#---------#-------#-#------#--------#--------#--------#
-#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#-
--#---#-#--#---#----#---#----#---#----#---#----#---#----#---#----#---#----#---#--
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
--#---#----#---#----#--------#---#----#---#----#---#----#---#----#---#----#---#--
-#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#-
#-------#-#-------#-------##-------#--------#-#------##-------#--------#--------#
-#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#-
--#---#----#---#----#---#----#---#----#---#----#---#----#---#----#---#----#---#--
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
---#-#------#-#------#-#------#-#------#-#------#-#--------#------#-#------#-#---
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
--#---#----#---#--------#----#--------#---#--------#----#--------#--------#---#--
-#-----#--#-----#--#-----#--#-----#--#--#--#--#-----#--#-----#--#-----#--#-----#-
#------#-#---#---#--------##-------##-------#--------##-------##-------##-------#
-#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#--#-----#-
--#---#----#---#--#-#---#----#---#----#---#----#---#----#---#----#---#----#---#--
---#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
---#-#------#-#------#--------#-#--------#------#--------#--------#-#--------#---
---#-#-#----#-#------#-#------#-#------#-#------#-#------#-#------#-#------#-#---
--#---#----#---#----#---#----#---#----#---#----#---#----#---#----#-#-#----#---#--
-#----------#---#--#--#--#--#--#--#--#-----#--#--#--####--#--#--#-----#--#-----#-
#--$$$--##--#-------------##-------##-------##----------------##-------##----#--#
-#-$---#--#-----####--------------#--#--------------####--------------#--#-----#-
###---#----#...#----#---#----#------------######---#----#---######------------#--
#--$-#------#.#------#-#######--########-#------#-#------#-#------##-----###-#---
#@--#-------#.#------###-----####------###------###------###------###----#-###---
#####-------###------------------------------------------------------#####------
Title:  beemaze
Author: Eric F Tchong
Above level is level 67 of the Atlas03 collection by Eric F Tchong.




;
##################################################
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#---------------------.-----$--------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------@-----------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
#------------------------------------------------#
##################################################



; 50x50 level of the same level below.
##################################################
#------------------------------------------------#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$+$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#-$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.$.-#
#------------------------------------------------#
##################################################

[ 本帖最后由 anian 于 2009-6-11 22:40 编辑 ]
作者: sokoban    时间: 2009-6-11 12:47:15

我试了一下啊，YSokoban 的确功能非常强大！

anian 兄设计的这几个测试关卡相当好。
作者: zhenying    时间: 2009-6-11 14:48:21     标题: 回复 11# 的帖子

jinyou兄，《老封推箱子》v1.0（boxman v1.0 ）以及其它早期的版本你有吗？
我尙有收藏的兴趣，希望得到支持。
作者: anian    时间: 2009-6-11 21:42:41

原帖由 sokoban 于 2009-6-11 12:47 发表
我试了一下啊，YSokoban 的确功能非常强大！

anian 兄设计的这几个测试关卡相当好。



关于那几个测试关卡...  第一个不是我设计的， 其他的两个是。
第一个是来自Eric F Tchong的Atlas03， 67关。
作者: jinyou    时间: 2009-6-12 11:36:42

18#
老封的早期版本我没有了。但是我觉得没有必要收集那些有许多BUG的东西。他1.85是修改已知BUG的。后来他突然大改界面，就很快升到4.0。中间几个版本都是修改界面BUG的。

14#
我画的一个箱子绝对不是线性增长，用地图大小和路程做坐标画出的绝不会是直线。当然没有达到指数级。
作者: xdgtzsyyj    时间: 2009-6-12 11:53:20

8楼的这个关卡很磨人啊，
作者: 管窥子    时间: 2009-6-12 12:03:40     标题: 回复 20# 的帖子

我觉得用地图大小和路程做坐标意义不大，就像电路中导线直接连通的地方都可以认为是一个节点，空跑的路再多也是一步，我认为用基本单元（如Sokoban兄给的“房间”）和推数为坐标更能表现这种关卡的性质。金优先生以为如何？
作者: zhenying    时间: 2009-6-12 13:08:04     标题: 回复 20# 的帖子

谢谢jinyou兄的介绍，我有点好奇想看看最初的版本是何模样。
作者: jinyou    时间: 2009-6-12 14:09:01

这样的符合指数要求吗

#############################
#  #  #  #  #  #  #  #  #   #
#.   $#.   $#.   $#.  $ #.$ #
# $#. # $#. # $#. # $#+ # $ #
#. # $#. # $#. # $#. #  #.$##
# $#. # $#. # $#. # $#*$#  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #. #
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #* #
# $#.   $#.   $#.    #. $  #
#  #  #  #  #  #  #  #  #  #
############################

lddddddddddddddrDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruuuuuuuuuuuurUldddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUluuuuuuuuuuuuuurrddLruulldDDDrUdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddlllluurDluuurDDluuuurDDluuuurDDluuuurDDluuuurDDluuuurDDluuuurDDlddddddddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDlddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDlddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDlddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDldRuuuulDruuulDruuulDruuulDruuulDruuulDruuulDlllddrUldddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUluuuuuuuuuuuuuuRRRurDDDlU…… ……30259
作者: sokoban    时间: 2009-6-12 22:27:47

jinyou 兄这一关很有意思，像是这一关的加强版。研究一下。

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

[ 本帖最后由 sokoban 于 2009-6-12 22:54 编辑 ]
作者: sokoban    时间: 2009-6-13 12:09:15     标题: 回复 24# 的帖子

Jinyou 先生贴的关卡和解法前段似乎不相符，可以重新贴一下解法的开头部分吗？

1.jpg

附件: 1.jpg (2009-6-13 12:09:15, 71.88 KB) / 下载次数 51
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTUxNjR8ZjMwYmJhZTV8MTcyNzQ1NDQyNnwwfDA%3D
作者: zhenying    时间: 2009-6-13 23:31:06     标题: 回复 26# 的帖子

Jinyou兄贴的关卡可能是这关，答案3W多步，提供解法的开头部分。
#############################
#  #  #  #  #  #  #  #  #   #
#.   $#.   $#.   $#.  $ #.$ #
# $#. # $#. # $#. # $#+ # $ #
#. # $#. # $#. # $#. #  #.$##
# $#. # $#. # $#. # $#*$#  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #. #
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #* #
# $#.   $#.   $#.    #. $  #
#  #  #  #  #  #  #  #  #  #
############################
Title: Ljy_370
Author: 李金玉
lddddddddddddddrDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruuuuuuuuuuuurUluuurrddLruulldDrruLdddlddrUUUUlDDrddlddrUUUUlDDrddlddrUUUUlDDrddlddrUUUUlDDrddlddrUUUUlDDrddlddrUUUUlDDrddlllluurDluuurDDluuuurDDluuuurDDluuuurDDluuuurDDluuuurDDluuuurDDlddddddddddddddRRRdrUUUlDuuuuuuuuuuuuurruullDDrruLdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddddddRRRdrUUUlDuuuuuuuuuuuuurruullDDrruLdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddddRRRdrUUUlDuuuuuuuuuuuuurruullDDrruLdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddRRRdrUUUlDuuuuuuuuuuuuurruullDDrruLdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDlddddddRRRdrUUUlDuuuuuuuuuuuuurruullDDrruLdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDlddddRRRdrUUUlDuuuuuuuuuuuuurruullDDrruLdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDlddRRRdrUUUlDuuuuuuuuuuuuurruullDDrruLdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDldRuuuulDruuulDruuulDruuulDruuulDruuulDruuulDlllddrUldddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUl........
作者: sokoban    时间: 2009-6-14 07:40:28     标题: 回复 27# 的帖子

多谢ChangKai 兄答疑。ChangKai 兄贴的似乎和 jinyou 兄的是一样的。这一关的图如26楼所示。“人”的左边是墙，但是解法的第一步是 l，我百思不得其解。
作者: anian    时间: 2009-6-14 07:50:56

原关应该是这个：

#############################
#-@#--#--#--#--#--#--#--#---#
#.$---#.$---#.$---#.$---#.$-#
#--#.$#--#.$#--#.$#--#.$#---#
#.$#--#.$#--#.$#--#.$#--#.$##
#--#.$#--#.$#--#.$#--#.$#--#-
#.$#--#.$#--#.$#--#.$#--#.$#-
#--#.$#--#.$#--#.$#--#.$#--#-
#.$#--#.$#--#.$#--#.$#--#.$#-
#--#.$#--#.$#--#.$#--#.$#--#-
#.$#--#.$#--#.$#--#.$#--#.$#-
#--#.$#--#.$#--#.$#--#.$#--#-
#.$#--#.$#--#.$#--#.$#--#.$#-
#--#.$#--#.$#--#.$#--#.$#--#-
#.$#--#.$#--#.$#--#.$#--#.$#-
#--#.$#--#.$#--#.$#--#.$#--#-
#.$#--#.$#--#.$#--#.$#--#.$#-
#--#.$---#.$---#.$---#.$---#-
#--#--#--#--#--#--#--#--#--#-
############################-
Title:改编后的恐怖型115
Author:李金玉

[ 本帖最后由 anian 于 2009-6-14 08:06 编辑 ]

附件: t.jpg (2009-6-14 07:56:37, 65.55 KB) / 下载次数 60
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTUyODV8YmU4YzRjMmR8MTcyNzQ1NDQyNnwwfDA%3D
作者: sokoban    时间: 2009-6-14 08:12:31

多谢 anian 兄，这下我明白了。
作者: zhenying    时间: 2009-6-14 10:57:53

原帖由 sokoban 于 2009-6-14 07:40 发表
多谢ChangKai 兄答疑。ChangKai 兄贴的似乎和 jinyou 兄的是一样的。这一关的图如26楼所示。“人”的左边是墙，但是解法的第一步是 l，我百思不得其解。


粗心所致，导出的原关卡与jinyou兄的弄混，对不起sokoban兄了。
同样是李金玉的这一关，答案大约要10W。
################################
#  #  #  #  #  #  #  #  #  #   #
#  #.$   #.$   #.$   #.$   #.$ #
#.$#  #.$#  #.$#  #.$#  #.$#   #
#  #.$#  #.$#  #.$#  #.$#  #.$##
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$#  #.$#  #.$#  #.$#  #.$#  #
#  #.$#  #.$#  #.$#  #.$#  #.$#
#.$   #.$   #.$   #.$   #.$   #
# @#  #  #  #  #  #  #  #  #  #
###############################
Author: 李金玉
作者: sokoban    时间: 2009-6-14 11:45:42

多谢 ChangKai 兄。这一关假设有 n 个箱子的话，推动数大概是 n^2 数量级。

[ 本帖最后由 sokoban 于 2009-6-14 15:43 编辑 ]
作者: jinyou    时间: 2009-6-14 19:29:42

对不起粗心了.
题目是我贴的答案演示到省略号时的图案.
作者: jinyou    时间: 2009-6-15 16:23:35

又找到一题
level 0
#####
# + ##
##$.$ #
#  *  #
#  *  #
##  ###
####  
level 1
#####
# + #
#$.$#
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  
level 2
#####
# + #
#$.$#
# * #
# * #
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  
level 7
#####
# + #
#$.$#
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  

每一级增加两个箱子，只能是偶数个，奇数个无解

level0="rDrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

level1="rDDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

level2="rDDDLUdrDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuuuullDDRUldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUdrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

box=2X+4=箱子个数
X|box | Total Pushes |   Total Moves |
0|  4 |           15 |            48 |
1|  6 |           57 |           170 |
2|  8 |          167 |           494 |
3| 10 |          455 |         1,346 |
4| 12 |        1,209 |         3,580 |
5| 14 |        3,183 |         9,432 |
6| 16 |        8,351 |        24,756 |
7| 18 |       21,881 |        64,878 |
8| 20 |       57,303 |       169,922 |
9| 22 |      150,039 |       444,934 |
10| 24 |      392,825 |     1,164,928 |
11| 26 |    1,028,447 |     3,049,900 |
12| 28 |    2,692,527 |     7,984,824 |
13| 30 |    7,049,145 |    20,904,626 |
14| 32 |   18,454,919 |    54,729,110 |
15| 34 |   48,315,623 |   143,282,762 |
16| 36 |  126,491,961 |   375,119,236 |
17| 38 |  331,160,271 |   982,075,008 |
18| 40 |  866,988,863 | 2,571,105,852 |
19| 42 |2,269,806,329 | 6,731,242,614 |

这个比较象九连环
以下用FOXPRO写了一个解法计算程序(仅对此题)，从用到两重循环可知，一定是指数级的。

************
set talk off
clear

maxn=9
DIME sa[10],sb[10],sc[10],sz[10]
*Sc[0]=""
*Sa[0]=""
Sa[1]="DDLUdr"
*Sb0="LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
Sc[1]="LUdrruulDlddlUluRuuurrDDLUdrrddL"
Sb[1]="LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"+ "LUlldRdrUrruulDuu" + "uu" +"ll" +"DDRUld" +"DDRUdddlUluRurrrddL"+ Sc[1]+ "LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"
Sz[1]="rD"+Sa[1]+ "rddl" +Sb[1] + "UruL"

for n=2 to maxn

  Sa[n]=fm("DDLUdr",n)
  Sc[n]="LUdrruulDlddlUluRu" + fm("uu",n) +"rr"+ Sa[n] + "rddL"
  Sb[n]=Sb[n-1] +"LUlldRdrUrruulDuu" + fm("uu",n) +"ll" +fm("DDRUld",n) +"DDRUdddlUluRurrrddL"

  *Sb[n]=Sb[n] +Sc[1] +Sb[0]
  Sb[n]=Sb[n] +Sc[1] +"LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
  FOR j=2 to n
    Sb[n]=Sb[n] +Sc[j] +Sb[j-1]
  next
  Sz[n]="rD"+Sa[n]+ "rddl" +Sb[n] + "UruL"

  _cliptext=Sz[n]
  ?"level","box","move and push"
  ?      n,n*2+4, len(Sz[n])
  wait
next

return

func fm(fs,fm)
fss=""
if fm>=1 then
        for fi=1 to fm
                fss=fss+fs
        next
endif
return fss
***********

[ 本帖最后由 jinyou 于 2009-6-15 16:26 编辑 ]
作者: anian    时间: 2009-6-17 21:42:08

谢谢jinyou兄！ 不知道你的计算程序要用多少时间才算出100个箱子的推动和移动。
  我对FOXPRO不认识， 不然我就自几试试。
作者: jinyou    时间: 2009-6-19 08:40:28

我的程序只算了十几个箱子．１００个箱子答案长度比魔方的可能状态数还多，我这种字符串累加方法，怎么能用，要是只计算长度那是很快的．极限(L[n+1]/L[n])=2.618=(((根号5)+1)/2) * (((根号5)+1)/2) （n 对应的箱子数=2*n+4） 就是每加两个箱子将增加 黄金比例平方倍 。
作者: xxx821006    时间: 2009-7-21 10:12:43

31楼的关卡我有答案 50355/23300
作者: migl    时间: 2009-7-21 14:41:06     标题: 回复 37# 的帖子

你给打了五折
作者: sokoban    时间: 2009-7-21 16:13:44     标题: 回复 37# 的帖子

欢迎37楼的新朋友
作者: jinyou    时间: 2009-7-22 08:46:47

37楼朋友说的对，是这个数。50355四舍五入就是10万。
作者: xxx821006    时间: 2009-7-23 15:15:48

我个人不喜欢这个类型的关卡，将推箱子变成了体力活！
其实适当简化一下，表达出关卡的难点和原理就可以了。
作者: sokoban    时间: 2009-7-23 15:22:05

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

不过这类关卡拿来分析，计算一下步数和箱子数之间的关系，倒有点意思。
作者: 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
我是慕名而来的~
借帖求问高手是否可能设计单个箱子情况下
推箱子的解法步数和关卡大小可以是指数关系？
...

一个箱子不可能是指数关系。
作者: shamy    时间: 2015-3-10 11:02:48

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

2个箱子可以吗？
作者: sokoban    时间: 2015-3-13 09:17:20

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

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



欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) Powered by Discuz! X2