扫雷游戏的算法解决方案

Question

我正在尝试制作扫雷求解器。如你所知，有两种方法可以确定哪些地方是安全的打开，或者确定哪些地方是有地雷的并且需要标记。第一种方法很简单，我们可以这样做：

如果（X周围的地雷数 - X周围已发现的地雷数）= X周围未打开的格子数，则所有X周围未打开的格子都有地雷

如果（X周围的地雷数 == X周围已发现的地雷数），则所有X周围未打开的格子都没有地雷

但我的问题是：当我们找不到任何有地雷或安全的格子时，我们需要查看多个格子怎么办？

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

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

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

- user216799

---

我不理解你提供的示例图像。最左边的“2”表示左侧第二行中的两个字段都被挖掘了，但第二个“2”只表示其中一个被挖掘了。在什么游戏情境下会出现这种情况？你是否想象游戏信息可能是矛盾的？ - pjmorse

但是，使用您的算法，您可以在该图像中找到一个安全区域。以被两个“1”包围的“2”为例；两个“1”周围的地雷数量等于“2”周围已发现的地雷数量。因此，您可以揭开其上方的空白区域。或者，您的意思是，如果您有一个尚未标记旗帜的该区域，您如何知道要标记这两个旗帜？ - Kevin

左右两侧还有更多未打开的字段。在左侧和右侧各添加一列未打开的字段，你就会明白了。 - user216799

我认为你不会找到一小组规则来涵盖每种情况，因为覆盖未揭示的瓦片的覆盖瓦片集与下一个未揭示瓦片所包围的瓦片集相交，依此类推。你可能需要通过一长串重叠的瓦片来推理出正确的移动方式，而不是猜测。一般来说，这是约束求解器的工作，从头开始实现并不容易。 - mbeckish

据传，很久以前我写了一个扫雷求解器，如果我没记错的话，只用了OP描述的两个规则。它可以自己解决高级难度的场地，但成功率只有10%左右。因此，如果你只是想建立一个无敌的最佳时间，并且有无限次尝试的机会，那么简单的方法可能已经足够好了。 - Kevin

Answer 1

很棒的问题，不过在你太兴奋之前，请阅读NP完备性和扫雷，以及相关的演示文稿，其中提供了一些好的最坏情况例子以及人类如何解决它们。尽管如此，如果我们使用基本的剪枝和启发式，预计我们不太可能遇到时间障碍。

这里提出了生成游戏的问题：扫雷求解算法。有一个非常酷的帖子讲述了代数学方法。您也可以尝试回溯（即猜测并查看是否使事情无效），类似于当局部信息对于像数独这样的东西不足够时的情况。请参阅这个关于该技巧的精彩讨论。

- Anil Vaitla

---

如果你可以从错误中备份，那么你只需一次性揭开每个方块，并跟踪哪些方块有地雷。我认为OP可能正在寻找一个遵循与人类相同规则的求解器-即如果您做出错误的移动，则失败。 - mbeckish

当其他方法都失败时，当然可以使用回溯法，否则树会呈指数级增长。 - Anil Vaitla

但是如果你不揭开地雷并输掉游戏，你怎么能回溯呢？ - mbeckish

抱歉，让我澄清一下。回溯意味着假装点击一个方块（当然这不会揭示任何新的方块）。现在考虑其他方块上的值如何改变，假设你点击的不是地雷。如果有一个方块变成小于1，则显然配置中存在矛盾，当前配置不可能，因此在假设点击的方块路径上必须有一个地雷。 - Anil Vaitla

我的错 - 我现在明白你的意思了。 - mbeckish

Answer 2

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

- aaronqli