5

我正在尝试制作扫雷求解器。如您所知，有两种方法可以确定雷区中的哪些字段可以安全打开，或者确定哪些字段已被挖掘并且您需要标记它。第一种确定方法是微不足道的，我们有这样的事情：

if (X 周围的地雷数量 – X 周围当前发现的地雷数量) = X 周围未开垦的田地数 那么 X 周围所有未开垦的田地都被开采

如果（X 周围的地雷数量 == X 周围发现的当前地雷数量）则 X 周围的所有未开垦区域都未被开采

但我的问题是：当我们找不到任何已开采或安全的场地并且我们需要查看多个场地时，情况会怎样？

http://img541.imageshack.us/img541/4339/10299095.png

比如这种情况。我们无法使用以前的方法确定任何内容。因此，对于这些情况，我需要算法方面的帮助。

我必须使用 A* 算法来做到这一点。这就是为什么我需要所有可能的安全状态来进行算法的下一步。当我找到所有可能的安全状态时，我会将它们添加到当前最短路径中，并根据启发式函数对路径列表进行排序并选择下一个需要打开的字段。

4

2 回答 2

8

很棒的问题，在你太兴奋之前，请阅读NP Completeness 和 Minesweeper，以及随附的演示文稿，其中开发了一些好的最坏情况示例以及人类如何解决它们。尽管如此，如果我们使用基本的修剪和启发式方法，我们很可能不会遇到时间障碍。

生成游戏的问题在这里问：扫雷求解算法。有一篇关于代数方法的非常酷的帖子。您还可以尝试回溯（即猜测一下，看看这是否会使事情无效），类似于本地信息不足以用于类似sudoku的情况。请参阅有关此技术的精彩讨论。

于 2013-04-11T19:45:01.457 回答
1

正如@tigger 所说，这不是一个可以通过一组简单的规则来解决的问题。Minesweeper 是一个很好的例子，其中 DPLL 等回溯算法很有用。使用命题逻辑这样简单的东西，你可以为扫雷实现一个非常有效的求解器。我不确定您是否熟悉 AI 推理和逻辑推理 - 如果不熟悉，您可能想看看 Stuart Russel 和 Peter Norvig 的《人工智能 - 现代方法》一书。如需快速参考 DPLL 和命题逻辑，请在 Google 上搜索“wumpus 世界命题逻辑”。

于 2013-04-11T22:07:44.140 回答