关于推箱子游戏的建议

符号

本指南将使用以下术语：

• 步数： 工人的步数，推或不推箱子都计入。
• 路径： 一系列动作。
• 位置： 工人和所有箱子在某地特定地方的情况。
• 解决方案： 所有箱子都在红点上的位置。
• 解决方案路径： 从初始位置到解决方案的一系列动作。
• 死局： 无法达到解决方案的路径。

总体战略

最短的解决方案可能包含100,300甚至1000个步数。 （我们最简单的游戏1需要73个动作，游戏8需要126个动作）。 如果平均每个移动有两种可能性，并且解决方案需要100次移动，那么盲目搜索将需要搜索2¹⁰⁰个路径以找到解决方案。 即使对于计算机，这也是不可能的。 因此，我们需要：

1. 尽早明确一个位置是不是死局，
2. 将总体目标分解为子任务。 如果100个步骤的解决方案路径可以分解为，例如，10个子任务，那么问题的复杂性将大大降低。 此外，有可能推断出完成子任务的顺序，然后整个问题变得容易解决，
3. 找到解决方案路径上的限制，
4. 想想其他探索方法。

关于 1)尽快找出死局

1.1)有时判断一个位置是否是死局很容易，只需要查看一个单独的箱子附近的情况。 要做的只是“本地”检查。 如果一个箱子不在一个点上并且不能水平移动，也不能垂直移动，那么该位置就是死局。 箱子可能被墙壁或其他也不能移动的箱子挡住。

1.2) 如果箱子靠近墙壁并且它可以被推动但是只能沿着同一侧的墙壁被推动而且它可以到达的任何地方都不是一个点，那么这个位置也是死局，虽然稍微难看出来一点。

1.3)在这种概括的情况中，箱子靠近墙壁并且可以移动到其侧面没有墙壁的地方（下面的位置A），但是将箱子推到A附近后，小工人无法到达A。

这三种情况可以只看箱子就决定，而不需要移动工人。 因此，可以在初始位置检查是否有此类情况，并可以标记出这些禁止的地方，比如说用！标记。 这样箱子就永远不会被推到这里。

1.4) 在进一步概括的情况中，小工人想要到达地点A就不得不把另一个箱子推到一个禁止的地方。

这种解释是循环的^[1], 也就是说，它用死局来描述死局。 这种死局更难以识别，因为它们无法通过“本地”检查发现，并且可能需要一些走步骤来测试。

关于 2)制定子任务

子任务的例子如下：

1. 把小工人从A移到B，
2. 把某个箱子从A移到B

完成这些任务都不应该制造出死局。

（a）的例子：工人怎么样才能绕过箱子到达A？

必须要有空间工人才能在箱子周围走动。 如果空的空间较少，那么工人无法在不产生死局的情况下绕过箱子。

如果玩家把大量子任务的路线烂熟于心，那么就可以节省很多时间，在本例中是一个9个步骤。更重要的是，玩家这道这个子任务是可能的，所以不会放弃。

与子任务相关的一个问题是如何找到它们。 例如，当反向解决问题时，就会出现子任务。 假设只能从一侧由一个箱子到达某个点，那么就需要将该箱子推向特定方向。 为了做到这一点，工人需要到达它的另一边。任务就可能是将箱子和工人放在正确的位置。

提出子任务的另一个典型示例如下。 安全地假设解决方案需要一个位置的所有内部空间。 这意味着，如果初始 位置具有庞大的内部空间，如上例中的2*3的空区域，这些空间用来干什么。可能是工人需要这个空间来绕过一个箱子，或者用于临时放一个箱子以便在其他地方释放空间。 因此，如果多余的空间能够临时存放一个箱子，那哪个箱子需要临时存放呢？怎么把这个箱子推到这个中间停放点？

关于 3)制定解决方案路径的限制

只需通过查看位置而不尝试移动就可以对解决方案路径进行许多限制。 例如：

3.1)有一个箱子可以进入但不可能贯穿的走廊，因此走廊末端的空间永远不能从走廊结束的一侧到达。

3.2)即使在不同侧面有空间，某个点也只能从一侧到达。

3.3)某个盒子永远不能在某个方向上移动，因此只能到达一个特定的点。

3.4)因为某些点只能从特定的方向到达，所以它决定了到达不同的点的顺序。

3.5)最后到达哪一点可能很清楚，因为工人需要空间来向某个方向推动一个盒子。

About 4) 其他探索

4.1) 可以并且应该尝试任何可以反转的推动顺序，即使这意味着工人必须走很长的路才能从另一侧推箱子以反转这些推动。即使这样的练习看起来毫无意义，但新位置也可能为如何开展提供新的可能性。

4.2) 如果有一条直线将所有点与至少一个箱子分开，则该箱子必须越过该线。如果这是不可能的，那么该位置就是死局。如果盒子只有一种方式穿过该线，则这就是对解决方案路径的巨大限制。

完整解决方案示例，游戏8

为了标记点，我们引入了坐标。 例如，工人最初在G1点。

最初，工人只有两个选项：A，穿过洞G3，或B，穿过洞E3。穿过G3只能让工人将B3的盒子推到B1，导致死局。所以工人穿过E3到达B2

我们可以做的唯一移动是A，将箱子从B3推到B4（不是B5，B5是死局），或者是从C2推到右边。

我们意识到盒子不能移动到通过G3的路线上的点，因为在这个它们之后就不能移动到左边了，如1.2中所示。

但是为了让它们通过洞B3，C3，我们需要在这个区域内有空间，所以我们需要在右边停放一个或两个箱子，之后又必须把它们移回来。

我们还意识到盒子B3只能在B线上移动，因此最终必须在B4点结束。

要在C4上移动后面的箱子然后将它们推到右边，工人必须能够移动到A4但是从下面到B4，箱子B3必须在B2处且空间B3，C3，C2必须是空的，所以两个盒子必须移开并停在右下方。

�

但是把箱子A3或B3推下去并不起作用。 我们在位置2唯一的另一个选择是首先将箱子B3推到B4，然后进行到位置3的移动。我们得到了

现在我们可以通过将箱子C3向下推到C2并与工人一起移动以将方框F2推到G2和G3：

如上所述，我们需要空间B3，C3，C2空出来，并将箱子B4下移到B2，所以我们需要暂时将箱子C2放在G2。我们得到：

简体中文：现在我们可以按照我们之前的计划将箱子G2推到C4，以便将其推向右边：

问题是我们要将盒子C4推到多右边。因为我们仍然需要通过相同的路径推箱子G3，所以我们需要让工人到G4并且为此我们要将箱子C4推到F4并将工人移动到G4以将G4推到G3：

中文：要将框G2向左移动，工人需要逆时针方向向后移动到H2。

剩下的很简单：将框G2推到C2，C4，D4

然后将框B2推到B4，工人移动到G4，最后把箱子F4推到E4。

完成。