扫雷舰解算算法

Question

我敢肯定你们大多数人都知道扫雷舰游戏。我想(用C#)编写我自己的扫雷舰游戏的代码，并且正在寻找一些关于什么是适用于该游戏的好算法的输入。我已经在网上浏览了很长一段时间，但没有找到一个好的解决方案。有人能帮我吗？

Answer 1

生成网格很简单。在执行玩家的移动时，您需要几个简单的算法来确定打开哪些方块，以及它们是输是赢。

生成网格

最简单的算法是随机放置所有的地雷。(请确保它们不会重叠！)

问题：玩家的第一次点击可能是一颗地雷。

改进:将网格的生成延迟到用户单击第一个方块，并且不要在该方块中放置任何地雷。

问题：玩家的第一次点击可能会显示一个非零数，他们将被迫随机点击，直到有东西打开。

改进:在第一次点击周围的(最多)八个方块中也不会产生任何地雷。

问题：玩家可能会在某一时刻被迫猜测，这是一个逻辑难题的可悲借口。

改进:在生成器旁边使用Run the solver，确保puzzle有一个独特的解决方案。这需要一些机智，而且在大多数变体中都不会这样做。

另一种不太常见的解决歧义的方法是检测玩家何时知道他们在相同的可能性之间进行选择，并将波形“折叠”到他们决定的位置。我从来没有见过这一点，但这将是一种乐趣。

玩游戏

除了标记旗帜之外，玩家还可以进行两种移动来尝试揭开方块：

• Single猜测：玩家点击一个状态未知且没有旗帜的方块。打开方块，看看玩家是否死了，然后在里面放一个数字。如果正方形包含0，则递归地对周围的所有正方形重复此操作。这应该在一个专用的函数中，将它与图形用户界面的事件处理程序分开，以简化递归，并且因为它在multiguess.
• Multiguess:中被重用，所以玩家点击一个未被覆盖且已知是安全的方块。如果周围的旗帜数量等于此正方形中的数量，我们将使用与上面相同的过程打开未标记的正方形。

赢得这场比赛

如果被遮盖的方块的数量与地雷的数量相同，那么玩家就赢了，即使他们没有在每个方块上放置旗帜。

当玩家输了的时候，习惯上会标记出他们所做的任何错误的猜测，剩余的地雷，以及他们踩到的地雷。

Answer 2

如果你想写一个求解器- Minesweeper is NP complete (Archive Link)，我只想添加以下内容。这意味着，在有人证明P = NP之前，在某些情况下，您可能没有比执行暴力搜索更好的方法了(但也许在游戏中，对于较小的字段，它不是NP完全的)。

Answer 3

正如亨利提到的，解决扫雷舰的正确方法是数学，特别是确定性部分的线性代数矩阵数学。我在这里有一个完整的帖子：

• 解释了这种方法是如何工作的，你可以在任何platform
• contains上编译和运行
• 的工作代码，该代码使游戏和解算器too

你可以在这里看到这一切：https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/

我建议通读一遍，然后好好思考一下。Minsweeper的概率部分也可以用统计来解决，但我还没有一个好的计划。然而，其他人也研究过它。