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

shamy

西北天狼 发表于 2013-7-5 12:18
接楼上，图A是B8(八个箱子）的初始状态，图B是大约移动M6（六个箱子的最佳移动步数）步后的状态，图C是B8 ...

太棒了，有公式。感谢天狼兄推导。
哦，是N的一次函数。

请问推动数量能否计算呢？

还有，不知道有没有3次函数的？
二次函数的在版主的博客里好像有。

西北天狼

shamy 发表于 2013-7-5 14:18
太棒了，有公式。感谢天狼兄推导。
哦，是N的一次函数。

推动数当然可以计算，只要依葫芦画瓢就能做出。有兴趣的可以当作习题来做。
注意，这是递推函数，相当于3的指数函数小一点：M(2n)≈a×3^n。

shamy

西北天狼 发表于 2013-7-5 14:53
推动数当然可以计算，只要依葫芦画瓢就能做出。有兴趣的可以当作习题来做。
注意，这是递推函数，相当于 ...

哦，原来是这样，感谢天狼兄了。

shamy

看样子多加些箱子，步数增大的越多。100个箱子估计就天文数字了。60个箱子步数就多的离谱了。

kukufeicong

这关步数太吓人，我只作为关卡收藏的。

西北天狼

箱子数        移动步数        推动步数
4         48         15
6         170         57
8         494         167
10         1346         455
12         3580         1209
14         9432         3183
16         24756         8351
18         64878         21881
20         169922         57303
22         444934         150039
24         1164928         392825
26         3049900         1028447
28         7984824         2692527
30         20904626         7049145
32         54729110         18454919
34         143282762         48315623
36         375119236         126491961
38         982075008         331160271
40         2571105852         866988863
42         6731242614         2269806329
44         17622622058         5942430135
46         46136623630         15557484087
总步数        415229612726         140017356783
Excel计算60个箱子还是够用的，再大就超出15位整数的有效范围了，需要编程实现。

shamy

西北天狼 发表于 2013-7-10 11:32
箱子数        移动步数        推动步数
4         48         15
6         170         57

多谢天狼兄讲解啊。想不到这关能有这么厉害。

sokoban

我分析过这关的一个变形，写在博客中：http://sokoban.ws/blog/?p=430

正如天狼兄指出，原关有个特点，只有偶数个箱子有解。我把这个关卡做了很小的改动，使得奇数的时候也有解，这是一个好处。第二个好处是更容易建立递归关系。缺点就是不如原关卡美观。在经过变形后我给出了变形后关卡的通项公式。

原关和变形关的关系是：当箱子数n是偶数的时候，原关卡移动少11步，推动少3步。

西北天狼

sokoban 发表于 2013-7-13 18:33
我分析过这关的一个变形，写在博客中：http://sokoban.ws/blog/?p=430

正如天狼兄指出，原关有个特点，只 ...

还可以变形为：







公式跟箱子数的奇偶无关。

西北天狼

看了sokoban版主的博客，又认真研究了一下Fibonacci数列的通项公式，根据递推公式
M(2n)=3M(2n-2)-M(2n-4)+2n+24
P(2n)=3P(2n-2)-P(2n-4)+11
且M(4)=48, M(6)=170; P(4)=15, P(6)=57, 可以推导出如下公式：

这同时也验证了18#的结论。