扫雷解决算法

Question

扫雷解决算法

algorithmminesweeper

28

我相信大多数人都知道扫雷游戏。我想用C#编写自己的扫雷游戏，但不确定应该使用什么算法？我已经在网上浏览了很长时间，但没有找到一个好的解决方案。

- Saurabh Lalwani

4

“好算法”？用于什么？ - Jonathan Feinberg

3

如果您想创建游戏（而不是求解器），为什么需要算法？只需在 YxZ 的区域上随机放置 X 个地雷即可... - Heinzi

1

我认为他的意思是“一个好的设计”，而不是其他什么。 - Konamiman

1

一个算法...用于什么？地雷放置吗？ - codebliss

扫雷游戏是纯粹的逻辑，而不是一些硬编码的胡言乱语！ - Secko

8个回答

6

我想补充一点，如果你尝试编写一个求解器 - 扫雷是NP完全问题（存档链接）。这意味着在有人证明P = NP之前，在某些情况下你可能无法做得比暴力搜索更好（但也许对于小型场地游戏不是NP完全问题）。

- Daniel Brückner

3

Claymath链接损坏。 - Adam Burley

2

NP并不意味着暴力破解。 - Shadow

@Shadow，有例子吗？ - user894319twitter

@user894319twitter，您可能拥有比暴力解决方案更快的启发式解决方案。 - Shadow

6

如Henri所述，解决扫雷的正确方法是使用数学，特别是线性代数矩阵数学来确定部分。我在这里写了一整篇文章：

解释了这种方法的工作原理
提供了可以在任何平台上编译和运行的工作代码
包含用于制作游戏和求解器的代码

你可以在这里查看全部内容：https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/

我建议你通读一遍，然后好好思考一下。扫雷中的概率部分也可以使用统计学来解决，但我还没有一个好的计划。不过，其他人也已经研究过了。

- Robert Massaioli

4

虽然我不是扫雷游戏的专家，但这里是我尝试解决它时使用的算法：

遍历所有已揭示区域的边缘方块。对于这些方块中的每一个，计算旁边已揭示的地雷数量，然后减去写在该方块中的数字（周围实际地雷的数量）。这就是这个方块周围剩余未揭示地雷的数量。将其除以当前方块周围未揭示方块的数量。这就是相邻的方块包含地雷的概率。如果任何方块的概率为1，则将其标记为地雷。如果任何方块的概率为0，则将其标记为安全。然后更新相关数字。

如果没有方块的概率为0或1怎么办？一个最优化的算法会考虑来自多个方块的限制。但正如我在开头写的那样，我不是扫雷游戏的专家，所以我从其他方块中随机选择概率最接近0或1的方块。

- Ofri Raviv

3

这是我的扫雷求解器：

对于每个数字方块：
- 如果周围未开启的方块数等于该方块数字：它们都是地雷
- 如果方块数字减去旗帜数量等于0：所有未开启的方块都不是地雷
使用子集规则

这是一个实际的实现，注意它使用了更难以解释的子集规则： https://github.com/SHiNKiROU/Minesweeper/blob/master/src/org/shinkirou/minesweeper/MinesweeperSolver.java#L27

当然，我的算法有时会失败。我计划实现一个类似 Prolog 的回溯求解器。

- Ming-Tang

2

评论中提到，建立游戏不需要算法。我相信你的意思是在解决问题时需要算法，大家可能也这样理解。

然而，任何问题的解决方案都可以被视为算法。

就像大多数数学问题一样，您可以将整个算法分解成较小、较简单的算法，直到您得到足够小的东西来解决它。这将为您带来第一个正确的解决方案。稍后，您可以在整个算法的上下文中优化较小的算法。

游戏板可以被视为一个二维数组。每个操作都将有一个关联的算法。第一个操作可能是一个随机生成的地雷位置集合，具有x、y坐标和地雷数量和板大小的参数。您将使用另一个算法与揭示方块相关联，该算法接受板和位置，并确定相邻的地雷数量。最后一个算法将接受板并检查是否剩余未揭示的无雷方块。

现在，您可以针对每个算法尝试进行优化以获得更好的性能，并说“给定使用x、y坐标的二维数组，计算当前方块相邻的地雷方块数量的最佳方法是什么”。

- Sam

2

请查看：http://quantum-p.livejournal.com/19616.html

在扫雷游戏中，任何无法通过猴子推理直观解决的位置都是一个矩阵，该矩阵可能能够解决一些单个（或整个）方块，从而提高解决率。简单的随机猜测并没有产生好的结果。我使用C ++将这种方法实现到我的解决算法中，通过添加线性方程组求解器进行优化。我正在通过运行数万次游戏，并进行统计来研究扫雷游戏的难度。

我的算法可以解决多达85％的（9,9,10）简单级别的扫雷游戏。我还没有对其他难度级别进行完整测试，但较小的测试表明，中等级别（16,16,40）的解决率为55-60％，而困难级别（30,16,99）则低至5-10％。我将添加一些新功能，使其更加优化。

- Henri

1

你看过这个C#实现的游戏吗？源代码可以下载，对象模型也有解释。

- Konamiman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Josh Lee · Accepted Answer

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

生成网格：

最简单的算法是随机放置所有地雷（确保它们不重叠！）

问题：玩家的第一次点击可能会踩到地雷。

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

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

改进：也不要在第一次点击周围（最多）八个方块中生成任何地雷。

问题：玩家可能会被迫猜测，从而使这成为一个悲惨的逻辑谜题。

改进：在生成器旁边运行求解器，确保谜题具有唯一解。这需要一些机智，并且在大多数变体中不执行。

另一种解决歧义的较少见的方法是检测玩家知道他们正在选择相等可能性之间的选项并“折叠波形”为他们所决定的位置。我从未见过实际操作，但这将是有趣的。

游戏玩法

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

单次猜测：玩家点击一个未知状态且没有旗帜的方块。揭示该方块，查看玩家是否死亡，并在其中放置一个数字。如果方块包含0，则递归地对所有周围的方块重复此过程。这应该在专用函数中完成，以将其与GUI的事件处理程序分离，使递归易于进行，并因为它在多次猜测中被重复使用。
多次猜测：玩家点击一个已揭开且已知安全的方块。如果周围旗帜的数量等于该方块中的数字，则使用与上述相同的过程打开未标记的方块。

赢得游戏

如果被覆盖的方块数与地雷数相同，则玩家获胜，即使他们没有在每个方块上放置旗帜。

当玩家失败时，通常会标记任何不正确的猜测、剩余的地雷和他们踩到的地雷。