星河无边——50见方关卡的移动极限再探索

20603

本来想接在cj兄的帖子下写的，篇幅太长，担心破坏cj兄帖子的独立性，所以另开个新贴。

20603

星河无边——50见方关卡的移动极限再探索

文/Zou Yongzhong

　　cjcjc先生9月16日发表《指数转弯关卡的研究以及50见方内极限最优移动步数关卡的设计》，与闲兄合作解决了斐波那契（Fibonacci，以下简称fibo）指数关卡转弯的难题，使得50见方关卡的最优移动步数大幅增长，非常了不起！
　　在此我也分享一下对这一课题的以往研究过程和最新探索。

　　一、三种转弯思路。
　　我最初的研究是以三种转弯思路为基础，扩展出了多种转弯形状，设计了多种组合方案。三种基础思路的理论依据是：

图1

　　如上图，fibo指数关卡转弯如果成立，转弯后的箱子必须错位靠墙才能正常运行，如果是向下靠墙，看似不会死锁，但由于半位奇偶属性不变的原理，其实在某些位置与半位理论产生矛盾形成死锁。
　　比如图1中的远端第1个目标位（即黄色标记的2号位）要填上，有四种方式：(1)8号位的箱子推到7号位，5号位的箱子直接填2号位，同时形成偶半位，即必须移1个偶半位到这里才能顺利腾挪；(2) 8号位的箱子推到9号位，5号位的箱子直接填2号位，同时形成奇半位，即必须移1个奇半位到这里才能顺利腾挪；(3)5号位的箱子推到6号位，8号位的箱子补充到5号位，将来再移开6号位的箱子，由5号位的箱子填上2号目标点，这样也会形成奇半位；(4)5号位的箱子推到4号位，8号位的箱子补充到5号位，将来再移开4号位的箱子，由5号位的箱子填上2号目标点，这样会形成偶半位。
以上四种方法，(2)、(3)两种方法都必须借助奇半位才能腾挪，但关卡只有偶半位，所以这样推一定会形成死锁；(1)、(4)两种方法都必须借助偶半位才能腾挪，关卡正好有偶半位，腾挪上存在可行性，但箱子贴了死墙，无法推离。转弯的箱子在推动过程中，相邻的箱子必须轮流两边靠墙。在上图中，向上靠墙的箱子要想推回来，有三种方案：
　　1、        开墙方案：

图2
##########
##-------#
###***##-#
##-------#
##-*****.#
##-*-----#
##-*-#####
#--*-##___
#-**$-#___
#--@--#___
###--##___
#######___
Title: 指数转弯测试开墙方案1
Author: Zou Yongzhong


图3
##########
#       ##
# ###***##
#       ##
#.***** ##
#     * ##
##### * ##
   #  * ##
   # **$ #
   #  @  #
   ###  ##
   #######
Title: 指数转弯测试开墙方案2
Author: Zou Yongzhong

　　转弯处开墙后，靠墙的箱子就不再形成死锁。这种方案可以顺时针和逆时针转弯。这里有两种开墙结构（三只开墙木箱的位置不同），经测试，根据转弯方向和转弯之前箱子的奇偶数目不同，必须采用相应的开墙结构。如图2，奇偶数目的计数方式是，从底部中心点到转弯的中心点，有5个箱子是奇数。奇数个箱子向右转、偶数个箱子向左转，采用图2的结构；奇数个箱子向左转、偶数个箱子向右转，采用图3的结构。
这是当时简单测试研究的结果，其实与事实有出入。
　　为了准确描述顺时针和逆时针转弯、左转和右转，我在这篇文章里所有列出的fibo关卡或类似fibo关卡，都使用了统一的方位，与《WV277》、《巴黎铁塔》、《亿不足道》等关卡的方位相同，顺时针和逆时针、左转和右转等概念都是建立在此方位之上的，旋转不影响，翻转后的关卡与此相反。
　　经过对图2与图3答案的观察和增加不同数目箱子的测试，这种方案虽然也是指数式增长，但由于部分箱子不完整参与递归，没达到fibo指数的程度，具体指数的底是多少，并没有更深入的研究和证明。
　　后期由于有更好的方案，所以对开墙方案研究不透彻，存在许多不确定因素。
　　除此之外，我还测试了基础部分改为开墙结构，比如：

图4
##########
##-------#
###***##-#
##-------#
##-*****.#
##-*-----#
##-*-###-#
#--*-*---#
#-**$*-###
#--@-*-#__
###--###__
########__
Title: 指数转弯测试开墙方案3
Author: Zou Yongzhong


图5
###########
#---------#
#-###***#-#
#-------#-#
#.*****-#-#
#-----*-#-#
#####-*-#-#
___#--*-*-#
___#-**$*-#
___#--@-*-#
___###--###
___########
Title: 指数转弯测试开墙方案4
Author: Zou Yongzhong

