经典证明:推箱子游戏所需步数可达指数级

    今天在写一个稿件时又翻阅了一下Erich FriedmanMath Magic,发现了一个有趣的东西——场地大小为n的推箱子游戏所需要的最少步数最坏情况是多少。下面这个构造说明,最坏情况至少也是指数级的。

    首先,让我们来看看该构造中的一个基本单元:

   

    这个构造中共有6个箱子,且它们都已经在目的位置上了。不难看出:
    1. 假如你人在这个区域之外,你只可能从右上角的出入口进入该区域,从其它地方进去都会导致死局
    2. 从右上角进入后你只能往下走,进入1区;走左边的话直接导致死局
    3. 你可以通过2区前往3区,但若从3区左上角的出口出去了,则2区动过的箱子将永远无法回到原位(除非你原路返回)
    4. 你可以通过2区前往3区,并把3区左边的那个箱子左移一格,再返回2区;这样下次你再从右上角进入该区域时便可以直接经过3区从左上角出去
    5. 最后你只能从4区离开

 
 

    把n个这样的构造串联起来,从右至左分别记作A_1, A_2, …, A_n。再在A_n左边附加一个只进不出的机关和一个需要移动一下的箱子。因此,整个图一共有6n+2个箱子,只有一个箱子不在目标位置。你的任务就是从A_1的最右边一直杀到A_n的最左边,并且保证此时A_1到A_n的所有箱子仍在原位上;然后进入A_n的左上角那块附加区域,把那个箱子推进去。
    不难看出,这个构造的唯一解便是从A_1的右上角进去,经过A_1的1区和2区,把A_1左上角的那个箱子向左推一格,然后从A_1下方出来;再次从A_1右上角进入,直接左行并从左上角出去,来到A_2的右上角;然后绕行A_2的1区和2区,把A_2左上角的箱子向左推一格,再从A_2下端出来。但注意到,此时A_1的状态又被还原了,你又无法直接从A_1左上角出去了;为了进入A_3,你不得不又重复刚才做的事情,把A_1左上角的箱子左移,出去之后再进来一遍。而进入A_3后,A_1和A_2的状态又都被还原了,于是你又不得不递归地处理A_1和A_2。因此,整个棋局的移动的步数显然是指数级的。

18 条评论

回复给 iceberg 取消回复

3  ×    =  3