百度贴吧推箱子关卡移动步数推算

20603

天狼兄和sokoban版主的计算都很精彩，受教了！

　　我早年也研究过此类关卡，如果要打造50×50以内的最小移动极限，除了在横向上复制，还有别的扩展方法，可以使最小移动步数远超万亿。可惜当年编的关卡已经丢失。最近若有时间我会把思路整理一下贴出来，供抛砖引玉。

20603

　　如果是横向简单复制，其移动步数只能算术级地增长，50×50的仓库内，倍数最多为9，即使在多余空位上做些变化，也是增长有限。但若初始关卡用这一关：
--#####-
--#-+-#-
--#$.$#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
--#-*-#-
###-*-#-
#---*-##
#-#-*--#
#--$.--#
####--##
---#####




就可以使整个指数增长的基数发生变化，这个基数可以远超9倍。比如这一关：

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





　　同样是横向复制，只是初始关卡做了改变，结果完全不同（这一关仅最右侧一列已经超过万亿步，左侧7列可以不计）。由于时间匆忙这一关未进行合理规划，步数并不算多，但这个思路是可以扩展的，左边7列可以互相嵌套或互相利用空间增加基数，结果需要进行精确计算。

20603

　　这个思路如何更好地扩展？再举如下一关例：

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





　　这一关就比上面那关扩展得更好，步数更多，而且收尾难度增大许多。有兴趣的可以计算一下步数，可能在4万亿上下（抱歉，关卡制作匆忙，可以增加零碎步数的地方还有很多，这里就不精雕细琢了）。关卡名字待定。
　　其实关卡左侧45×50的大空间内，可以任意发挥想象，设计出比这一关步数多得多的方案。我早年研究时设计出来的关卡已经丢失了，但设计方向还记得。用下面这关来做说明：

20603

　　很多年前做的研究，具体关卡已经不记得了，重新还原发现有漏洞，但思路表达出来了：

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






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




　　原先设计的关卡，推最右列需要10亿次以上经过N46/48的循环路径，每次从N46出去时，都必须将中间一列全部完成，每次从N48回来时，都必须将中间一列还原到初始，才能确保过关。也就是说，单单中间这一列，就要完成10亿次以上（每次25亿步）！而这个图形才利用了19×50的空间，如果在50×50的空间内互相嵌套设计，那么移动步数极限是多少？

　　可惜原设计关卡已经记不起，这个根据印象临时还原的关卡有个漏洞。

20603

西北天狼 发表于 2013-8-2 13:06
29#的叠加如果成立，将要逆天了。可惜还有漏洞，中间的一列被穿越了，不知03兄能否炼石补天！
28#的右下局 ...

　　你的改编很好！“黄金隧道”名字也不错，左侧大空间的木箱是锁链式推动的，用“黄金链道”如何？
　　这关如果不考虑趣味性和难度，还有许多值得改进和增加步数的地方，比如木箱行数的第3、5、7、9、11行，都可以将点位移到对面（即移下来，只移点位，木箱位置不变）。当时估算这关大概在4万亿步左右，后来粗算了一下，估算低了，实际步数还要多。

　　29#的设计漏洞我尝试了几十种方案都未能解决，记得以前设计的关卡是解决了漏洞的，当时也是测试了各种方案后确立了一种方案，也许是当年测试得比较马虎，现在中间列完全推好再复原几乎不能实现。也许可以实现部分推好再还原，避免直接穿越。也可以把中间列完全放弃改成别的关卡样式，可以做到完全推好再完全还原，但步数就大打折扣了（当然还是很惊人的天文数字）。

20603

西北天狼 发表于 2013-8-9 10:36
为了获得更长的回路，必须考虑让步数能指数型增长，先看下图。

要通过上面的房间一次，必须走下面的房间 ...

很好！


　　Sokoban版主曾经贴过这个指数关卡：

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



　　
　　双指数关卡无疑是关卡步数爆炸式增长的关键，我在29#楼的双指数关卡由于有漏洞，也曾用Sokoban贴的这个指数关卡来设计，试图超过亿亿步，无奈怎么处理都只是接近而没能达到亿亿步，故没有贴出来。后来换用了另一个底为4的指数式增长方式，步数达到2000亿亿步！由于关卡还比较粗糙，可以优化的地方还很多，暂不贴出，待以后有空慢慢处理细节后再贴出来。

20603

shamy 发表于 2013-8-13 10:19
总感觉有个问题，4149092853620561步，每步1字节，大概需要3.6EB？
难道我算错了？
2000亿亿步，需要17 Z ...

以千为进制的数字单位依次为K、M、G、T、P、E、Z……

1T=1万亿
1P=1000万亿
1E=100亿亿
1Z=10万亿亿

　　你那个算法往后多算了一个单位，还没到ZB的级别。

　　不过离ZB的数量级已经不远了，经过若干次推倒重来的编排设计，现在50*50关卡的最优移动步数已经达到5万亿亿步，远超我在29楼的双指数设计步数。

20603

shamy 发表于 2013-8-18 14:37
求五万亿亿步的关卡……超乎了想象……

别着急，等五万亿亿步成为可以忽略不计的零头时，再贴出来也不迟。

对了，前面没写全，Z后面的数字单位是什么？

1T=1万亿
1P=1000万亿
1E=100亿亿
1Z=10万亿亿
1Y=1亿亿亿=1×10^24=1000000000000000000000000