　　图4、图5将基础部分也改成开墙类型。经测试分析，基础部分改为开墙结构，可供腾挪的空间少了半个，但并不带来更多的腾挪步骤，由于多了外围通道，导致部分箱子不参与完整的递归，使基础部分（不计转弯部分）步数的指数式增长受到影响。观察的结果是每增加2个箱子，步数大约为原来的2倍（仅观察部分数据，未证明）。原基础关卡fibo指数的底是1.618，这种开墙基础关卡（不计转弯部分）指数的底大约是√2，约为1.414，比fibo指数的效率要低。这种基础结构虽然指数增长的效率降低了，但对整体布局思路还是有意义的，后面会专门分析。

　　2、半位方案：

图6

　　转弯处留出与关卡系统半位（指fibo基础关卡的初始半位）奇偶属性相同的半位，使靠墙的箱子不会死锁。
　　这个方案闲兄和cj兄已经发过类似关卡，所以我就不贴xsb格式了。cj兄已经对这个方案进行了较为详细的阐述，我也不赘述了，只对cj兄没有阐明的部分做一个说明，那就是这种方案的两个结构产生的组合比较多，不同组合的推法会有或细微或较大的差异，某些布局下会产生一些捷径。比如这两个关卡：

   
图7

　　两个图的区别，主要是向左转还是向右转的区别，其余几乎一样，就像一个图的左右镜像。然而，它们的最优移动步数却差别较大，简单优化后左图27610步，右图14415步，可能还有优化余地，但仍然差距明显。原因是转弯方向不同时，为了保证半位属性相同，必须改变半位的位置，这让不同位置的半位腾挪难度不同；左图凸角半位较难利用，应用效率低，右图直角半位更整齐，易利用；两种转弯口的半位，在大部分组合中是相互独立的，但在少数组合中容易借助双半位带来捷径。




　　3、单箱方案：

图8
##########
#####-@-##
#-----*-##
#.*****-##
#-----*-##
#####-*-##
___#--*-##
___#-**--#
___#--$--#
___###--##
___#######
Title: 指数转弯测试单箱方案1
Author: Zou Yongzhong


图9
##########
##-@-#####
##-*-----#
##-*****.#
##-*-----#
##-*-#####
##-*-##___
#--*-##___
#-**--#___
#--$--#___
###--##___
#######___
Title: 指数转弯测试单箱方案3
Author: Zou Yongzhong

　　单箱方案是指在转弯处增加一个箱子，相应在墙上围绕增加的箱子开缺口，以避免靠墙的箱子形成死锁。经过测试，和开墙方案类似，这种单箱方案对转弯方向和转弯之前箱子的奇偶数目也有一定要求，从图8这种一次转弯的结构看，可分为4种类型：偶数个右转、偶数个左转、奇数个右转、奇数个左转。其中偶数个箱子右转，奇数个箱子左转可以成立，其它2种则不成立。然后又测试了如下的几种二次转弯结构：


图10
############
##---#######
##-*-------#
##-*******-#
##-*----*--#
##-*-##-*-##
##-*-##-*-#_
#--*-##-*-#_
#-**--#-.-#_
#--$--#####_
###@-##_____
#######_____
Title: 指数转弯测试单箱方案5（有解）
Author: Zou Yongzhong


图11
#############
##---########
##-*--------#
##-********-#
##-*-----*--#
##-*-###-*-##
##-*-###-*-#_
#--*-###-*-#_
#-**--##-.-#_
#--$--######_
###@-##______
#######______
Title: 指数转弯测试单箱方案6（无解）
Author: Zou Yongzhong


图12
______#####_
______#-.-#_
______#-*-#_
#######-*-#_
##---##-*-##
##-*----*--#
##-*******-#
##-*-------#
##-*-#######
##-*-##_____
#--*-##_____
#-**--#_____
#--$--#_____
###@-##_____
#######_____
Title: 指数转弯测试单箱方案7（无解）
Author: Zou Yongzhong


图13
_______#####_
_______#-.-#_
_______#-*-#_
########-*-#_
##---###-*-##
##-*-----*--#
##-********-#
##-*--------#
##-*-########
##-*-##______
#--*-##______
#-**--#______
#--$--#______
###@-##______
#######______
Title: 指数转弯测试单箱方案8（有解）
Author: Zou Yongzhong

　　最初对以上四种图形的测试，证实了上述偶数个箱子必须右转、奇数个箱子只能左转的结论。其实后来发现，这些测试并不完整，而且误导了我，后面会有阐述。

