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

cjcjc

---------####-
##########--##
#------------#
#--********--#
##-*------*-##
-#-*-####-*-#-
-#-*-#--#-*-#-
-#-*-#--#-*-#-
-#-*-#--#-.-#-
-#-*-########-
-#-$------$-#-
-#-.*******+#-
-#--------$-#-
-##--########-
--####--------
Title: 铁索连环 (MF8 166th Sokoban Competition, Main)
Author:闲(XIAN)



今天166期比赛结束了，上面的xsb是本期主关，闲(XIAN)设计的关卡《铁索连环 (MF8 166th Sokoban Competition, Main)》。

我推过了这一关，觉得非常有设计价值，写了一些东西，主要是总结了闲兄的一些工作，也写了一些我的想法和猜测，在这里和大家分享。

cjcjc

这关又是一个半个空位腾挪的关卡，一般来说我对这种关卡不是特别擅长。但是这次我刚好研究过类似的关卡，所以花了三四个小时就解开了，又用软件优化了几个小时，当天就提交了。而且油纸成伞兄比我还早半个小时提交。说这关不是特别难，可能有的朋友不太理解，毕竟是数万步的半位腾挪，但这么说也是有我的理由。

第一是因为这关可以拆成三部分分别来看，每一部分都是一个指数型关卡：

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



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



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



其中《上》和20603的《巴黎铁塔》是等价的。为了解开主关，首先分别解开这三关的删掉偶数行或偶数列的简化版（这一步可以用解关器，但是不鼓励大家使用）；然后解开这三关的原版；最后把主关当作这三关的嵌套，就可以获得主关的完整解法。

第二个理由是，这关的半位有4个，虽然没有理论支持，但是根据我的经验，半位越多腾挪起来越容易。因为《上》和《左》分别只需要2个和3个半位就可以完成腾挪，所以这期主关有更多的腾挪方式和空间。

cjcjc

说我自己的解关方法，就是按三关嵌套来接的，这种方法的优点是思考量比较少，但是缺点也很明显。把主关当作《上》《左》《下》的嵌套，完成《左》一次，需要完成《上》若干次；完成《下》一次，需要完成《左》若干次，最后的步数会非常的大，省了脑子但是费了手。这时我们会自然地联想到曾经20603大师在“《不乱方寸》的前世今生——再谈50见方的关卡移动极限”这篇帖子中提到的一个问题：有没有箱子可以转弯排列并且步数呈指数增长的设计？我自己尝试过，没有设计出来这种结构，6年前的20603大师也没找到这样的布局方法（不过根据最近的交流，20603大师透露对于这个问题他已经有几种不同的解决方案了，期待以后可以见到大师的设计），难道这期主关解决了这个问题？难道50*50大小的关卡的移动步数极限要上一个新的高度了吗？

乍看上去，这期主关还不能满足这样的设计目的。我第一次解开主关的步数是140多万步，优化后的步数只有4万步左右。根据西北天狼大师在“百度贴吧推箱子关卡移动步数推算”帖子内的计算列表可以看出，17个箱子的指数关卡的最优解的移动步数就有4万多步，这关的箱子数则不止17个。仔细观察优化后的答案也可以看出来，《左》和《下》的连接处和其它一些地方会有一些步骤和基础的fibo关卡的运作方式不同。

cjcjc

为了确定这个结构到底满不满足最优移动步数呈指数增长，我首先研究了《上》和《左》的转弯结构（以下称之为结构A，《左》和《下》的转弯结构称之为结构B），做了一系列简化关卡，以下关为例：

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



不计算转弯结构和基础fibo关卡的底部结构之中的箱子，上方一行箱子个数记为2，右侧一列箱子个数记为2，此关记做《2-2》。对于这一系列的简化关，上方增加任意数量的箱子和右侧增加偶数个箱子后均有解（如果只使用这种转弯的结构，对于多次转弯的关卡，称上面简化关中小人起始位置所在的边为起始边，称离小人起始位置最远的边为结束边，其他边称为中间边。起始结构相同，每次转弯都是逆时针方向，起始边和所有中间边增加偶数个箱子，结束边增加任意数量的箱子后均有解）。结合电脑优化器得到的结果，把此系列的简化关的最优移动（由电脑优化得到，可能不准确，但是相信在数字比较小的时候误差不大）展示如下：

右\上	2	4	6	8	10
2	468	972	2276	5680	14584
4	1008	1992	4540	11194	28604
6	2394	4638	10432	25566	65170
8	6018	11554	25842	63166	160846
10	15496	33248	80566	204772	530060

可以发现，这些关卡全部有解，且基本上每一关的最优移动都是它的同一行或同一列的前一关的两倍多。我猜测这个增长速度会趋近于(3+√5)/2=2.618，也即是斐波那契数列的极限增长速度。或许这个设计真的能够满足“指数转弯”！

cjcjc

当然这只是通过观察得到的结果，并没有严格的证明。想证明这一系列关卡都有解，可以通过归纳法递归证明，即所有关卡都可以分解成 简单且通用的腾挪步骤 + 少一个或两个箱子的关卡的答案中的部分或全部步骤 + 普通不转弯fibo关卡的腾挪 三部分组合完成，如此递归下去，具有转弯结构的fibo关卡最终可以分解成 简单且通用的腾挪步骤 + 普通不转弯fibo关卡的腾挪 组合，所以是有解的；但是对于最优移动增长速度的证明，我还没有好的思路。

cjcjc

上面对于转一次弯的关卡的分析和猜想，我猜测可以将其推广到多次转弯的情况下，为此我尝试了下面两个关卡，发现都有解，但是电脑已经不能将答案完全简化了（《2-2-2》的解优化后移动为1037，不知道是不是最优，《8-4-4-2》的解我花了2000多万步，估计能优化到1%甚至更少，但是已经超过yaso和jsoko的范围了）。

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



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



多次转弯的可解性，依然可以通过归纳法递归证明；对于最优移动增长速度，我猜测增加一个转弯的结构后最优移动增长的数字可以忽略，但是也没有严格的证明（这也可以解释上面说的两个问题：主关优化后的答案有一些地方看上去和基础的fibo关卡的运作方式不同，而且主关的最优移动比同箱子数的fibo关卡少，是因为转弯结构有一些独特的步骤，不参与fibo关卡的递归中）。

cjcjc

至此我猜想这种结构满足箱子可以转弯任意次排列，并且每次转弯的边都可以增加偶数个箱子均有解，解的最优移动步数呈指数增长。那么用这种思路设计50*50的关卡，使最优移动达到最大，得到了下面的关卡：

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



根据之前的结论，首先我判断这关有解。然后由对最优移动增长速度的猜测，计算这关的最优移动。保守起见，按每增加两个箱子最优移动变为2倍计算，边上的箱子数总计为350。因此得到这关的最优移动至少是468*2^173=5.6*10^54（这个数字偏差可能会非常非常大），已经超过了当年03兄和天狼兄设计的万亿亿亿(10^28)级别的关卡。

cjcjc

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

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



一开始，我的设计中只包括《上》和《左》连接的转弯结构A，对于《下》和《左》连接的结构B，我一开始没有吃透，所以没采用这种设计。经过我的推理和验证，发现如同闲兄所说，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

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