作者：杨超
本文地址：http://sokoban.ws/blog/?p=430
一
推箱子的其中一个很重要的魅力来源于推箱子求解问题在计算复杂性理论里是一个 PSPACE 完全问题。在这里不对什么是 PSPACE 完全问题作出解释，但是推箱子的一部分美妙之处可以认为正是来源于它的计算复杂度达到了 PSPACE 完全问题的级别。具体表现就是可以设计出很多不同模式的关卡，而且我们目前所涉及到的模式只是一小部分，还有很广阔的空间等待我们去探索。另外一个表现就是存在一系列具有指数长度答案（相对与关卡的大小）的关卡，这一类关卡就是推箱子关卡众多模式里面非常有趣的一类，也是本文要讨论的对象。
二
2009年6月8日，我曾在魔方吧论坛发贴子介绍了一类指数长度答案的关卡。无独有偶，约一个月后的2009年7月5日，Matrix67的一片博客文章也介绍了这一关卡。我的贴子和 Matrix67 的博文介绍的关卡都是基于2000年国外的一个关于推箱子问题的解答。
对这个关卡的具体分析这里就不再重复了，简单的说它就是由一个个的“房间”构成，上图是三个房间的情况。要过关，最左侧一个房间要进入2次，但要进入左一房间1次，就要进入左二房间2次，所以左二房间一共要进入4次。同理，左三房间就要进入8次。一般的，若有n个房间的话，第n个要进入2^n次，于是答案长度便成指数增长了。
这个关卡设计巧妙，让人感受到推箱子的美。下面我们要介绍一个更美的更简洁紧凑，但同样也是具有指数长度的答案的系列关卡。
三
这个更漂亮的系列关卡也是在推箱子玩家里面流传了很长时间了，有很多变化形式，其中最经典的可能是如下图所示。
这是 Aymeric du Peloux 2001年设计的 Picokosmos 第17关。David Holland 在2002年曾分析过这个关卡。Dries De Clercq 在这个基础上作了名为 Fibo 系列的变形关卡。上图所示的经典形式不只是一个关卡，而是一系列关卡，关卡可以纵向任意伸长(同时箱子也增加)，只要保持箱子总数是偶数个就行了（奇数的时候关卡无解）。若用n表示箱子的数目，随着n增大，答案步数以n的指数函数增长。
没有玩过这一关的朋友可以点击此链接在线玩。先提前警告，虽然只有8个箱子，要解出来不太容易。
我是2009年在魔方吧发了前面提到的贴子之后，才注意到这个关卡，当时没有看到 David Holland 的分析文章，独立地研究了这一系列关卡的步数。下一节将简要的介绍一下我的计算方法。
四
上一节提到，这一系列关卡只对偶数个箱子有解。为了便于建立递推关系，我对箱子位置作了以下微妙调整，使得对奇数也有效。主要有两处改动：一是最下方一个箱子连同目标移动了一格；二是最上方一侧的箱子移下一格（哪一侧由奇偶性确定）。如下面所示，分别是4到8个箱子的情形（注意本节的图和上一节的图左右反了）。
设 n 个箱子的上述关卡的最佳答案需要用 M(n) 步移动，P(n)步推动过关。可以得到下面的递推关系：
M(n)= M(n-1)+M(n-2)+n +12, n 是奇数
M(n)= M(n-1)+M(n-2)+n+10, n 是偶数
P(n)= P(n-1)+P(n-2)+8 .
要得到上面的递推关系，需要观察出这系列关卡的过关规律，下面以n＝7 为奇数的时候推导以上公式。
首先观察到这样一个现象：过关时，箱子把关卡分割成左右两侧不相通的区域。以最佳答案过关时，人是停留在右侧区域，如下图所示的位置。
要想人最后留着左侧区域也是可以做到的，但是就是要多用2步移动，推动步数不变，最后位置如下。我们这里述而不证的这一观察到的结束位置的规律是必须亲自解过这一系列关卡才能有体会。如果你还没来得及解关，下面的递推关系就会彻底地揭示了求解的秘密了。
下面开始推导递推关系了。根据实践规律，当 n=7 个箱子时，前6步必须是 ldDDRU (6步移动，4步推动)。这6步之后，关卡变成下图。
————(1)
此时，若忽略最上面两个箱子，关卡实际上就是 n=5 个箱子的情形。利用 n=5 的时候的解法，可以走到下图的状态。
————(2)
从状态(1)到状态(2)，基本相当于解一个 n=5 个箱子的关卡，但由于人最后是停在左侧区域，根据前面提到的观察规律，中间需要移动 M(5) + 2 步和推动 P(5) 步。
接下来的步骤必须是 uuuuurrDDLU （移动11步，推动4步）。一般地，则是移动 n+4 步，推动还是4步。经过这11步，得到状态（3）。
————(3)
从状态（3）开始，直到最后过关，相当于解一个 n=6 个箱子的关卡，因为最上方的箱子保持不动。所以余下共移动 M(6) 步，推动 P(6) 步。
经过上面以 n=7 为例的分析，我们得到奇数时的递推关系：
M(n)=6+M(n-2)+2+n+4+M(n-1)=M(n-1)+M(n-2)+n+12
P(n)=4+P(n-2)+4+P(n-1)=P(n-1)+P(n-2)+8.
偶数的时候原理一样，具体的推导过程在此就省略了。
有了递推公式，和 n=4,5 时最佳步数，我们很容易就可以计算出下面的通项公式。
M(n)=(-1)^(n+1) + (9+sqrt(5)) * a^n + (9-sqrt(5)) * b^n – n -14 ,
P(n)=( (10+4*sqrt(5))/5 ) * a^n + ( (10-4*sqrt(5))/5 ) * b^n – 8,
其中 a=(1+sqrt(5))/2 , b=(1-sqrt(5))/2.
下面用 MathJax 显示一下上述两个通项公式。
$ M(n)=(-1)^{n+1} + (9+\sqrt{5})\cdot\Big({\frac{1+\sqrt{5}}{2}}\Big)^n + (9-\sqrt{5})\cdot\Big({\frac{1-\sqrt{5}}{2}}\Big)^n-n-14 $ ,
$ P(n)={\frac {10+4\sqrt{5}}{5} } \cdot \Big({\frac{1+\sqrt{5}}{2}}\Big)^n + {\frac {10-4\sqrt{5}}{5} }\cdot\Big({\frac{1-\sqrt{5}}{2}}\Big)^n-8 $ .
从通项公式中，我们可以看出，无论是移动还是推动，答案都是具有指数长度的。
常系数线性递推关系的求解是比较经典的数学理论了，中学数学竞赛常常有这方面的题目，在高等数学里亦有不少应用。这一系列关卡结构紧凑、浑然天成，却又蕴含如此典型的递推关系，实在是令人意想不到，堪称常系数线性递推关系的求解最有趣的应用之一。
附、第四节7个箱子关卡的最佳答案（306移动，102推动），答案格式说明请参看xsb和lurd格式简介:
ldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUrdrddLLUlldR
drUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUrdDDL
UrdrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuul
lDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRd
rUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulD
GIF动画演示答案(GIF动画用YSokoban,irfanview和gifsicle制作，可参看制作推箱子GIF动画教程)：
还是这一关，人最后停止在左侧区域的答案（308移动，102推动），移动多了2步，最后十来步稍微有区别：
ldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUrdrddLLUlldR
drUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUrdDDL
UrdrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuul
lDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRd
rUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluR