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

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

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因此，整个棋局的移动的步数显然是指数级的