　　总结：以上三种方案都是为了避免箱子转弯后产生死锁，在转弯后外部的墙上设置了缺口。不论是开墙、设置半位或单箱，都必须尽量靠近转弯口，这是由fibo指数关卡的运行步骤决定的，远端的箱子逐步到位，如果缺口设在远端，对近端的箱子则不起作用。

20603

　　二、方案的比较。
　　这三种转弯方案各有特点：
　　开墙方案变化多，布局想象空间大，但易产生漏洞，且该方案的部分结构指数式增长小于fibo指数增长，最终步数相较fibo指数拉开的差距会非常大。
　　半位方案比较灵活，转弯布局几乎无限制，但是转弯部分有捷径，步数少。相同面积相同箱数，不同布局可能会产生较大的步数差距。
　　单箱结构是我最喜欢的一种结构，相同的空间内具有最高的效率。但是方向限制复杂，布局限制多。
　　这里用几个相似关卡比较一下三种方案的移动步数：

图14
#############
########---##
#-*------*-##
#-*-******-##
#-*-*----*-##
#-#-*-##-*-##
#---.-#--*-##
#######-**--#
______#--$--#
______###@-##
______#######
Title: 指数转弯测试方案比较1
Author: Zou Yongzhong


图15
############
#######--###
##--------##
#--******-##
#--*----*-##
##-*-##-*-##
##-.-#--*-##
######-**--#
_____#--$--#
_____###@-##
_____#######
Title: 指数转弯测试方案比较2
Author: Zou Yongzhong


图16
############
#######---##
#-------*-##
#-*******-##
#--*----*-##
##-*-##-*-##
##-.-#--*-##
######-**--#
_____#--$--#
_____###@-##
_____#######
Title: 指数转弯测试方案比较3
Author: Zou Yongzhong


图17

#######_____
#---.-######
#-#-*-#---##
#-*-*---*-##
#-*-*****-##
#-*-----*-##
#######-*-##
_____#--*-##
_____#-**--#
_____#--$--#
_____###@-##
_____#######
Title: 指数转弯测试方案比较4
Author: Zou Yongzhong

　　上面的前三个关卡，采用三种不同的方案，同样的木箱排序造型，开墙方案为3141步，半位方案为557步，单箱方案为2227步。开墙方案具有最多的移动步数，单箱方案次之，半位方案则显然空间利用率低，这是因为双半位（系统半位加转弯半位）令转弯口的腾挪变得简洁，更多箱子不参与递归。如果考虑到开墙方案多占一列空间，图17减去一列空间（减一列后转弯方向改变，但空间利用与其它两关是相同的）的步数为1995步，那么单箱方案的2227步是最优的。布局时不同转向的组合，各方案之间不一定有这么大的差距，差距有可能缩小但仍然明显，并且这差距也会随着转弯次数的增多而指数式增长。

20603

　　三、方案的选择。
　　通过上面的比较，对于50见方的关卡布局，开墙方案和单箱方案更合适，半位方案则适合作补充。就我最初的想法，当然希望开墙方案能成功，这意味着更多的步数。我内心的愿望是这样的：


图18
##################################################
#---##--######--######--######--######--#####-.-##
#-#-#-------#-------#-------#-------#-------#-*-##
#-#-#$*****-*-*****-*-*****-*-*****-*-*****-*-*-##
#-#-#-*---*-*-*---*-*-*---*-*-*---*-*-*---*-*-*-##
#-#-#-*-#-*-*-*-#-*-*-*-#-*-*-*-#-*-*-*-#-*-*-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-#-*-##
#-#---*-*-*---*-*-*---*-*-*---*-*-*---*-*-*---*-##
#-###-*-*-*****-*-*****-*-*****-*-*****-*-*****--#
#-#---*-*-------*-------*-------*-------*--------#
#---##@-##--######--######--######--######--######
##################################################
Title: 指数转弯测试布局2（漏洞）
Author: Zou Yongzhong

　　这是最紧凑的布局，也是一个明知不可为而为之的布局，开墙部分会产生明显的漏洞（即使弥补了漏洞也是无解的）。这个布局只是表达了当时内心的思路和愿望。
　　当然这种布局是不可行的，再次布局我选用了单箱结构：

图19
##################################################
##---#############################################
##-*---------------------------------------------#
##-*********************************************-#
##-*------------------------------------------*--#
##-*-########################################-*-##
##-*-#----------------------------------------*-##
##-*-#-****************************************-##
##-*-#--*---------------------------------------##
##-*-##-*-####################################--##
##-*-##-*-#---####################################
##-*-##-*-#-*-----------------------------------##
##-*-##-*-#-***********************************-##
##-*-##-*-#-*--------------------------------*--##
##-*-##-*-#-*-##############################-*-###
##-*-##-*-#-*-#------------------------------*-###
##-*-##-*-#-*-#-******************************-###
##-*-##-*-#-*-#--*-----------------------------###
##-*-##-*-#-*-##-*-##########################--###
##-*-##-*-#-*-##-*-#---###########################
##-*-##-*-#-*-##-*-#-*---------------------------#
##-*-##-*-#-*-##-*-#-***************************-#
##-*-##-*-#-*-##-*-#-*------------------------*--#
##-*-##-*-#-*-##-*-#-*-######################-*-##
##-*-##-*-#-*-##-*-#-*-#----------------------*-##
##-*-##-*-#-*-##-*-#-*-#-**********************-##
##-*-##-*-#-*-##-*-#-*-#--*---------------------##
##-*-##-*-#-*-##-*-#-*-##-*-##################--##
##-*-##-*-#-*-##-*-#-*-##-*-#---##################
##-*-##-*-#-*-##-*-#-*-##-*-#-*------------------#
##-*-##-*-#-*-##-*-#-*-##-*-#-******************-#
##-*-##-*-#-*-##-*-#-*-##-*-#-*---------------*--#
##-*-##-*-#-*-##-*-#-*-##-*-#-*-#############-*-##
##-*-##-*-#-*-##-*-#-*-##-*-#-*-#############-*-##
##-*-##-*-#-*-##-*-#-*-##-*-#-*-##------------*-##
##-*-##-*-#-*-##-*-#-*-##-*-#-*-#--************-##
##-*-##-*-#-*-##-*-#-*-##-*-#-*-#--*----------*-##
##-*-##-*-#-*-##-*-#-*-##-*-#-*-##-*-########---##
##-*-##-*-#-*-##-*-#-*-##-*-#-*-##-*-#############
##-*-##-*-#-*-##-*---*--#-*-#-*-##-*-#############
##-*-##-*---*--#-******-#-*---*--#-*-------------#
##-*-##-******-#-*------#-******-#-*************-#
##-*-##-*------#---######-*------#-*----------*--#
##-*-##---###############---######---########-*-##
##-*-########################################-*-##
#--*-*-#--------------------------------------*-##
#--*-*-#.**************************************-##
#--*-*-#-$------------------------------------*-##
###@-#---####################################---##
##################################################
Title: 指数转弯测试布局5（无解）
Author: Zou Yongzhong

　　为什么基础关要使用开墙结构？

图20

　　其实这里有个设计思路在里面，那就是“嵌套”，像《黄金链道》那样，使基础关卡的步数大幅增加。比如我们把多余的木箱改为墙，看看这一关：

图21

　　这个结构优化步数为4262步，如果不开墙做嵌套，看看下面的关卡是多少步：

图22

　　移动步数优化后是184步，嵌套后步数是之前的20倍以上（正式布局后倍数会有较多的缩水），这个部分是全关的基础，参与递归序列的箱子，每推1只都要经过这部分的嵌套绕圈（当然实际重复的基础部分要比这个简洁），这意味着整个关卡步数的大幅增加。
　　跟《黄金链道》不同的是，《黄金链道》是外部嵌套，这里是“自我嵌套”。这个设计思路就是嵌套的同时不耽误指数关卡的整体布局，不需要占用外部空间，这就是我前面说到的基础部分开墙设计在布局中的意义。
　　不过很可惜，这一思路虽好，却由于基础部分开墙造成指数增长的效率降低，得不偿失。当我发现这个问题时，曾试图寻找更合适的基础关卡。

20603

　　四、fibo关卡的变换。
　　基础部分开墙的设计，为整体“自我嵌套”的布局提供了可能，但指数的底从1.618降到约1.414左右，嵌套带来的倍数增长远远弥补不了指数增长效率降低带来的损失。为了解决这个问题，我找到多种疑似适合开墙设计的fibo指数关卡，看看有没有可以取代原基础关的设计。还有一些不同类型的fibo关卡，一并列出供参考。
　　下图是根据我的《WV277》关卡变换的fibo指数关卡：

图23
#######__
#-----#__
#-###-#__
#-#-.-#__
#-#$*-#__
#-#-*-#__
#-#-*-###
#---*-*-#
#-#**-*-#
#-*-@---#
####--###
___####__
Title: WV277-6
Author: Zou Yongzhong

　　我看cj兄发表的文章里提到anian兄的一关，与此关类似，但少了一个墙。这一关是两边开墙，看似从两边都可以嵌套扩展，其实较难实现。关卡从左侧开了个通道用于嵌套，转弯测试正常：

图24
#######____
#-----#____
#-###-#____
#-#---#####
#-#-*-----#
#-#$*****.#
#-#-*-----#
#-#-*-#####
#-#-*-###__
#---*-*-#__
#-#**-*-#__
#-*-@---#__
####--###__
___####____
Title: 指数转弯测试开墙方案9
Author: Zou Yongzhong

　　嵌套测试做了两个图，左图有解右图无解：

图25
################
###########---##
#-----------*-##
#-***********-##
#--*--------*-##
##-*-######-*-##
##-*-##---#-*-##
##-*-##-*---*--#
##-*-##-******-#
##-*-##-*------#
##-*$##-*-######
#--.-##-*-######
#-###---*-*-####
#-###-#**-*-####
#-###-*-@---####
#-----##--######
################
Title: 指数转弯测试开墙方案10
Author: Zou Yongzhong

　　右图无解是因为通道入口与原基础关不一致。左图虽然有解，指数的增长和图4、图5类似，没有改善。由于此结构比较臃肿，空间浪费多，就没有做太多分析。

　　下面是变换的另几种fibo指数关卡：

图26
#######  
### . #  
### * #  
### * #  
### * #  
### * ###
#   *   #
# #***# #
#   *   #
# ##$ ###
#   @##  
#######  
Title: WV277-7
Author: Zou Yongzhong


图27
_#####__
_#-.-#__
_#-*-#__
_#-*-#__
_#-*-#__
_#-*-###
##-*-*-#
#--*-*-#
#--$-*-#
#-##*#-#
#-----@#
########
Title: WV277-11
Author: Zou Yongzhong




图28
_#####__
_#-.-#__
_#-*-#__
_#-*-#__
_#-*-#__
_#-*-#__
##-*-#__
#--*-###
#--$-*-#
#*-*-*-#
#--*--@#
########
Title: WV277-16
Author: Zou Yongzhong


图29

_#####__
_#-.-#__
_#-*-#__
_#-*-#__
_#-*-#__
##-*-###
#--*---#
#-****-#
#--$---#
###**@-#
###---##
########
Title: WV277-8
Author: Zou Yongzhong

　　图26看似左右都开了墙，转弯没问题，但经测试，不论用什么方法进行嵌套，都会降低指数增长的效率，也不合适。图27、图28也是一样，单独关卡符合fibo指数增长，一旦嵌套就效率变低。图29是附带设计的一个fibo指数关，此外我设计的另一些fibo关卡，疑似与外面已有的关卡雷同或类似，就不列出来了。还有一个关卡是很久之前Laizhufu兄问我能加几堵墙，我将一些木箱改墙后得到一个fibo指数关卡，因为属于laizhufu未发布的关卡的一部分，所以也不发出来了。
　　我们来分析一下，测试了这么多关卡都未能嵌套成功，是何原因？再看下面2图：

图30
_#####
_#-.-#
_#-.$#
_#-*-#
_#-*-#
##-*-#
#--*-###
#-**-*-#
#-$--*-#
#-#--*-#
#-####@#
#------#
########
Title: WV277-13
Author: Zou Yongzhong


图31
#########
#-------#
#-#####-#
#-#-.-#-#
#-#-*-#-#
#-#-*-#-#
#-#-*-#-#
#-#-*-#-#
#---*-#-#
##-**-*-#
##-$--*@#
####--*-#
#########
Title: WV277-13-2
Author: Zou Yongzhong

##############
#------------#
#-##########-#
#-######---#-#
#-#------*-#-#
#-#.******-#-#
#-#------*-#-#
#-######-*-#-#
#--------*-#-#
#######-**-*-#
_____##-$--*@#
_____####--*-#
_____#########
Title: 指数转弯测试开墙方案13
Author: Zou Yongzhong

　　图30和图31（左）都是符合fibo指数增长的关卡，并且两关是等价的，是右下开墙，通道开在递归序列箱子的左侧。从图31可以看出，关卡如果转弯(见图31右)，与外围一圈是无关的，转弯后基础部分确实是要多绕圈子，但那是外部绕圈（占用了布局空间），不是内部自我嵌套。要实现自我嵌套，必须在递归序列箱子的远端设置出口。像下图这样：

图32

#############
#######---###
#-------*-###
#-*******-###
#--*----*-###
##-*-##-*-###
##-*-#--*-###
##-*-#-**-*-#
##-*-#-$--*-#
##-*-###--*-#
##-.-######@#
####--------#
#############
Title: 指数转弯测试开墙方案14
Author: Zou Yongzhong

