魔方吧·中文魔方俱乐部

标题: 指数转弯关卡的研究以及50见方内极限最优移动步数关卡的设计 [打印本页]
作者: cjcjc    时间: 2022-9-16 13:31:41     标题: 指数转弯关卡的研究以及50见方内极限最优移动步数关卡的设计

本帖最后由 cjcjc 于 2022-9-17 10:52 编辑

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

[soko=0,0]_________HHHH_/HHHHHHHHHH__HH/H____________H/H__********__H/HH_*______*_HH/_H_*_HHHH_*_H_/_H_*_H__H_*_H_/_H_*_H__H_*_H_/_H_*_H__H_._H_/_H_*_HHHHHHHH_/_H_$______$_H_/_H_.*******xH_/_H________$_H_/_HH__HHHHHHHH_/__HHHH________[/soko]

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

我推过了这一关，觉得非常有设计价值，写了一些东西，主要是总结了闲兄的一些工作，也写了一些我的想法和猜测，在这里和大家分享。
作者: cjcjc    时间: 2022-9-16 13:37:34

本帖最后由 cjcjc 于 2022-9-17 10:53 编辑

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

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

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

[soko=0,0]_________HHHH_/HHHHHHHHHH__HH/H____________H/Ha.********__H/HH________*$HH/_HHHHHHHH___H_/________HHHHH_[/soko]

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

[soko=0,0]___HHHH_/HHHH__HH/H______H/H__**__H/HH_*__HH/_H_*_HH_/_H_*_H__/_H_*_H__/_H_*_H__/_H_*_H__/_H_*_H__/_H$*_H__/_H_x_H__/_HHHHH__[/soko]

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

[soko=0,0]___HHHH________/HHHH__HH_______/H______H_______/H__**__H_______/HH_*__HH_______/_H_*_HHHHHHHHHH/_H_*________$_H/_H_**********xH/_H____________H/_HH__HHHHHHHHHH/__HHHH_________[/soko]

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

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

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

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

本帖最后由 cjcjc 于 2022-9-17 15:50 编辑

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

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

2-2不计算转弯结构边上的箱子.png

不计算转弯结构和基础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，也即是斐波那契数列的极限增长速度。或许这个设计真的能够满足“指数转弯”！




附件: 2-2不计算转弯结构边上的箱子.png (2022-9-16 13:53:03, 5.49 KB) / 下载次数 105
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3NzcyfDgzNWQ3MzI0fDE3NTIwOTcwNzV8MHww
作者: cjcjc    时间: 2022-9-16 14:20:43

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

本帖最后由 cjcjc 于 2022-9-17 10:55 编辑

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

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

[soko=0,0]HHHHHHHHHHHH/HHHHHHHH__HH/H_________HH/H__******_HH/HH_*____*_HH/HH_*_HH_*_HH/HH_*_HH_*_HH/HH_._H__*_HH/HHHHHH_**__H/HHHHHH___$aH/HHHHHHHH__HH/HHHHHHHHHHHH[/soko]

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

[soko=0,0]HHHHHHHHHHHHHH/HHHHHHHHHH__HH/H___________HH/H__********_HH/HH_*______*_HH/HH_*_HHHH_*_HH/HH_*_HHHH_*_HH/HH_*_HHHH_*_HH/HH_*_HHHH_*_HH/HH_*____H_*_HH/HH_****.H_*_HH/HH______H_*_HH/HH__HHHHH_*_HH/HHHHHHHH__*_HH/HHHHHHHH_**__H/HHHHHHHH___$aH/HHHHHHHHHH__HH/HHHHHHHHHHHHHH[/soko]

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

本帖最后由 cjcjc 于 2022-9-17 15:51 编辑

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

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

[soko=50,50]HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH/HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH__HH/H_______________________________________________HH/H__********************************************_HH/HH_*__________________________________________*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH__HHH_*_HH/HH_*_HH___________________________________HHH_*_HH/HH_*_HH__********************************_HHH_*_HH/HH_*_HHH_*______________________________*_HHH_*_HH/HH_*_HHH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*_HHH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*_HHH_*_HHHHHHHHHHHHHHHHHHHHHHH__HHH_*_HHH_*_HH/HH_*_HHH_*_HH_______________________HHH_*_HHH_*_HH/HH_*_HHH_*_HH__********************_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*__________________*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHHHHHHHHHHHHHHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHHHHHHHHHHHHHHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHHHHHHHHHH__HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HH___________HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HH__********_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH_*______*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH_*_HHHH_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH_*_HHHH_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH_*_HHHH_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH_*_HHHH_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH_*____H_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH_****.H_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH______H_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHH__HHHHH_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHHHHHHHHH_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*_HHHHHHHHHH_*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_*____________*_HHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_**************__HH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH_________________HH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHH__HHHHHHHHHHHHHHHHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*_HHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HHH_*_HH/HH_*_HHH_*________________________*_HHH_*_HHH_*_HH/HH_*_HHH_**************************__HH_*_HHH_*_HH/HH_*_HHH_____________________________HH_*_HHH_*_HH/HH_*_HHH__HHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*____________________________________*_HH__*_HH/HH_**************************************__H_**__H/HH_________________________________________H___$aH/HH__HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH__HH/HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH[/soko]

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

本帖最后由 cjcjc 于 2022-9-17 10:57 编辑

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

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

[soko=0,0]_HHHH_______________/HH__HHHHHHHHHH______/H____________H______/H__********__H______/HH_*______*_HH______/_H___HHHH_*_H_______/_HHHHH__H_*_H_______/________H_*_H_______/________H_*_HHHHHHHH/________H_*______$_H/________H_********xH/________H__________H/________HH__HHHHHHHH/_________HHHH_______[/soko]

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

本帖最后由 cjcjc 于 2022-9-17 10:59 编辑

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

基础的起始结构.png

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

[soko=0,0]HHHHHHHHH/HHHHH__HH/H______HH/H.****_HH/H____*_HH/HHHH_*_HH/HHHH_*_HH/HHH__*_HH/HHH_**__H/HHH___$aH/HHHHH__HH/HHHHHHHHH[/soko]

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

[soko=0,0]HHHHHHHHH/HHH__HHHH/HH______H/HH_****.H/HH_*____H/HH_*_HHHH/HH_*_HHHH/H__*_HHHH/H_**__HHH/H___$aHHH/HHH__HHHH/HHHHHHHHH[/soko]

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

[soko=0,0]HHHHHHHHH/HH__HHHHH/HH______H/HH_****.H/HH_*____H/HH_*_HHHH/HH_*_HHHH/HH_*_HHHH/H__*_HHHH/H_**__HHH/H___$aHHH/HHH__HHHH/HHHHHHHHH[/soko]

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

[soko=0,0]HHHHHHHHH/HHHH__HHH/H______HH/H.****_HH/H____*_HH/HHHH_*_HH/HHHH_*_HH/HHHH_*_HH/HHH__*_HH/HHH_**__H/HHH___$aH/HHHHH__HH/HHHHHHHHH[/soko]

附件: 基础的起始结构.png (2022-9-16 14:40:12, 22 KB) / 下载次数 121
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3NzczfGY2ZGFhYTM5fDE3NTIwOTcwNzV8MHww
作者: cjcjc    时间: 2022-9-16 14:48:51

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

起始结构的半位.png 结构A的半位.png 结构B的半位.png


附件: 结构B的半位.png (2022-9-16 14:46:42, 7.41 KB) / 下载次数 96
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3Nzc2fGIxOGUxMDczfDE3NTIwOTcwNzV8MHww

附件: 结构A的半位.png (2022-9-16 14:46:34, 7.2 KB) / 下载次数 102
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3Nzc1fDcxNmIxMzNmfDE3NTIwOTcwNzV8MHww

