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

cjcjc

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



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

cjcjc

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

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



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



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



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

cjcjc

附录1：主关的简化关卡

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



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

cjcjc

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

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

cjcjc

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

cjcjc

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

  

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

cjcjc

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

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



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

cjcjc

对于多次转弯，再按照边上的箱子数量的奇偶性总结规律比较麻烦，更简单的规律是：只要结构A、结构B和起始结构中的半位奇偶性全部一致，那么就可以任意组合，得到的关卡有解且最优移动呈指数增加。三种半位如下图所示：

cjcjc

此外闲兄还分享，A和B两种结构是可以任意组合的，比如一个关卡转弯多次，其中有结构A也有结构B。再结合上面说的不同方向的转弯，我总结出来的规律如下：
对于下图的起始结构，如果起始边的箱子数量是偶数，则可以使用结构A逆时针旋转或使用结构B顺时针旋转；如果起始边的箱子数量是奇数，则可以使用结构A顺时针旋转或使用结构B逆时针旋转，即下面4个关卡《2-2》、《2-2B顺》、《3-2顺》、《3-2B》和它们在边上加偶数个箱子的拓展关卡有解。



#########
#####--##
#------##
#.****-##
#----*-##
####-*-##
####-*-##
###--*-##
###-**--#
###---$@#
#####--##
#########
Title:简化2-2
Author:



#########
###--####
##------#
##-****.#
##-*----#
##-*-####
##-*-####
#--*-####
#-**--###
#---$@###
###--####
#########
Title:简化2-2B顺
Author:



#########
##--#####
##------#
##-****.#
##-*----#
##-*-####
##-*-####
##-*-####
#--*-####
#-**--###
#---$@###
###--####
#########
Title:简化3-2顺
Author:



#########
####--###
#------##
#.****-##
#----*-##
####-*-##
####-*-##
####-*-##
###--*-##
###-**--#
###---$@#
#####--##
#########
Title:简化3-2B
Author:

cjcjc

设计了上面这关之后我去找到了闲兄交流，他和我分享了一些他在设计主关时的发现和猜测，使我收获颇多。第一是他也发现了这个“转弯”的设计解的步数的指数增长性，他做了一些中间关卡，依此估计最优移动的增长速度，我在计算中做了参考（但是取了一个非常保守的数字）；第二是对于主关左侧和下部的连接方式，即结构B，同样可以满足“指数转弯”这一要求；第三是存在不同方向的“转弯”，他将下面的关卡分享在了MF8论坛的比赛帖中：

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



一开始，我的设计中只包括《上》和《左》连接的转弯结构A，对于《下》和《左》连接的结构B，我一开始没有吃透，所以没采用这种设计。经过我的推理和验证，发现如同闲兄所说，A和B的性质应该是类似的，即有解，且加箱子后解的最优移动呈指数增长。推理和验证的方法相同，不再重复说明，大家可以做几个简化关尝试。