　　这一关看上去与图5《指数转弯测试开墙方案4》相似，其实不同，右下角三个箱子的位置下移了，通道如果开在递归序列箱子的右侧，则无解。相同的地方则是：有些箱子不参与完整递归，指数增长效率降低了。图30、图31与图32的通道开口都在递归序列箱子的左侧，区别在于：图30、图31开口在下方，不用绕递归序列箱子一圈；图32开口在上方，从递归序列箱子远端的左侧开口，造成搬运工可以从左上方下来辅助腾挪，使参与递归的箱子有了助力，节省了步骤。
　　至此基本情况就是，虽找到许多开墙结构的fibo指数关卡，可以做fibo基础关，但却不能实现嵌套；若修改为适合嵌套的指数关卡，基本都达不到fibo级别。因此，唯有放弃嵌套式设计了。

20603

五、舍弃嵌套，重新布局。
　　经过多次设计和测试，嵌套都不能令人满意，无奈只好放弃。新的50见方关卡是这样排列的：

图33
##################################################
##---#############################################
##-*---------------------------------------------#
##-*********************************************-#
##-*------------------------------------------*--#
##-*-########################################-*-##
##-*-####################################---#-*-##
##-*-#------------------------------------*-#-*-##
##-*-#-************************************-#-*-##
##-*-#--*---------------------------------*-#-*-##
##-*-##-*-###############################-*-#-*-##
##-*-##-*-------------------------------#-*-#-*-##
##-*-##-*******************************-#-*-#-*-##
##-*-##-*----------------------------*--#-*-#-*-##
##-*-##---##########################-*-##-*-#-*-##
##-*-###########################---#-*-##-*-#-*-##
##-*-#---------------------------*-#-*-##-*-#-*-##
##-*-#-#**************************-#-*-##-*-#-*-##
##-*-#---*-----------------------*-#-*-##-*-#-*-##
##-*-###-*-#####################-*-#-*-##-*-#-*-##
##-*-###-*---------------------#-*-#-*-##-*-#-*-##
##-*-###-*********************-#-*-#-*-##-*-#-*-##
##-*-###-*------------------*--#-*-#-*-##-*-#-*-##
##-*-###---################-*-##-*-#-*-##-*-#-*-##
##-*-##################---#-*-##-*-#-*-##-*-#-*-##
##-*-#------------------*-#-*-##-*-#-*-##-*-#-*-##
##-*-#-******************-#-*-##-*-#-*-##-*-#-*-##
##-*-#--*---------------*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*-#############-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*-------------#-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*************-#-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*----------*--#-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##---########-*-##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-#############-*-##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-#-------------*-##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-#--************-##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*----------*-##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*-########-#-##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*-########---##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*-#############-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*-------------#-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*************-#-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##-*----------*--#-*-#-*-##-*-#-*-##-*-#-*-##
##-*-##---########-*-##-*-#-*-##-*-#-*-##-*-#-*-##
##-*-#############-*-##-*-#-*-##-*---*-##-*-#-*-##
#--*-##------------*-##-*---*-#--*****-##-*---*-##
#--*--#.************-#--*****-#------*-#--*****-##
#--*--#-$----------*-#------*-######-#-#------*-##
###@-#############---######---######---######---##
##################################################
Title: 指数转弯测试布局6（无解）
Author: Zou Yongzhong

　　图33和图19在布局上类似，都是尽量最大化利用空间。布局的关键点，是保留尽量多的单排墙，这种依靠一个角来回布置直角的方法，既能形成更多的单排墙，又能利用每一寸空间。由于转弯会使一些箱子不参与递归，所以在布置更多箱子的前提下，要尽量少转弯，在转弯和箱子的增减上要进行计算和权衡。
　　关卡也有一些奇怪的设计，如今突然看到，我都忘记原因了。好在原文件里有一些记录和说明文字，来帮助我回忆当时的思路。比如关卡的左侧从上往下2/5处，以及下方从左往右3/5处，是明显的空间浪费，墙体好像还能缩回去一行。后来看说明，才明白这布局是考虑到了单箱转弯结构受到奇偶数和方向的制约，整个布局是按照之前讲单箱方案时提到的“偶数个箱子右转，奇数个箱子左转”的规律进行的。在单箱转弯结构受转弯规律制约时，则用半位转弯结构进行补充；在用半位转弯结构进行补充觉得不划算时，为了确保所在行列箱子的奇偶数合法，就选择减去一行；

20603

　　六、单箱规律错误，研究搁浅。
　　这样的关卡虽然没法去解，但还是要对是否有解进行全面的测试。当时在进行有解测试时，发现了所谓的转弯规律并不正确，有些局部拆分出来是无解的。在前面阐述单箱转弯规律时，首先是对一次转弯的左、右、奇、偶等特性进行了观察，并总结出初步的规律，而后又对二次转弯的图形进行观察，二次转弯应该有2^4=16种组合，去除首次转弯的两种不可行类型，还有8种组合，但我只测试了其中首次向右转弯的4种，见图10-图13，这种图形刚好验证了前面总结的规律。而事实上，用心看这篇文章的朋友可能已经发现，图16、图25、图32这三个关卡已经不符合之前总结的单箱转弯规律，其实图25和32是写这篇文章时补上的关卡图，当时验证用的关卡比较简单，也有些误差。图16是当时做的方案比较图，却没有深究这一“违反规律”的构造，如果再深入研究一下，或许当年就能正确完成整体的50见方关卡布局了。
在这期间还发现，开墙结构转弯规律也是被误解了，只不过开墙方案几乎已被放弃，就没有进行具体的分析。
下图是再次寻找单箱转弯规律时测试的部分关卡：

图34       

　　为纠正单箱方案出现的布局规律理解错误，我再次测试了一些二次转弯和三次、四次转弯关卡，基本上有解和无解关卡是平均分布，图34只是一部分。先是怀疑每转一弯变一次奇偶规律，接着又感觉好像奇变偶不变，再后认为，首弯偶右则偶右奇左，首弯奇左则偶左奇右。这里的奇或偶指的是转弯之前所在列的箱子数目，左、右指的是往左、往右。研究的结果感觉都不太对。
　　由于多次转弯的关卡，腾挪实在费时，最后也没确认正确的规律，只好把这一研究束之高阁，尘封在电脑里。
　　也许有人要问，既然发现单箱转弯方案失败了，当时为何不用半位方案制作一个50见方关卡？回想起来，大概是坚信单箱转弯规律一定能找到，且半位转弯与单箱转弯比起来，差距实在比较大，从开始就确立了使用单箱方案，而没有尝试半位方案。并且觉得即使当时没完成，转弯规律一定会找到，待有空时再完成也一样。

20603

　　七、单箱结构的奇偶规律。
　　直到前一阵cjcjc兄发给我看他的研究成果，我才重新找出电脑里的一些关卡文件，许多思路已经忘记了，近日找时间把所有文字记录和关卡、零碎想法全部过了一遍，才理清了逻辑。重新寻找单箱转弯规律要比之前快了很多，因为我这次没有制作若干关卡来做测试，而是立足于理论分析，加之有了《推箱快手》这个很好的工具。终于找出了规律。
　　之前对半位奇偶性已经有了足够的认识，当时我虽然还没发表半位定理，但早已研究熟悉了相关的一些理论，所以对半位转弯结构的奇偶性能很快发现，半位的设置必须与系统半位奇偶同性，避免合成一个整位。但在单箱转弯结构中，却没能顺利找出规律，一个根本原因是没有合适的工具，木箱和半位的奇偶属性不能一目了然地看清楚。现在重新寻找奇偶规律时，特别要感谢愉翁兄，在《推箱快手》中提供了奇偶识别功能，随时能识别木箱、半位和局部结构的奇偶状况。
　　采用单箱方案的布局，全场几乎只有一处半位在运行，这就要求系统半位在每个转弯口都能顺利通行。如果是半位转弯方案，进行转弯时，即使转弯口奇偶位置不太顺畅，两处半位也可以接力运行，几乎无法阻挡半位的通行。而单箱结构就不同，没有可供接力的半位，所以只能在适合的路口转弯，否则有可能导致半位空间在通过转弯路口时难以转身，或者有去无回。

图35

　　如图，关卡系统半位是奇半位，半位空间在第一、第二弯都能正常通行，然而到第三弯时却遇到阻碍，左图无法通过，右图可以通过但回头时会形成死锁。这是由于转弯角所对应的半位与系统半位属性不同所造成的腾挪困难。也就是说，单箱方案转弯时，与内转角墙（图中白框墙）形成对角的半位（图中蓝框半位）必须与系统半位奇偶属性相同，才能转弯。
　　从这个结论看，之前总结规律时提到的“奇变偶不变”还是有一定道理的，从第二弯开始遵循的规则是：奇数个箱子改变时针方向，偶数个箱子不改变时针方向。
　　现在回头再看图33的关卡，可以看到多处明显违背单箱转弯规律的结构，所以无解。

20603

    　八、星河无边，何以为界？
　　据估算，可观测的宇宙包含的原子总数大约为10^80左右，50见方的关卡最优移动极限能否突破这一数字？答案是肯定的。我当年曾把图33那个无解关卡命名为《星河尘埃》，发现无解后就放弃了命名，今天就将其作为新关卡的命名吧。
　　单箱方案的布局规律掌握了，完成布局就很容易了，前日就做好了新的关卡，昨晚到今天凌晨进行了测试。关卡如下：

