指数转弯关卡的研究以及50见方内极限最优移动步数关卡的设计

cjcjc

根据此规律，我对《宇宙旋风》做出了一点改进（还修改了几个箱子和小人的起始位置，另一种布局展示在附录中）：

##################################################
##############################################--##
#-----------------------------------------------##
#--********************************************-##
##-*------------------------------------------*-##
##-*-########################################-*-##
##-*-##################################--####-*-##
##-*-#------------------------------------###-*-##
##-*-#--*********************************-###-*-##
##-*-##-*-------------------------------*-###-*-##
##-*-##-*-#############################-*-###-*-##
##-*-##-*-########################--###-*-###-*-##
##-*-##-*-#--------------------------##-*-###-*-##
##-*-##-*-#--***********************-##-*-###-*-##
##-*-##-*-##-*---------------------*-##-*-###-*-##
##-*-##-*-##-*-###################-*-##-*-###-*-##
##-*-##-*-##-*-##############--###-*-##-*-###-*-##
##-*-##-*-##-*-#----------------##-*-##-*-###-*-##
##-*-##-*-##-*-#--*************-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-----------*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-#########-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-####--###-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-#-$----##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-#+.***-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-#-$--*-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-####-*-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-####-*-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-####-*-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-####-*-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*-####-*-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-*------*-##-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-********--#-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##-----------#-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##--##########-*-##-*-##-*-###-*-##
##-*-##-*-##-*-##############-*-##-*-##-*-###-*-##
##-*-##-*-##-*----------------*-##-*-##-*-###-*-##
##-*-##-*-##-******************--#-*-##-*-###-*-##
##-*-##-*-##---------------------#-*-##-*-###-*-##
##-*-##-*-##--####################-*-##-*-###-*-##
##-*-##-*-########################-*-##-*-###-*-##
##-*-##-*--------------------------*-##-*-###-*-##
##-*-##-****************************--#-*-###-*-##
##-*-##-------------------------------#-*-###-*-##
##-*-##--##############################-*-###-*-##
##-*-##################################-*-###-*-##
##-*------------------------------------*-##--*-##
##-**************************************--#--*--#
##-----------------------------------------#-*---#
##--##########################################--##
##################################################
Title: 宇宙旋风
Author: 闲(XIAN) + cjcjc



由类似的方法计算这一关的最优移动至少是3.3*10^61，这个数字偏差同样会非常非常大。

cjcjc

最后写一段我的反思：这种结构看上去好像不那么复杂，为啥我当时研究这个问题的时候没有设计出来呢？我觉得有下面几个原因：第一是当时我的半位腾挪水平不够，理论也不够，我记得我设计出类似的结构，但是半位奇偶性不同，合成一个完整的空位了，然后有点想当然，没有进行更多的研究，就换了其他的思路；第二是优化水平不够，我设计了一些结构，按我自己的答案看上去还挺像一回事的，优化一下发现压根不是按照fibo关卡那样运作的，答案也只是线性增加，如果优化水平够的话应该能更早发现问题，少做无用功；第三是对fibo关卡的认识太少，想法有点刻板。我对fibo关卡的认识基本上来自最简单的结构，也就是《上》的那种结构，我自己总结的几个特点是：1.可以扩展任意数量的箱子，奇数个偶数个都可以；2.中间的箱子可以向上运行，两侧的箱子可以向下运行（我期望转弯的结构也是这样的），如图所示（右图无解，是我期望的示意图）：

  

3.是n个箱子的关卡，走法中会包括n-1和n-2个箱子的走法，再加上一些简单的通用步骤；4.是至少要有2个半位，半位越多，腾挪越容易，设计更有可能出漏洞。事实上我一开始总结的这四点都不太对，1和2由这次闲兄的设计来看明显是不对的，同样的起始结构、转弯结构和转弯方向时，要在中间边和起始边加箱子，必须增加偶数个；箱子在外侧可以向下运行，在内侧则不行。3大致正确，但是在转弯处的腾挪又有一些不同。而且每转一次弯就增加一个半位的设计和4更是矛盾的，而且也有其他的fibo关卡设计只有一个半位（见附录）。各种原因综合起来导致我没成功。

cjcjc

虽然还没完全确定，但是如an版主所说，这已经是目前最好的转弯版本了。闲兄的实力大家有目共睹，半位腾挪的功力尤其高，同时富有创造力，不断设计出精彩的关卡，实在是令我感到佩服。如果这个设计的最优移动的指数增长性得到了确认，指数关卡转弯这一大难题就正式得到解决，50*50内极限最优步数问题也会得到突破性的进展，可以说是意义非凡（03大师和天狼大师的指数关卡嵌套思路是用下方回路通过次数乘左侧的指数关卡步数来估算总步数，那个设计难度非常高，极富启 发性，而且我甚至觉得是种艺术了；这个设计如果成立相当于直接用多个指数关卡的步数相乘，相比来说最后的步数会更大）。

cjcjc

如果哪位箱友可以给出严格的有解的证明，指数增长性的证明，更准确的最优移动估计，更好的设计，或者其他的想法，希望能够分享，十分感谢。

感谢闲兄、an版主、20603大师、st群主和杨版主等各位大佬的分享和意见。

cjcjc

附录1：主关的简化关卡