附件: 起始结构的半位.png (2022-9-16 14:46:24, 34.92 KB) / 下载次数 90
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3Nzc0fDE1NjVmZjJhfDE3NTIwOTcwNzV8MHww
作者: cjcjc    时间: 2022-9-16 14:54:59

本帖最后由 cjcjc 于 2022-9-17 11:12 编辑

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

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

[soko=50,50]HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH/HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH__HH/H_______________________________________________HH/H__********************************************_HH/HH_*__________________________________________*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH__HHHH_*_HH/HH_*_H____________________________________HHH_*_HH/HH_*_H__*********************************_HHH_*_HH/HH_*_HH_*_______________________________*_HHH_*_HH/HH_*_HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*_HH_*_HHHHHHHHHHHHHHHHHHHHHHHH__HHH_*_HHH_*_HH/HH_*_HH_*_H__________________________HH_*_HHH_*_HH/HH_*_HH_*_H__***********************_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_____________________*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HHHHHHHHHHHHHHHHHHH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HHHHHHHHHHHHHH__HHH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_H________________HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_H__*************_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*___________*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_HHHHHHHHH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_HHHH__HHH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_H_$____HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_Hx.***_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_H_$__*_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_HHHH_*_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_HHHH_*_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_HHHH_*_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_HHHH_*_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*_HHHH_*_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_*______*_HH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH_********__H_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH___________H_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HH__HHHHHHHHHH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*_HHHHHHHHHHHHHH_*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_*________________*_HH_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_******************__H_*_HH_*_HHH_*_HH/HH_*_HH_*_HH_____________________H_*_HH_*_HHH_*_HH/HH_*_HH_*_HH__HHHHHHHHHHHHHHHHHHHH_*_HH_*_HHH_*_HH/HH_*_HH_*_HHHHHHHHHHHHHHHHHHHHHHHH_*_HH_*_HHH_*_HH/HH_*_HH_*__________________________*_HH_*_HHH_*_HH/HH_*_HH_****************************__H_*_HHH_*_HH/HH_*_HH_______________________________H_*_HHH_*_HH/HH_*_HH__HHHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*_HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH_*_HHH_*_HH/HH_*____________________________________*_HH__*_HH/HH_**************************************__H__*__H/HH_________________________________________H_*___H/HH__HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH__HH/HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH[/soko]

由类似的方法计算这一关的最优移动至少是3.3*10^61，这个数字偏差同样会非常非常大。
作者: cjcjc    时间: 2022-9-16 15:00:04

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

箱子运行示意图-1.png    箱子运行示意图-2.png

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


附件: 箱子运行示意图-2.png (2022-9-16 14:56:01, 13.39 KB) / 下载次数 91
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3Nzc4fDAwNDkwMzRlfDE3NTIwOTcwNzV8MHww

附件: 箱子运行示意图-1.png (2022-9-16 14:56:01, 10.91 KB) / 下载次数 84
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3Nzc3fDA5MTZkYWRlfDE3NTIwOTcwNzV8MHww
作者: cjcjc    时间: 2022-9-16 15:06:30

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

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

感谢闲兄、an版主、20603大师、st群主和杨版主等各位大佬的分享和意见。
作者: cjcjc    时间: 2022-9-16 15:17:53

本帖最后由 cjcjc 于 2022-9-17 11:03 编辑

附录1：主关的简化关卡

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

[soko=0,0]_______HHHHH_/HHHHHHHH___H_/H__________HH/H__********_H/HH_*________H/_H_*_HHHH__HH/_H_*_H__HHHH_/_H_*_H_______/_H_*_H_______/_H_*_HHHHHHHH/_H_*______$_H/_H_*******.xH/_H________$_H/_HH__HHHHHHHH/__HHHH_______[/soko]

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

[soko=0,0]_______HHHH_/HHHHHHHH__HH/H__________H/H__******__H/HH_*____*_HH/_H_*_HH___H_/_H_*_HHHHHH_/_H_*_HHHHHH_/_H_*____$_H_/_H_******xH_/_H________H_/_HH__HHHHHH_/__HHHH______[/soko]


