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

sokoban

西北天狼 发表于 2013-7-14 23:19
看了sokoban版主的博客，又认真研究了一下Fobinacci数列的通项公式，根据递推公式
M(2n)=3M(2n-2)-M(2n-4) ...

和天狼兄的计算结果吻合，看来我的计算没有出错。

西北天狼

1#的47×49关卡，试图打造50×50以内的最强关卡，显然还有一些空间可以利用。
以下关卡的设计，目的在于挑战50×50以内关卡的移动步数极限。
##################################################
###  #@ . #    #   . ###      . ##  #   . #    ###
# $.  #$.$# * .* #$.$# *. * #$.$#   * #$.$# * .* #
#  *  # * ##  $  # * #  $  ## * #  *  # * ##  $  #
#  * ## * $.# *  # * #  * #.$ * ## *  # * $.# *  #
## * #  * #.$ * ## *  # * $.# *  # * #  * #.$ * ##
## * #  $  ## * #  *  # * ##  $  # * #  $  ## * ##
##$.$# *. * #$.$#   * #$.$# * .* #$.$# *. * #$.$##
## .   #      . ##  #   . #    #   . ###      . ##
##################################################

Title: 九龙行测试(3831/1104)
Author: 西北天狼



关卡高度        移动步数        推动步数
10        3831         1104
12        10103         2964
14        26509         7824
16        69447         20538
18        181847         53814
20        476101         140922
22        1246455         368964
24        3263255         965976
26        8543293         2528964
28        22366599         6620910
30        58556471         17333754
32        153302773         45380334
34        401351799         118807224
36        1050752567         311041308
38        2750905837         814316664
40        7201964871         2131908642
42        18854988695         5581409214
44        49363001125         14612318946
46        129234014583         38255547564
48        338339042519         100154323680
50        885783112861         262207423404

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

Title: 九龙行八千亿(885783112861/262207423404)
Author: 西北天狼

20603

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

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

吉菜

好难理解呀

2490715998

雷蛤谁弄了

anian

20603 发表于 2013-7-28 08:35
天狼兄和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-7-31 17:12
　　很多年前做的研究，具体关卡已经不记得了，重新还原发现有漏洞，但思路表达出来了：

############## ...

将两种指数型关卡叠加，实在是妙招，步数难以计数。
先从小型的算起，慢慢理解吧：）