Sokoban求解器，提示

Question

我必须做一个索科班解算器(http://en.wikipedia.org/wiki/Sokoban)。你做过这样的事吗？我是在寻找提示，而不是代码。比如“你可以使用IDA* alg”或者“我使用了启发式方法，它很好”，或者“我使用了不能避免死锁的技术”。

基本上，我想在写任何代码之前把策略写在纸上。

Answer 1

我已经写了关于Sokoban算法的硕士论文。我的目标是对Sokoban解算器中使用的技术提供一个很好的概述。它没有提供明确的答案，但可能为对编写Sokoban求解器感兴趣的人提供了一个很好的起点。

http://weetu.net/Timo-Virkkala-Solving-Sokoban-Masters-Thesis.pdf

Answer 2

你可以创建一个暴力解算器，尝试将你的人移动到每个可能的方向。通过使用递归(或堆栈)，您可以在未找到解决方案时跟踪您的步骤。

A*可能不会对你有任何好处，因为你不需要在迷宫中找到路，但也需要移动盒子。这意味着您可能需要在移动长方体后向原来的方向后退。因此，对于每一步，你都需要评估所有的方向，包括你来自的那个方向。也就是说，除非您在上一步中没有移动长方体。

编辑你可以使用A*使它变得更智能；找到一种从你当前位置到任何你可以移动框的位置的方法。这可能会使您的解决方案更有效率，因为您不必跟踪中间的所有位置，而只需跟踪您推入的上一个框到下一个框的位置。