作者: cjcjc    时间: 2022-9-16 15:23:00

本帖最后由 cjcjc 于 2022-9-17 11:14 编辑

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

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

[soko=0,0]HHHHHHH/HH_._HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/HH_*_HH/Ha_*_HH/H__$__H/H_*_*_H/HHH__HH/HHHHHHH[/soko]

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

[soko=0,0]_HHHHH_/_H_x_H_/_H$.$H_/_H_*_H_/_H_*_H_/HH_*_H_/H__*_HH/H__*__H/H__*__H/HHH__HH/__HHHH_[/soko]

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

[soko=0,0]HHHHHHH/HHa._HH/HH$.$HH/HH_*_HH/HH_$._H/H__*__H/H___*_H/HH__HHH/HHHHHHH[/soko]

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

本帖最后由 cjcjc 于 2022-9-17 11:15 编辑

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

[soko=0,0]HHHHHHHH/HHH_._HH/HHH_*_HH/H___*_HH/HaH_$__H/H__*_*_H/HHHH__HH/HHHHHHHH[/soko]

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

本帖最后由 cjcjc 于 2022-9-17 11:17 编辑

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

[soko=0,0]_HHHHH_/_H_._H_/_H$x$H_/_H_*_HH/HH_*__H/H__*__H/H____HH/HH__HH_/_HHHH__[/soko]

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

[soko=0,0]_HHHHH_/_H_x_H_/_H$.$H_/_H_*_H_/_H_*_H_/_H_*_HH/HH_*__H/H__$__H/H__._HH/HH__HH_/_HHHH__[/soko]

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

本帖最后由 cjcjc 于 2022-9-17 11:21 编辑

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

[soko=0,0]_HHHHH__/_H_x_H__/_H$.$H__/_H_*_H__/HH_*_HHH/H_.$___H/H$_$.._H/H.__$_HH/H_$._HH_/HHHHHH__[/soko]

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

[soko=0,0]_HHHHH__/_H_x_H__/_H$.$H__/_H_*_H__/_H_*_H__/HH_*_H__/H_.$_HH_/H_.$__HH/H__*_*_H/H_$.___H/HHHHHHHH[/soko]

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

[soko=0,0]_HHHHH_/_H_x_H_/_H$.$H_/_H_*_H_/_H_*_H_/HH_*_H_/H_.$_HH/H__*__H/H_.$__H/H_.$_HH/HHHHHH_[/soko]

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

[soko=0,0]_HHHHH_/_Ha._H_/_H$.$H_/_H_*_H_/HH_*_H_/H_.$_HH/H__*__H/H_*___H/H_*__HH/HHHHHH_[/soko]

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

[soko=0,0]_HHHHH___/_H_x_H___/_H$.$H___/_H_*_H___/_H_*_H___/_H_*_HH__/HH_$._HH_/H_$.___HH/H___.$*_H/HHHH____H/___HHHHHH[/soko]

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

[soko=0,0]HHHHHHHH/HH_x_HHH/HH$.$HHH/HH_*_HHH/HH_*_HHH/HH_*_HHH/HH_*_HHH/H__*___H/H__*_._H/HH__$_HH/HHH__HHH/HHHHHHHH[/soko]

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

[soko=0,0]HHHHHHHH/HH_x_HHH/HH$.$HHH/HH_*_HHH/HH_*_HHH/HH_*_HHH/HH_*_HHH/H__$_HHH/H__*__HH/HH_._*_H/HHH____H/HHHHHHHH[/soko]

696这几个关卡都比较简单，推起来感觉差不多。
作者: cjcjc    时间: 2022-9-16 15:48:44

本帖最后由 cjcjc 于 2022-9-17 11:24 编辑

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

[soko=0,0]__HHHHHHH/__H_____H/__H_HHH_H/__H_x_H_H/__H_*$H_H/__H_*_H_H/__H_*_H_H/__H_*_H_H/HHH_*_H_H/H___*___H/H_*****_H/H_____*_H/HHH__HHHH/__HHHH___[/soko]

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

