百度贴吧推箱子关卡移动步数推算
本帖最后由 西北天狼 于 2013-7-3 12:31 编辑箱子数 移动步数 推动步数
4 48 15
6 170 57
8 494 167
10 1346 455
12 3580 1209
14 9432
16 24756
18 64878
20 169922
22 444934
24 1164928
26 3049900
28 7984824
30 20904626
32 54729110
34 143282762
36 375119236
38 982075008
40 2571105852
42 6731242614
44 17622622058
46 46136623630
总的移动步数：46136623630*9+7*8=415229612726 赞一个，，楼主威武！！ 额...好吓人的图！！ 本帖最后由 shamy 于 2013-7-3 13:32 编辑
哟，怎么见到我的图了。原来是这样，这关需要4千多亿步。 没看懂 大概算了一下，若1秒钟100步，要131年。 推箱子我看了就没头绪 乍一看上去，似乎有很多已经归位，给人一种简单的感觉。再仔细一看，这一关绝对没有我想象的那么简单。一看步数真的吓了一跳 本帖最后由 西北天狼 于 2013-7-10 11:19 编辑
#1所示的百度贴吧推箱子关卡，不算最大的，但步数令人生畏！像九连环和汉诺塔一样知道原理的人很多，实际操作的人少之又少。通常人们只满足于知道大致的结果，做到这一点，不像想象中那么难。由于这种关卡有较强的规律可循，所以先从较小的4、6、8、10个箱子做起，找出它们的最优解（如下）。
-#####-
##-+-#-
#-$.$##
#--*--#
#--*--#
###--##
--####-
48/15
_HHHHH_
HH_x_H_
H_$.$HH
H__*__H
H__*__H
HHH__HH
__HHHH_
-#####-
-#-+-#-
-#$.$#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
170/57
_HHHHH_
_H_x_H_
_H$.$H_
HH_*_H_
H__*_HH
H__*__H
H__*__H
HHH__HH
__HHHH_
-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
494/167
_HHHHH_
_H_x_H_
_H$.$H_
_H_*_H_
_H_*_H_
HH_*_H_
H__*_HH
H__*__H
H__*__H
HHH__HH
__HHHH_
-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
-#-*-#-
-#-*-#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
1346/455
_HHHHH_
_H_x_H_
_H$.$H_
_H_*_H_
_H_*_H_
_H_*_H_
_H_*_H_
HH_*_H_
H__*_HH
H__*__H
H__*__H
HHH__HH
__HHHH_
本帖最后由 西北天狼 于 2013-7-5 12:26 编辑
接楼上，图A是B8(八个箱子）的初始状态，图B是大约移动M6（六个箱子的最佳移动步数）步后的状态，图C是B8到达B6的状态，图D是B6又经过大约M4步后状态，同时也是B8大约移动两个M6步后状态；
再看一例，图E是B10的初始状态，图F是大约移动M8步后的状态，图G是B10到达B8的状态，图H是B8又经过大约M6步后状态，同时也是B10大约移动两个M8步后状态。
综上所述可知：图D，2×M6≈M8-M6+M4；图H，2×M8≈M10-M8+M6。即：Mn≈3×M(n-2)-M(n-4)
将具体的数据代入上式有：494=3×170-48+32, 1346=3×494-170+34。
预计M12=3×1346-494+36=3580
-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
-#-*-#-
-#-*-#-
-#-*-#-
-#-*-#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
3580/1209
_HHHHH_
_H_x_H_
_H$.$H_
_H_*_H_
_H_*_H_
_H_*_H_
_H_*_H_
_H_*_H_
_H_*_H_
HH_*_H_
H__*_HH
H__*__H
H__*__H
HHH__HH
__HHHH_
验算正确，结论：M4=48，M6=170，Mn=3×M(n-2)-M(n-4)+Bn+24，其中n为大于6的偶数，Bn为箱子数。