扫雷的算法解决方案

Question

我正在尝试制作扫雷求解器。如您所知，有两种方法可以确定雷区中的哪些区域可以安全打开，或者确定哪些区域已被开采并且您需要对其进行标记。第一种确定方法很简单，我们有这样的东西:

如果(X 周围的地雷数量 - X 周围当前已发现的地雷数量)= X 周围未开发的区域数量，则 X 周围所有未开发的区域都被开采

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

但我的问题是:当我们找不到任何雷区或安全区并且我们需要查看不止一个区时，情况会怎样？

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

比如这种情况。我们无法使用以前的方法确定任何内容。所以我需要这些案例的算法帮助。

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

Answer 1

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

生成游戏的问题在这里问:Minesweeper solving algorithm . algebraic 上有一篇非常酷的帖子方法。您也可以尝试回溯(即猜测并查看是否会使事情无效)，类似于本地信息不足以处理类似 sudoku 的情况。 .看到关于这个的精彩讨论 technique .