-------#####-
########---#-
#----------##
#--********-#
##-*--------#
-#-*-####--##
-#-*-#--####-
-#-*-#-------
-#-*-#-------
-#-*-########
-#-*------$-#
-#-*******.+#
-#--------$-#
-##--########
--####-------
Title: 铁索连环c
Author: 闲(XIAN)



-------####-
########--##
#----------#
#--******--#
##-*----*-##
-#-*-##---#-
-#-*-######-
-#-*-######-
-#-*----$-#-
-#-******+#-
-#--------#-
-##--######-
--####------
Title:铁索连环-简化
Author:闲(XIAN)

cjcjc

附录2：我收集的一些指数关卡

#######
##-.-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
##-*-##
#@-*-##
#--$--#
#-*-*-#
###--##
#######
Title: 巴黎铁塔
Author: 20603



-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
Title: Big Hano?
Author: Aymeric du Peloux



#######
##@.-##
##$.$##
##-*-##
##-$.-#
#--*--#
#---*-#
##--###
#######
Title: 696 set level 431
Author: Dries De Clercq



这三关的结构是最简单的指数关卡结构之一，不知道谁先谁后，都在此展示。杨版主和天狼大师早前可能也设计出类似的结构，但是我没收集到有关资料。可能也有我不知道的同样的设计。《铁索连环-上》也是这种结构。

cjcjc

########
###-.-##
###-*-##
#---*-##
#@#-$--#
#--*-*-#
####--##
########
Title: WV277
Author: 20603



和上面的关卡稍有不同，左侧增加一个墙，构成一个小通道，是之前的指数嵌套关卡的关键设计。值得注意的是，根据论坛的资料，03大师先设计了有墙的结构，再去掉墙获得了没墙的结构。

cjcjc

-#####-
-#-.-#-
-#$+$#-
-#-*-##
##-*--#
#--*--#
#----##
##--##-
-####--
Title: Cosmonotes 14
Author: Aymeric du Peloux



-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
-#-*-##
##-*--#
#--$--#
#--.-##
##--##-
-####--
Title: Anchor
Author: Aymeric du Peloux



上面的两关属于另一种最简单的指数关卡结构，这两关基本上等价，不知道哪个在先，都在此展示。可能也有我不知道的同样的设计。《铁索连环-下》的简化版本和此结构有相似之处，不知道算不算等价结构。

cjcjc

-#####--
-#-+-#--
-#$.$#--
-#-*-#--
##-*-###
#-.$---#
#$-$..-#
#.--$-##
#-$.-##-
######--
Title: 696 set level 249
Author: Dries De Clercq



-#####--
-#-+-#--
-#$.$#--
-#-*-#--
-#-*-#--
##-*-#--
#-.$-##-
#-.$--##
#--*-*-#
#-$.---#
########
Title: 696 set level 250-改
Author: Dries De Clercq



-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
##-*-#-
#-.$-##
#--*--#
#-.$--#
#-.$-##
######-
Title: 696 set level 251-改
Author: Dries De Clercq



-#####-
-#@.-#-
-#$.$#-
-#-*-#-
##-*-#-
#-.$-##
#--*--#
#-*---#
#-*--##
######-
Title: 696 set level 252
Author: Dries De Clercq



-#####---
-#-+-#---
-#$.$#---
-#-*-#---
-#-*-#---
-#-*-##--
##-$.-##-
#-$.---##
#---.$*-#
####----#
---######
Title: 696 set level 692
Author: Dries De Clercq



########
##-+-###
##$.$###
##-*-###
##-*-###
##-*-###
##-*-###
#--*---#
#--*-.-#
##--$-##
###--###
########
Title: 696 set level 693
Author: Dries De Clercq



########
##-+-###
##$.$###
##-*-###
##-*-###
##-*-###
##-*-###
#--$-###
#--*--##
##-.-*-#
###----#
########
Title: 696 set level 694
Author: Dries De Clercq



696这几个关卡都比较简单，推起来感觉差不多。

cjcjc

--#######
--#-----#
--#-###-#
--#-+-#-#
--#-*$#-#
--#-*-#-#
--#-*-#-#
--#-*-#-#
###-*-#-#
#---*---#
#-*****-#
#-----*-#
###--####
--####---
Title:
Author: anian



--#####-
--#-+-#-
--#-*$#-
--#-*-#-
--#-*-#-
-##-*-#-
##--*-#-
#---*-#-
#-*-*-##
#-*-*--#
#-*----#
########
Title:
Author: 闲(XIAN)



--#######
--#-----#
--#-###-#
--#-+-#-#
--#-*$#-#
--#-*-#-#
--#-*-#-#
-##-*-#-#
##--*-*-#
#---*-*-#
#-###---#
#---#*###
###---#--
--#####--
Title:
Author: 闲(XIAN)



--#######
--#-----#
--#-###-#
--#-+-#-#
--#-*$#-#
--#-*-#-#
--#-*-#-#
--#-*-#-#
--#-*-#-#
###-.-#-#
#-*$.-*-#
#-#-.$*-#
#-#**$--#
#------##
########-
Title:
Author: 闲(XIAN)



上面这四关都是我截取下来的关卡的局部，所以没有名字。除了第二关外，其它三关都只有一个半位，但是有一个辅助的大通道。第四关的最优移动可能不是指数增长，我没仔细验证。