[soko=0,0]__HHHHH_/__H_x_H_/__H_*$H_/__H_*_H_/__H_*_H_/_HH_*_H_/HH__*_H_/H___*_H_/H_*_*_HH/H_*_*__H/H_*____H/HHHHHHHH[/soko]

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

[soko=0,0]__HHHHHHH/__H_____H/__H_HHH_H/__H_x_H_H/__H_*$H_H/__H_*_H_H/__H_*_H_H/_HH_*_H_H/HH__*_*_H/H___*_*_H/H_HHH___H/H___H*HHH/HHH___H__/__HHHHH__[/soko]

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

[soko=0,0]__HHHHHHH/__H_____H/__H_HHH_H/__H_x_H_H/__H_*$H_H/__H_*_H_H/__H_*_H_H/__H_*_H_H/__H_*_H_H/HHH_._H_H/H_*$._*_H/H_H_.$*_H/H_H**$__H/H______HH/HHHHHHHH_[/soko]

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

本帖最后由 cjcjc 于 2022-9-17 11:25 编辑

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

[soko=0,0]__HHHHH_/__H_x_H_/__H$*_H_/__H_*_H_/__H_*_H_/__H_*_H_/__H_*_H_/HHH_*_HH/H___*__H/H__**__H/H*_*__HH/H____HH_/HHHHHH__[/soko]

最后一个是我设计的，很简单，没什么意思……
作者: cjcjc    时间: 2022-9-16 16:00:37

注：以上关卡中有点修改了起始和结束状态；有的进行了旋转，保持方向一致；有的增加/删除了偶数个箱子，但是基本都和原始关卡等价。
作者: cjcjc    时间: 2022-9-16 16:06:19

本帖最后由 cjcjc 于 2022-9-17 11:25 编辑

附录3：不同起始结构的转弯

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

[soko=0,0]____HHHH_/HHHHH__H_/H______H_/Hx****_H_/H_$__*_H_/HHHH_*_HH/__HH_*__H/__H__*__H/__H____HH/__HH__HH_/___HHHH__[/soko]

我的猜想：使用闲兄的转弯结构，对于不同的起始结构，一样可以设计出“指数转弯”关卡。以另一种最简单的起始结构为例，我猜想上面的关卡以及它的扩展都有解（这关是有解的，我已经解出来了），而且最优移动呈指数增长。对于附录2中其他的起始结构（除了有辅助大通道的三关），应该也有类似的结果，不过我没有验证。
作者: cjcjc    时间: 2022-9-16 16:12:12

本帖最后由 cjcjc 于 2022-9-17 11:27 编辑

附录4：50*50的不同布局

##################################################
###############--########--########--########--###
##########--------##--------##--------##--------##
#########--******-#--******-#--******-#--******-##
######--#--*----*-#--*----*-#--*----*-#--*----*-##
#--------#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
#--*****-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*---*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-*$#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
##-+-#-*-#-*-##-*-##-*-##-*-##-*-##-*-##-*-##-*-##
#####--*---*-##-*----*-##-*----*-##-*----*-##-*--#
#####--*****-#--******-#--******-#--******-#--**-#
######-------#---------#---------#---------#-----#
###########--########--########--########--##--###
##################################################
Title: 银河旋风
Author: 闲(XIAN) + cjcjc

[soko=50,50]HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH/HHHHHHHHHHHHHHH__HHHHHHHH__HHHHHHHH__HHHHHHHH__HHH/HHHHHHHHHH________HH________HH________HH________HH/HHHHHHHHH__******_H__******_H__******_H__******_HH/HHHHHH__H__*____*_H__*____*_H__*____*_H__*____*_HH/H________H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/H__*****_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*___*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_*$H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HH_x_H_*_H_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH_*_HH/HHHHH__*___*_HH_*____*_HH_*____*_HH_*____*_HH_*__H/HHHHH__*****_H__******_H__******_H__******_H__**_H/HHHHHH_______H_________H_________H_________H_____H/HHHHHHHHHHH__HHHHHHHH__HHHHHHHH__HHHHHHHH__HH__HHH/HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH[/soko]

