百度贴吧推箱子关卡移动步数推算

西北天狼

箱子数        移动步数        推动步数
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

哟，怎么见到我的图了。原来是这样，这关需要4千多亿步。

洛阳狼王

没看懂                             

sokoban

大概算了一下，若1秒钟100步，要131年。

嘉芯饼干

推箱子我看了就没头绪

大雁5展翅

乍一看上去，似乎有很多已经归位，给人一种简单的感觉。再仔细一看，这一关绝对没有我想象的那么简单。一看步数真的吓了一跳

西北天狼

#1所示的百度贴吧推箱子关卡[47 x 49 - 414]，不算最大的，但步数令人生畏！像九连环和汉诺塔一样知道原理的人很多，实际操作的人少之又少。通常人们只满足于知道大致的结果，做到这一点，不像想象中那么难。由于这种关卡有较强的规律可循，所以先从较小的4、6、8、10个箱子做起，找出它们的最优解（如下）。
-#####-
##-+-#-
#-$.$##
#--*--#
#--*--#
###--##
--####-
48/15



-#####-
-#-+-#-
-#$.$#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
170/57



-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
494/167



-#####-
-#-+-#-
-#$.$#-
-#-*-#-
-#-*-#-
-#-*-#-
-#-*-#-
##-*-#-
#--*-##
#--*--#
#--*--#
###--##
--####-
1346/455

西北天狼

接楼上，图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


验算正确，结论：M4=48，M6=170，Mn=3×M(n-2)-M(n-4)+Bn+24，其中n为大于6的偶数，Bn为箱子数。