图36
##################################################
##---#############################################
##-*---------------------------------------------#
##-*********************************************-#
##-*------------------------------------------*--#
##-*-########################################-*-##
##-*-#####################################--#-*-##
##-*-#--------------------------------------#-*-##
##-*-#-************************************-#-*-##
##-*-#--*---------------------------------*-#-*-##
##-*-##-*-###############################-*-#-*-##
##-*-##-*-------------------------------#-*-#-*-##
##-*-##-*******************************-#-*-#-*-##
##-*-##------------------------------*--#-*-#-*-##
##-*-##--###########################-*-##-*-#-*-##
##-*-############################--#-*-##-*-#-*-##
##-*-#-----------------------------#-*-##-*-#-*-##
##-*-#--**************************-#-*-##-*-#-*-##
##-*-##-*------------------------*-#-*-##-*-#-*-##
##-*-##-*-######################-*-#-*-##-*-#-*-##
##-*-##-*----------------------#-*-#-*-##-*-#-*-##
##-*-##-**********************-#-*-#-*-##-*-#-*-##
##-*-##-*-------------------*--#-*-#-*-##-*-#-*-##
##-*-##---#################-*-##-*-#-*-##-*-#-*-##
##-*-#######---#######---##-*-##-*-#-*-##-*-#-*-##
##-*-#-------*-#-------*-##-*-##-*-#-*-##-*-#-*-##
##-*-#-*******-#-*******-##-*-##-*-#-*-##-*-#-*-##
##-*-#--*----*-#--*----*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
##-*-##-*-##-*-##-*-##-*-##-*-##-*-#-*-##-*-#-*-##
#--*-##-*-#--*----*-#--*----*-#--*---*-##-*---*-##
#--*--#-*-#-*******-#-*******-#-******-#--*****-##
#-*$--#-*-#-------*-#-------*-#--------#------*-##
###@-##-.-#######---#######---#######--######---##
##################################################
Title: 星河尘埃
Author: Zou Yongzhong
Date: 20220920

　　粗略计算关卡《星河尘埃》最优移动步数超过10^95，应该是《银河旋风》的100万倍以上。cj兄对《银河旋风》的计算太保守了，根据我的估算，我给他的4.3*10^63的数字后面再加至少20个0.。
　　《星河尘埃》会不会无解或漏洞？其实是可以通过分解关卡来测试的。图33的关卡一经测试就发现无解。这类转弯的fibo关卡，能够解出的关键是半位空间的移动，半位空间必须跑遍全场且来去自如。对于每一处转弯的连接，都可以观察到半位是怎么移动的，在相同的结构内，如果半位奇偶属性一致，运行轨迹也会一致。我们解关时是逐步解决的，解决到哪个部分，就会把半位空间带到那个部分，它在整体里的局部腾挪与分拆后的小关腾挪是一致的。所以只要所有转弯组合通过测试，就表明整关通过测试。
我从《星河尘埃》中提取了11种典型的组合：

图37

　　我对提取的关卡作了旋转以方便测试，并对11个关卡全部验证，有解无漏。《星河尘埃》所有转弯组合都可以在这11个图中找到对应部分，对这些关卡局部小转弯的部分还进行了加长测试，并在《星河尘埃》全关中进行了半位运行测试和轨迹分析，结果是合格的。由此我判断此关卡有解。
　　既然是寻找“最值”，索性就补上一些细节，再做一关：


Title: 星河无边
Author: Zou Yongzhong
Date: 20221015

　　这一关取名《星河无边》，已用同样方法进行了合格性测试。这一关比《星河尘埃》多了3个箱子的增量，最优移动步数大概是《星河尘埃》的4倍多。
　　星河无边，何以为界？50见方关卡的最优移动极限在哪里？期待未来能再突破！

20603

　　九、《星河无边》最优移动的初步计算
　　因空闲时间有限，《星河无边》的细节未做详细解释，待有空时再做整理补充。这里简单计算一下《星河无边》的最优移动步数。
　　关卡去除细枝末节，有501只箱子。关卡基础部分以11只木箱作为计算：
　　
　　基础关卡最优移动为2212步。关卡有22次转弯，其中单箱转弯16次，半位转弯6次。16个单箱转弯加进了16只木箱，要减去；经测算单箱转弯对递归木箱的影响约为0.85只箱子，16次转弯计为14只箱子，要减去；关卡使用的半位转弯结构对递归木箱的影响约为3只箱子，6次转弯计为18只箱子，要减去。
　　参与递归的木箱数目=501-11-16-14-18=442
　　估算最优移动步数=2212*1.618^442=5.16*10^95
　　故《星河无边》最优移动步数约为5.16*10^95步。由于关卡内每个局部对整体运行存在不同的影响，所以计算并不精确，只是一个大概数字。一些细枝末节添加的步数有若干亿步，在整个关卡中是完全忽略不计的。


2022年9月22日初稿
2022年10月15日修正