论坛 › ★ 推箱子 (Sokoban) › 指数转弯关卡的研究以及50见方内极限最优移动步数关卡的设计

cjcjc 发表于 2022-9-16 15:54:35

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

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

__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__

最后一个是我设计的，很简单，没什么意思……

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

____HHHH_/HHHHH__H_/H______H_/Hx****_H_/H_$__*_H_/HHHH_*_HH/__HH_*__H/__H__*__H/__H____HH/__HH__HH_/___HHHH__

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

cjcjc 发表于 2022-9-16 16:12:12

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

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

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

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

这一关的最优移动至少是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

全部都结束了，第一次在论坛发帖，以前都是回帖:lol

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 static/image/common/back.gif
超级兄与闲兄合作解决了fibo指数关卡转弯的难题，使得50见方关卡的最优移动步数大幅增长，非常了不起！

...

期待大师的分享~

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

另外，刚刚给上面的xsb增加了图片，看得更直观一些。

柠檬水 发表于 2022-9-17 20:56:39

膜一膜大佬，讲的很好

西北天狼 发表于 2022-9-21 15:16:44

cjcjc 发表于 2022-9-16 16:12 static/image/common/back.gif
附录4：50*50的不同布局

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


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

查看完整版本: 指数转弯关卡的研究以及50见方内极限最优移动步数关卡的设计