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

20603

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

20603

　　第９楼的《星河无边》关卡做了修正，原关卡有误，麻烦已经保存关卡的朋友以新关卡替代，原关卡无效删除。

20603

anian 发表于 2022-9-28 20:42
FIBO拐弯以前曾经研究过， 但都是失败的。

50X50见方的极限是多少看来目前还没有更好的想法。

anian兄说得对，目前的结构很难超越10∧100。并且我觉得，找到比fibo更有效率的结构的可能性也非常小。

2Bizer

看到一半就看不懂了，果然还是段位太低了

anian

FIBO拐弯以前曾经研究过， 但都是失败的。

50X50见方的极限是多少看来目前还没有更好的想法。
但如果增长速度是1.618的结构， FIBO设计是目前知道最少空间利用的设计。
如果还是保持这个增长速度， 其实50X50的极限是可以知道个大概的。

我曾经研究过这样的：
50X50 = 2500。  如果不限制关卡是见方， 只限制关卡是从2500个格组成的。
用FIBO的关卡设计，
容易看到， 每增加10格， 就可以多两个箱子。 因为原FIBO关卡是必须两个两个箱子增加的。

如果用最低箱子右移一格的设计:

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

可以每增加5格就多一个箱子。

按照这个数， 可以做出一关495个箱子的关卡, 共用了2498个格。

495个箱子， 最优的答案是：
push = 106509865922918858813872141409484991708258376523272847879158118956353031014079395956198661399296148179238,
moves = 315861200543852892480435277520355310503733260080965382662017364728597285326492092398851340992171928984407

大概 3.15x10^105。

如果关卡必须是50x50见方， 因为关卡里面需要拐弯， 如果还是以1.618倍增加的速度，

应该是无法超出 10^100的。

如果想超出， 就必须想出超过1.618倍增加速度的设计。

xwfh2000

叹为观止。我对细节还没能完全领悟，还在学习中。
能拐弯的指数关卡应该是最有效的提高步数的方式。
它和理论极限所差的只是“拐弯”的效率了。
和cjcjc兄的期盼一样，也许步数会超过10^100这个标志性数字。这个数字有个专用的名称：古戈尔

20603

　　超级兄：你所说的“增长速度是1.414的指数关卡应该就是n个箱子的版本包括n-2个箱子版本的答案两次以及一些简单步骤”，应该是差不多，我的想法是：

　　

　　P是推数，n是箱子数。它的值与你说的“n-2个箱子推两次“是相近的。

　　至于增长速度是2的结构，如果增加单个箱子，增长指数的底为2的话，目前的这种单排箱子的形状肯定是不行的。我觉得单排箱子排列的形状，最高增长速度就是约1.618，因为单排排列的最远端箱子到位只需要1推，那么次远端的箱子最多只需循环一次；对于次远端的箱子同理。那么推数最多就是按照斐波那契等比数列的比例递增，不可能有再高的比例。除非箱子排列方式不同，最远端箱子需要至少2推到位，才能使(n-1)或(n-2)的循环增加，但这样的排列方式不同，必然会造成布局空间的浪费，比目前fibo结构更有效率的可能性相当小。

cjcjc

周末两天时间，第一天在收拾家务和推比赛主关，主关很应景，也有fibo关卡的局部。第二天才研读03大师的成果，没想到03大师有这么多指数转弯的方案，实在是难以想象。

主要时间花在了最后采用的单箱方案上。单箱方案的转弯结构和最后总结的规律都足够简洁，空间利用率很高。在试推简化关卡的时候可以看到，因为只有一个半位，所以整体运行的流程很接近不转弯的fibo关卡，理解起来比较容易。而且没有半位方案中转弯损失步数的情况发生。

至于开墙方案，之前03大师私下和我分享过一些简化关卡，我试推的时候感觉对腾挪要求高一些，规律比较难找。再结合后面的不同基础结构和不同位置的通道和开墙，要完全消化可能还要费一番功夫。。

此外，不同效率的指数关卡也是我以前没见到过的。我的理解是：n个箱子的fibo关卡的答案包括n-1和n-2个箱子的fibo关卡的答案以及一些简单步骤，所以增长速度是1.618；增长速度是1.414的指数关卡应该就是n个箱子的版本包括n-2个箱子版本的答案两次以及一些简单步骤。还没来得及验证，不知道说的是不是准确，等有空再深入研究下。如果能研究出来增长速度是2的结构，那将会是大的突破。我看03大师的字里行间好像是已经有这方面的端倪了？03大师不愧是推箱先驱，功力太深了，佩服。

《星河尘埃》最优移动步数超过10^95，用“天文数字”来形容这个数字都已经不够了，实在是令人难以想象。未来还能突破吗？能超过10^100吗？期待大师更多的研究和更精彩的设计！

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日修正

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见方关卡的最优移动极限在哪里？期待未来能再突破！