这一关的最优移动至少是4.3*10^63
作者: cjcjc    时间: 2022-9-16 16:17:36

本帖最后由 cjcjc 于 2022-9-16 16:42 编辑

传送门：

第一百六十六期 MF8 推箱子比赛 (166th)

20603 - 《不乱方寸》的前世今生——再谈50见方的关卡移动极限

西北天狼 - 百度贴吧推箱子关卡移动步数推算
作者: cjcjc    时间: 2022-9-16 16:22:37

全部都结束了，第一次在论坛发帖，以前都是回帖
作者: 20603    时间: 2022-9-17 00:50:41

超级兄与闲兄合作解决了fibo指数关卡转弯的难题，使得50见方关卡的最优移动步数大幅增长，非常了不起！

我也曾经研究过多种fibo指数关卡的转弯方案，并做出7、8个50见方的关卡图，其中大部分是漏洞或者无解，其中一个比较接近完成的方案也因为发现一个奇偶问题而搁浅。但最近重新研究发现了一些规律，待有空时发出来给大家参考。
作者: cjcjc    时间: 2022-9-17 12:19:53

20603 发表于 2022-9-17 00:50
超级兄与闲兄合作解决了fibo指数关卡转弯的难题，使得50见方关卡的最优移动步数大幅增长，非常了不起！

...

期待大师的分享~

其实这个设计还没有严格的证明它的最优移动的指数增长性，不能说是完全解决了。如果能够完全解决，可以说完全是闲兄的功劳，和我没啥关系

另外，刚刚给上面的xsb增加了图片，看得更直观一些。
作者: 柠檬水    时间: 2022-9-17 20:56:39

膜一膜大佬，讲的很好
作者: 西北天狼    时间: 2022-9-21 15:16:44

cjcjc 发表于 2022-9-16 16:12
附录4：50*50的不同布局

##################################################

超级兄，这个布局还要严格证明，当年就是因为转弯出问题，最终被穿越！
根据03兄的理论，两个半位奇偶不同，可能腾挪出一个整位。 所以转角处，可能被穿越。
总之，瑕不掩瑜，超级兄还是太厉害了。
作者: 西北天狼    时间: 2022-9-22 15:00:20

本帖最后由 西北天狼 于 2022-10-25 16:05 编辑

看了各位大师的研讨，我认为有半空位的弯道，最佳移动的步数将会大打折扣。
-----####-
--####--##
--#------#
--#-#**--#
--#---*-##
--###-*-#-
----#-*-#-
#####-*-#-
#-$---*-#-
#+*****-#-
#-----$-#-
#####-.-#-
----#####-
Title: 加墙
Author: TianLang


[soko=10,13]
_____HHHH_
__HHHH__HH
__H______H
__H_H**__H
__H___*_HH
__HHH_*_H_
____H_*_H_
HHHHH_*_H_
H_$___*_H_
Hx*****_H_
H_____$_H_
HHHHH_._H_
____HHHHH_
[/soko]
作者: 西北天狼    时间: 2022-9-22 15:07:53

本帖最后由 西北天狼 于 2022-10-25 16:12 编辑

Title: 偶数
Author: TianLang

----####--
---##--###
---#-----#
---#--**-#
---##-*--#
----#-*-##
#####-*-#-
#-$---*-#-
#+*****-#-
#-----$-#-
#####-.-#-
----#####-


[soko=10,12]
____HHHH__
___HH__HHH
___H_____H
___H__**_H
___HH_*__H
____H_*_HH
HHHHH_*_H_
H_$___*_H_
Hx*****_H_
H_____$_H_
HHHHH_._H_
____HHHHH_
[/soko]
作者: 西北天狼    时间: 2022-9-22 15:13:27

#########-
#----#--##
#-##-----#
#-###**--#
#-#---*-##
#-#-#-*-#-
#---#-*-#-
#####-*-#-
#-$---*-#-
#+*****-#-
#-------#-
#####--##-
----####--
Title: 奇数
Author: TianLang

[soko=0,0]
HHHHHHHHH_
H____H__HH
H_HH_____H
H_HHH**__H
H_H___*_HH
H_H_H_*_H_
H___H_*_H_
HHHHH_*_H_
H_$___*_H_
Hx*****_H_
H_______H_
HHHHH__HH_
____HHHH__
[/soko]
作者: 西北天狼    时间: 2022-9-22 15:19:13

##################################################
##  ##############################################
##                                               #
## ********************************************  #
## *                                          * ##
## * ######################################## * ##
## * ##  #################################### * ##
## * ##                                     # * ##
## * ## **********************************  # * ##
## * ## *                                * ## * ##
## * ## * ############################## * ## * ##
## * ## * ##  ########################## * ## * ##
## * ## * ##                           # * ## * ##
## * ## * ## ************************  # * ## * ##
## * ## * ## *                      * ## * ## * ##
## * ## * ## * #################### * ## * ## * ##
## * ## * ## * ##  ################ * ## * ## * ##
## * ## * ## * ##                 # * ## * ## * ##
## * ## * ## * ## **************  # * ## * ## * ##
## * ## * ## * ## *            * ## * ## * ## * ##
## * ## * ## * ## * ########## * ## * ## * ## * ##
## * ## * ## * ## * #    #  ## * ## * ## * ## * ##
## * ## * ## * ## * #  #     # * ## * ## * ## * ##
## * ## * ## * ## * # ###**  # * ## * ## * ## * ##
## * ## * ## * ## * # #   * ## * ## * ## * ## * ##
## * ## * ## * ## * # # # * ## * ## * ## * ## * ##
## * ## * ## * ## * # # # * ## * ## * ## * ## * ##
## * ## * ## * ## * # # # * ## * ## * ## * ## * ##
## * ## * ## * ## * #   # * ## * ## * ## * ## * ##
## * ## * ## * ## * ##### * ## * ## * ## * ## * ##
## * ## * ## * #  *       * ## * ## * ## * ## * ##
## * ## * ## * #  ********* ## * ## * ## * ## * ##
## * ## * ## * ##           ## * ## * ## * ## * ##
## * ## * ## * ##########  ### * ## * ## * ## * ##
## * ## * ## * ############### * ## * ## * ## * ##
## * ## * #  *                 * ## * ## * ## * ##
## * ## * #  ******************* ## * ## * ## * ##
## * ## * ##                     ## * ## * ## * ##
## * ## * ####################  ### * ## * ## * ##
## * ## * ######################### * ## * ## * ##
## * #  *                           * ## * ## * ##
## * #  ***************************** ## * ## * ##
## * ##                               ## * ## * ##
## * ##############################  ### * ## * ##
## * ################################### * ## * ##
#  *                                     * ## * ##
#  *************************************** ## * ##
##                                         ##$* ##
########################################  ### + ##
##################################################
Title: 广宇深深
Author: cjcjc + TianLang
360截图20220922151444831.jpg

附件: 360截图20220922151444831.jpg (2022-9-22 15:19:10, 153.36 KB) / 下载次数 92
http://www.mf8-china.com/forum.php?mod=attachment&aid=Mjc3ODQwfDJkNWJjMTc4fDE3NTIwOTcwNzV8MHww
作者: cjcjc    时间: 2022-9-22 17:04:07

西北天狼 发表于 2022-9-21 15:16
超级兄，这个布局还要严格证明，当年就是因为转弯出问题，最终被穿越！
根据03兄的理论，两个半位奇偶不 ...

感谢天狼大师的分享~
你说的这个问题我考虑过，9楼和10楼的结论可以避免这个问题的出现。这个布局就是根据上述结论修改的，所以应该是不存在你说的问题。各位如果有空可以再检查验证一下。
作者: cjcjc    时间: 2022-9-22 18:59:54

我做过转两次弯的简化关卡试了，是有解的，简化答案也大致上是按fibo关卡那样运行的，也没有出现半位合并的情况。不过关卡和答案没保存，刚刚重新做了一个简化关，贴在这里。

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

[soko=0,0]_____HHHH_____/HHHHHH__HH____/H________H____/H__*****_H____/HH_*___*_H____/_H_*_H_*_H____/_H_*$H_*_HHHH_/_H_x_H_*_H__HH/_HHHH__*_____H/____H__****__H/____HH____*_HH/_____HHHH___H_/________HHHHH_[/soko]

Solution: luuuuurrrrrrddddddrrrdddllullluuRRRllluuuRluURDlllULulldRddddrrUUddlluuRDluuuurRdLDlUrrRdLulldddrrUULulDrrruLdrrrrDDDuuuluLruulDrrDldlddRUldddrUldddrUdrrULrddrruuLruulDrdddlluRlllluuurrDDLUrRRDLrrruLulDldddrrUULrddlluRurruLulDlllddRRULrddrrUULuurDrdLddlluRllllUluRuuurrDDLUrdDDLUlldRdrUruRRDLrrruLulDldddrrUULrddlluRurruLulDlluullDDRUdddRRULrddrrUULuurDrdLddlluRllllUluRurrDDLUrRRDLrrruLulDldddrrUULrddlluRurruLulDlllddRRULrddrrUULuurDrdLddlluRllllUluRuuuulluuRRDLrrrDDLUrdDDLUrdDDLUlldRdrUruRRDLrrruLulDldddrrUULrddlluRurruLulDlluullDDRUdddRRULrddrrUULuurDrdLddlluRllllUluRurrDDLUlldRdrUruRRDLrrruLulDldddrrUULrddlluRurruLulDlluuuuuuLulDlddRRULuurDrdLdllllluluRRRRRDrdLLLddllUUddrruuLDurrruulllDurrrddllUlulldRurRdRlddllUURDrruLdrrruLuurDrdLdlDDRUldDDRUdddRRULrddrrUULuurDrdLddlluRllllUluRurrDDLUrRRDLrrruLulDldddrrUULrddlluRurruLulDlllddRRULrddrrUULuurDrdLddlluRllllUluRuuurrDDLUrdDDLUlldRdrUruRRDLrrruLulDldddrrUULrddlluRurruLulDlluullDDRUdddRRULrddrrUULuurDrdLddlluRllllUluRurrDDLUrRRDLrrruLulDldddrrUULrddlluRurruLulDlllddRRULrddrrUULuurDrdLddlluRllllUluRuuuulluuRRDLrrrDDLUrdDDLUrdDDLUlldRdrUruRRDLrrruLulDldddrrUULrddlluRurruLulDlluullDDRUdddRRULrddrrUULuurDrdLddlluRllllUluRurrDDLUlldRdrUruRRDLrrruLulDldddrrUULrddlluRurruLulDlluuuuuuLulDlddRRULuurDrdLdllllluluRRRRRDrdLLLrrDDRUldDDRUdddRRULrddrrUULuurDrdLddlluRllllUluRurrDDLUrRRDLrrruLulDldddrrUULrddlluRurruLulDlllddRRULrddrrUULuurDrdLddlluRllllUluRuuurrDDLUrdDDLUlldRdrUruRRDLrrruLulDldddrrUULrddlluRurruLulDlluullDDRUdddRRULrddrrUULuurDrdLddlluRllllUluRurrDDLUrRRDLrrruLulDldddrrUULrddlluRurruLulDlllddRRULrddrrUULuurDrdLddlluRllllUluRuuuuuuurDrdDDDDLrDDLUrRRDLrrruLulDldddrrUULrddlluRurruLulDllllUUUUddddldRdrRRdrrUUruLLLL



欢迎光临 魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/) Powered by Discuz! X2