23

我很确定你们中的大多数人都知道扫雷游戏。我想（在 C# 中）编写我自己的扫雷游戏，并且正在寻找一些关于什么是该游戏的好算法的输入。我已经在网上浏览了很长一段时间，但找不到一个好的解决方案。有人可以帮我吗？

4

8 回答 8

59

Generating the grid is simple. There are a couple simple algorithms that you need when executing the player's move, to determine which squares to open up and whether they have lost or won.

Generating the grid

The simplest algorithm is to place all of the mines randomly. (Make sure you don't overlap them!)

Problem: The player's first click might be a mine.

Improvement: Delay the generation of the grid until the user clicks on the first square, and don't put any mines in that square.

Problem: The player's first click might reveal a non-zero number, and they will be forced to click randomly until something opens up.

Improvement: Don't generate any mines in the (up to) eight squares around the first click, either.

Problem: The player might be forced to guess at some point, making this a sad excuse for a logic puzzle.

Improvement: Run the solver alongside the generator, making sure that the puzzle has a unique solution. This takes some cleverness, and isn't done in most variants.

Another, less common way to resolve ambiguities is to detect when the player knows they are choosing between equally likely possibilities and "collapse the waveform" into the position they decided on. I have never seen this in action, but it would be kind of fun.

Playing the game

Besides marking flags, the player can make two kinds of moves to attempt to uncover squares:

  • Single guess: The player clicks on a square with unknown state and no flag. Reveal the square, see if the player died, and put a number in it. If the square contains a 0, repeat this recursively for all the surrounding squares. This should be in a dedicated function, to separate it from the GUI's event handler, to make the recursion easy, and because it's reused in the multiguess.

  • Multiguess: The player clicks on a square that is uncovered and known to be safe. If the number of flags surrounding equals the number in this square, we open up the unflagged squares using the same procedure as above.

Winning the game

If the number of squares that are covered up is the same as the number of mines, then the player has won, even if they haven't placed a flag on every square.

When the player loses, it is customary to mark any incorrect guesses that they made, the remaining mines, and the mine that they stepped on.

于 2009-11-15T20:42:24.070 回答
6

如果您尝试编写求解器，我只想添加以下内容 - Minesweeper is NP complete (Archive Link)。这意味着在有人证明P = NP之前，在某些情况下，您可能无法做比执行蛮力搜索更好的事情（但对于小领域来说，游戏可能不是 NP 完整的）。

于 2009-11-18T20:18:31.540 回答
5

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

  • 解释了该方法的工作原理
  • 具有可以在任何平台上编译和运行的工作代码
  • 包含制作游戏的代码和求解器

您可以在这里看到所有内容：https ://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/

我建议通读一遍，然后好好考虑一下。Minsweeper 的概率部分也可以使用统计数据来解决，但我还没有一个好的计划。但是，其他人也对此进行了研究。

于 2013-01-16T03:36:39.670 回答
4

我绝对不是扫雷专家，但这是我尝试解决它时使用的算法：

遍历所有显示区域边界的正方形。对于这些方格中的每一个，数一数你在它旁边发现的地雷数量。减去写在正方形中的数字（它周围的真实地雷数量）。那就是这个广场周围未发现的地雷数量。将其除以当前方格周围未显示的方格数。即每个相邻方格中包含一个地雷的概率。如果任何方块的概率为 1，则将其标记为地雷。如果任何方块的概率为 0，则将其标记为安全。然后你更新相关的数字。

如果没有正方形的概率为 0 或 1，你会怎么做？最佳算法将考虑来自多个方格的约束。但正如我一开始写的，我不是扫雷专家，所以我从其他概率最接近 0 或接近 1 的方格中随机选择。

于 2009-11-15T20:18:50.377 回答
3

这是我的扫雷求解器：

  • 对于每个数字方块：
    • 如果未打开的计数==平方数：它们都是地雷
    • 如果平方数-标记周围的计数== 0：所有未打开的都不是地雷
  • 使用子集规则

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

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

于 2010-12-05T02:07:17.910 回答
2

检查这个：http: //quantum-p.livejournal.com/19616.html

棋盘上任何不能用猴子推理直观地解决的位置都是一个矩阵，它可以解决一些单独的（或整个位置）方格，从而提高解决率。简单的随机猜测并没有产生好的结果。我通过添加线性方程组求解器将这种方法实现到我的 C++ 求解算法中。我正在通过算法运行数万场比赛并进行统计来研究扫雷的难度。

我的算法解决了高达 85% 的 (9,9,10) 简单级别的扫雷。我还没有对其他难度级别进行完整的测试，但较小的测试表明中等级别 (16,16,40) 的解决率是 55-60 %，困难级别 (30,16,99) 低至 5 -10%。我将添加一些使其最优化的新内容。

于 2010-10-25T18:50:08.550 回答
2

评论是您不需要算法来构建游戏。我相信您的意思是解决问题意义上的算法，每个人可能也会这样理解它。

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

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

游戏板可以被认为是一个二维数组。您将有一个与每个操作相关联的算法。第一个操作可能是一组随机生成的地雷位置，其中 x、y 坐标带有地雷数量和棋盘大小的参数。您将有另一种与显示正方形相关联的算法，该算法采用棋盘和位置并确定与其相邻的地雷数量。最终的算法将使用棋盘并检查是否有任何没有地雷的方格被留下来显示。

现在，您可以采用这些算法中的每一个并尝试优化它们以获得更好的性能，并说“在给定使用 x,y 坐标的二维数组的情况下，计算与当前正方形相邻的地雷的正方形的最佳方法是什么？

于 2009-11-15T17:37:41.263 回答
1

你见过这个游戏的 C# 实现吗？源代码可下载，并解释了对象模型。

于 2009-11-15T17:18:57.830 回答