The implementation of Minesweeper in Simon Tatham's Portable Puzzle Collection is guessing-free. (It's also MIT licensed, so you're free to copy his implementation if you so desire.)
It's well-known solving minesweeper is NP-complete.
This is true but perhaps not as relevant as you think. The proposed algorithm is something like "repeatedly generate random boards until the computer can solve one". NP-hardness is a property of the worst case, but here we're really interested in the average-case hardness. If an unusually hard board is generated, we can time out the solver and restart with a new board.
Also, even if there were an oracle to distinguish good boards from bad, would you really want the user to have to solve a hard problem in order to avoid guessing? A less talented computer solver might bias the choice toward fairer boards.
I realize this question is rather old but figured I'd add an answer that is a bit different from the other answers and can result in fairly performant minesweeper board generation. Also, I'm including fully functional source code, albeit lacking comments and my usual professional polish and isn't quite complete.
We'll use the following numbers to indicate certain conditions:
-1 to indicate open spaces that are guaranteed to be empty and free (permanent).
0 to indicate a space that could be open or contain a mine (non-permanent).
1 to indicate a possible mine position (non-permanent).
2 to indicate a permanent mine position (permanent).
The first step is to reserve the starting position and the surrounding 8 spaces with -1 and then randomly generate a board filled with possible mines. This is the easy part. The key is to then solve the board internally before presenting it to the user.
Before entering the solver phase, find all the points with no mines in the region from the starting position and flag them as points of interest to resolve.
For the solver phase, solve as much as possible using logic rules until hitting a wall. The solver can be as simple or as complex as desired but players prefer reasonably simple rules of deduction over having to do a deep analysis to figure out mine positions. There are two types of deduction rules: Known mine positions and known empty spaces.
The first rule is obvious: All mines for the surrounding spaces have been found. Open the remaining spaces and mark them as points of interest. Mark the current point as done.
The next rule is also obvious: All surrounding spaces have been filled and the only remaining spaces are mines. Fill spaces with permanent mines. Mark the current point as done.
After that, things get a bit trickier. The next most common pattern is "1 2 1" with 3 adjacent unknown spaces (after counting up the mines left for the adjacent points). When that pattern is encountered either vertically or horizontally, then there can't be a mine in the middle space and the other two spaces have to be the mines.
From here, there are a couple of other logic rules that can be applied that are rather complex to explain but don't require recursion or testing a bunch of different points. I'll try to do my best:
The first complex rule is to open logically impossible positions where only one mine can be placed in two different adjacent spots, but there are three open adjacent spaces in a row/column (i.e. open the third spot). For example, for a logical "1 1 ?" there has to be a mine in one of the two 1 positions and the ? has to be an open space.
The other complex rule is to open logically impossible positions where only one mine can be placed in two different spots, but the adjacent space has only one mine and more than the same two possible spots (i.e. the rest are clear). For example:
???
?11
?1
When working with the point in the middle, the left three ? can't be mines and therefore have to be open spaces because there has to be a mine in the other two spaces.
I think those more complex rules become more apparent after generating a bunch of boards and encountering them for the first time.
All of those rules are doable with just working with the current point of interest and not going crazy with recursion or anything more complex.
Okay, now let's say the solver hits a wall in the logic and doesn't open any new spaces and doesn't know for certain about any more mines. The solution is to randomly move one or more non-permanent mines to a non-permanent location somewhere else on the board. This has the unfortunate tendency to push some mines to the edges and corners but it otherwise works fairly well. Doing this may also rarely cause earlier solved locations to become unsolvable.
The next step is to fill in spaces that were unreachable with mines (i.e. change 0's to 1's).
If the solver moves any mines, reset -1's to 0's and 2's to 1's, reopen the starting position, and start the solver over again until no more mines are moved. Also, if the output ever results in more than a 20% overfill of the target number of mines, then it's almost certain that the majority of the board got cut off with mines. For those situations, just start over with a brand new board. It takes less than 1 second to generate and solve a decent sized board internally using this algorithm in most programming/scripting languages. So the player can afford to wait for an extra half second.
I haven't looked at Simon Tatham's algorithm but I've played his mobile Mines minigame in his puzzle collection enough to know that it has a tendency to have a bunch of mines on the outer edges and corners. So it's likely that his algorithm does something similar to the above.
Here's a quick and dirty implementation in PHP of most of the algorithm shown above (mainly it doesn't do the last step and repeat the solver loop, which results in slightly less than perfect results - an exercise for you to implement on your own):
Writing generators/solvers for various games and puzzles is a satisfying experience as a software developer. Don't cheat yourself of that experience. The key to most puzzle generators/solvers is to start small, stare at various board states for a while, come up with a logical rule that works for most cases, implement that, and then repeat. So don't just grab the above code and use it as-is. Write your own. You should only peek at what other people have done if you truly get stuck or after you've rolled your own.
Disclaimer: This may or may not be entirely correlated, but it's something neat I noticed, and might be useful to others trying to find the answer.
In minesweeper, there's a neat little thing I found when looking at different minesweeper boards: In the game, when generating a board, all non-mine squares have their value set to the number of neighboring mines. However, you can apply the same thing, but in reverse: All mines add 1 to the value of each neighboring space. This makes it possible to think of mines less like mines, and more like layered 3x3 squares. To demonstrate, here's a board, stripped of any neighboring mine counts:
....x
.x...
x..x.
..x..
x...x
If we use the normal generation method, setting the value of each non-mine tile to the number of neighboring mine tiles, we get:
1111x
2x222
x33x1
23x32
x212x
So what's the issue with using this method? Well, it has to do with just how many times we're checking for a mine. Let's see:
1111x - took 23 checks
2x222 - took 31 checks
x33x1 - took 26 checks
23x32 - took 31 checks
x212x - took 20 checks
Ouch. That comes in at a total of 131 checks. Now, let's try the square method:
1111x - took 8 checks
2x222 - took 13 checks
x33x1 - took 18 checks
23x32 - took 13 checks
x212x - took 11 checks
This method is much faster, with a total of only 63 checks, less than half of the naïve method.
These "squares" can also be utilized when solving boards. For example:
0000
?110
??10
???0
In this example, we can clearly see a corner, and therefore a square, with a mine in the center (+ and - are queued opens and flags):
0000
?110
?-10
???0
We can also expand the corner, since there isn't another square on top of it:
0000
+110
+-10
?++0
However, we cannot expand the last ? in the same way until we uncover all the queued tiles. Just as an example, I'm going to use some twos:
0000
1110
2x10
?210
Now we can see another corner, and it turns out that it intersects a mine. This can be hard to spot, but this is a corner.
One thing to watch out for, though, is something like this:
00000
01110
12x10
x?210
2x100
In this scenario, there are 3 squares. The 4x4 region in the top right matches the previous scenario, but don't get fooled: the twos from earlier are part of two separate squares in this one, and the unknown tile happens to be a three. If we had placed a mine there, the twos would be complete, and we would have lost to misjudgment, trying to uncover a tile that seems safe.
TL;DR: Mines can be thought of as layered 3x3 squares, which can save time when generating and/or solving.
发布评论
评论（4）
Simon Tatham 的便携式拼图合集中扫雷的实现是无需猜测的。 （它也是麻省理工学院许可的，因此如果您愿意，您可以自由复制他的实现。）
The implementation of Minesweeper in Simon Tatham's Portable Puzzle Collection is guessing-free. (It's also MIT licensed, so you're free to copy his implementation if you so desire.)
这是事实，但也许并不像您想象的那么相关。所提出的算法类似于“重复生成随机板，直到计算机可以解决一个问题”。 NP 硬度是最坏情况下的属性，但这里我们真正感兴趣的是平均情况硬度。如果生成了异常坚硬的板，我们可以使求解器超时并使用新板重新启动。
另外，即使有一个神谕来区分好板和坏板，你真的希望用户必须解决一个难题以避免猜测吗？一个不太有才华的计算机解算者可能会偏向于更公平的棋盘。
This is true but perhaps not as relevant as you think. The proposed algorithm is something like "repeatedly generate random boards until the computer can solve one". NP-hardness is a property of the worst case, but here we're really interested in the average-case hardness. If an unusually hard board is generated, we can time out the solver and restart with a new board.
Also, even if there were an oracle to distinguish good boards from bad, would you really want the user to have to solve a hard problem in order to avoid guessing? A less talented computer solver might bias the choice toward fairer boards.
我意识到这个问题相当老了，但我想我应该添加一个与其他答案有点不同的答案，并且可以产生相当性能的扫雷板生成。另外，我还提供了功能齐全的源代码，尽管缺乏注释和我通常的专业润色，而且并不完全完整。
我们将使用以下数字来指示某些条件：
第一步，将起始位置和周围8个空格保留为-1，然后随机生成一个布满可能地雷的棋盘。这是最简单的部分。关键是在将电路板呈现给用户之前先在内部对其进行解决。
在进入求解器阶段之前，从起始位置开始找到该区域内所有没有地雷的点，并将它们标记为要求解的兴趣点。
对于求解器阶段，使用逻辑规则尽可能多地求解，直到碰壁。解算器可以根据需要简单或复杂，但玩家更喜欢相当简单的演绎规则，而不是必须进行深入分析来找出地雷位置。推演规则有两种：已知矿位和已知空地。
第一条规则很明显：周围空间的所有地雷都已被发现。打开剩余的空间并将它们标记为兴趣点。将当前点标记为已完成。
下一个规则也很明显：周围的所有空间都已被填满，唯一剩下的空间就是地雷。用永久性地雷填充空间。将当前点标记为已完成。
之后，事情变得有点棘手。下一个最常见的模式是“1 2 1”，其中有 3 个相邻的未知空间（在计算相邻点剩余的地雷之后）。当垂直或水平遇到该图案时，中间空间不可能有地雷，而其他两个空间必须是地雷。
从这里开始，还有一些可以应用的其他逻辑规则，这些规则解释起来相当复杂，但不需要递归或测试一堆不同的点。我会尽力做到最好：
第一个复杂的规则是打开逻辑上不可能的位置，其中只能在两个不同的相邻位置放置一个地雷，但在行/列中有三个打开的相邻空间（即打开第三个位置） ）。例如，对于逻辑“1 1 ?”两个 1 位置之一必须有一个地雷，而 ?必须是一个开放的空间。
另一个复杂的规则是打开逻辑上不可能的位置，其中两个不同的地点只能放置一个地雷，但相邻的空间只有一个地雷和两个以上相同的可能地点（即其余的都是清晰的）。例如：
当使用中间的点时，左边的三个？不可能是地雷，因此必须是开放空间，因为其他两个空间中必须有一个地雷。
我认为在生成一堆板并第一次遇到它们之后，那些更复杂的规则会变得更加明显。
所有这些规则都是可行的，只需处理当前的兴趣点，而不是疯狂地进行递归或任何更复杂的事情。
好吧，现在假设解算器在逻辑上遇到了障碍，没有打开任何新空间，也不确定是否还有更多地雷。解决方案是将一个或多个非永久性地雷随机移动到棋盘上其他地方的非永久性位置。不幸的是，这有可能将一些地雷推到边缘和角落，但它在其他方面效果相当好。这样做也很少会导致先前解决的位置变得无法解决。
下一步是填补地雷无法到达的空间（即将 0 改为 1）。
如果解算器移动了任何地雷，请将 -1 重置为 0，将 2 重置为 1，重新打开起始位置，然后重新启动解算器，直到不再移动地雷。此外，如果输出导致地雷目标数量超出 20% 以上，那么几乎可以肯定，棋盘的大部分区域都被地雷切断了。对于这些情况，只需使用全新的主板即可。在大多数编程/脚本语言中使用此算法在内部生成并求解一个合适大小的板只需不到 1 秒。所以玩家可以多等待半秒。
我没有看过 Simon Tatham 的算法，但我在他的拼图系列中玩过他的移动地雷迷你游戏，足以知道它的外边缘和角落有一堆地雷的倾向。所以他的算法很可能会做与上面类似的事情。
这是上面显示的大多数算法在 PHP 中的快速而肮脏的实现（主要是它不执行最后一步并重复求解器循环，这会导致结果稍不完美 - 您可以自己实现的练习） ：
作为软件开发人员，为各种游戏和谜题编写生成器/求解器是一种令人满意的体验。不要用这种经历欺骗自己。大多数谜题生成器/求解器的关键是从小处开始，盯着各种棋盘状态一段时间，提出适用于大多数情况的逻辑规则，实施该规则，然后重复。因此，不要只获取上面的代码并按原样使用它。写你自己的。只有当你真的陷入困境或者在你自己推出之后，你才应该看看其他人做了什么。
I realize this question is rather old but figured I'd add an answer that is a bit different from the other answers and can result in fairly performant minesweeper board generation. Also, I'm including fully functional source code, albeit lacking comments and my usual professional polish and isn't quite complete.
We'll use the following numbers to indicate certain conditions:
The first step is to reserve the starting position and the surrounding 8 spaces with -1 and then randomly generate a board filled with possible mines. This is the easy part. The key is to then solve the board internally before presenting it to the user.
Before entering the solver phase, find all the points with no mines in the region from the starting position and flag them as points of interest to resolve.
For the solver phase, solve as much as possible using logic rules until hitting a wall. The solver can be as simple or as complex as desired but players prefer reasonably simple rules of deduction over having to do a deep analysis to figure out mine positions. There are two types of deduction rules: Known mine positions and known empty spaces.
The first rule is obvious: All mines for the surrounding spaces have been found. Open the remaining spaces and mark them as points of interest. Mark the current point as done.
The next rule is also obvious: All surrounding spaces have been filled and the only remaining spaces are mines. Fill spaces with permanent mines. Mark the current point as done.
After that, things get a bit trickier. The next most common pattern is "1 2 1" with 3 adjacent unknown spaces (after counting up the mines left for the adjacent points). When that pattern is encountered either vertically or horizontally, then there can't be a mine in the middle space and the other two spaces have to be the mines.
From here, there are a couple of other logic rules that can be applied that are rather complex to explain but don't require recursion or testing a bunch of different points. I'll try to do my best:
The first complex rule is to open logically impossible positions where only one mine can be placed in two different adjacent spots, but there are three open adjacent spaces in a row/column (i.e. open the third spot). For example, for a logical "1 1 ?" there has to be a mine in one of the two 1 positions and the ? has to be an open space.
The other complex rule is to open logically impossible positions where only one mine can be placed in two different spots, but the adjacent space has only one mine and more than the same two possible spots (i.e. the rest are clear). For example:
When working with the point in the middle, the left three ? can't be mines and therefore have to be open spaces because there has to be a mine in the other two spaces.
I think those more complex rules become more apparent after generating a bunch of boards and encountering them for the first time.
All of those rules are doable with just working with the current point of interest and not going crazy with recursion or anything more complex.
Okay, now let's say the solver hits a wall in the logic and doesn't open any new spaces and doesn't know for certain about any more mines. The solution is to randomly move one or more non-permanent mines to a non-permanent location somewhere else on the board. This has the unfortunate tendency to push some mines to the edges and corners but it otherwise works fairly well. Doing this may also rarely cause earlier solved locations to become unsolvable.
The next step is to fill in spaces that were unreachable with mines (i.e. change 0's to 1's).
If the solver moves any mines, reset -1's to 0's and 2's to 1's, reopen the starting position, and start the solver over again until no more mines are moved. Also, if the output ever results in more than a 20% overfill of the target number of mines, then it's almost certain that the majority of the board got cut off with mines. For those situations, just start over with a brand new board. It takes less than 1 second to generate and solve a decent sized board internally using this algorithm in most programming/scripting languages. So the player can afford to wait for an extra half second.
I haven't looked at Simon Tatham's algorithm but I've played his mobile Mines minigame in his puzzle collection enough to know that it has a tendency to have a bunch of mines on the outer edges and corners. So it's likely that his algorithm does something similar to the above.
Here's a quick and dirty implementation in PHP of most of the algorithm shown above (mainly it doesn't do the last step and repeat the solver loop, which results in slightly less than perfect results - an exercise for you to implement on your own):
Writing generators/solvers for various games and puzzles is a satisfying experience as a software developer. Don't cheat yourself of that experience. The key to most puzzle generators/solvers is to start small, stare at various board states for a while, come up with a logical rule that works for most cases, implement that, and then repeat. So don't just grab the above code and use it as-is. Write your own. You should only peek at what other people have done if you truly get stuck or after you've rolled your own.
免责声明：这可能完全相关，也可能不完全相关，但我注意到这是一件很巧妙的事情，并且可能对其他试图找到答案的人有用。
在扫雷中，当我查看不同的扫雷板时，我发现了一个巧妙的小事情：在游戏中，当生成板时，所有非地雷方块的值都设置为相邻地雷的数量。但是，您可以应用相同的方法，但相反：所有地雷将每个相邻空间的值加 1。这使得我们可以将地雷想象得不像地雷，而更像分层的 3x3 方块。为了演示，这里有一个棋盘，去除了任何相邻地雷计数：
如果我们使用正常的生成方法，将每个非地雷图块的值设置为相邻地雷图块的数量，我们得到：
那么使用此方法有什么问题？嗯，这与我们检查地雷的次数有关。让我们看看：
哎呀总共有 131 个检查。现在，让我们尝试一下平方方法：
这种方法要快得多，总共只有 63 次检查，不到 naïve 方法的一半。
这些“方块”也可以在解棋盘时使用。例如：
在这个例子中，我们可以清楚地看到一个角，因此是一个正方形，中心有一个地雷（+和-排队打开和标志）：
我们还可以扩展角，因为没有另一个正方形最重要的是：
但是，我们不能扩展最后一个？以同样的方式，直到我们发现所有排队的图块。举个例子，我将使用一些二元：
现在我们可以看到另一个角，结果发现它与一个地雷相交。这可能很难发现，但这是一个角落。
不过，需要注意的一件事是这样的：
在这个场景中，有 3 个正方形。右上角的 4x4 区域与之前的场景相匹配，但不要被愚弄：之前的 2 是这个场景中两个单独方块的一部分，而未知的图块恰好是 3。如果我们在那儿埋了一个地雷，那么这两个就完整了，而我们就会因误判而失败，试图找到一块看似安全的瓷砖。
TL;DR：地雷可以被认为是分层的 3x3 方块，这可以节省生成和/或求解的时间。
Disclaimer: This may or may not be entirely correlated, but it's something neat I noticed, and might be useful to others trying to find the answer.
In minesweeper, there's a neat little thing I found when looking at different minesweeper boards: In the game, when generating a board, all non-mine squares have their value set to the number of neighboring mines. However, you can apply the same thing, but in reverse: All mines add 1 to the value of each neighboring space. This makes it possible to think of mines less like mines, and more like layered 3x3 squares. To demonstrate, here's a board, stripped of any neighboring mine counts:
If we use the normal generation method, setting the value of each non-mine tile to the number of neighboring mine tiles, we get:
So what's the issue with using this method? Well, it has to do with just how many times we're checking for a mine. Let's see:
Ouch. That comes in at a total of 131 checks. Now, let's try the square method:
This method is much faster, with a total of only 63 checks, less than half of the naïve method.
These "squares" can also be utilized when solving boards. For example:
In this example, we can clearly see a corner, and therefore a square, with a mine in the center (+ and - are queued opens and flags):
We can also expand the corner, since there isn't another square on top of it:
However, we cannot expand the last ? in the same way until we uncover all the queued tiles. Just as an example, I'm going to use some twos:
Now we can see another corner, and it turns out that it intersects a mine. This can be hard to spot, but this is a corner.
One thing to watch out for, though, is something like this:
In this scenario, there are 3 squares. The 4x4 region in the top right matches the previous scenario, but don't get fooled: the twos from earlier are part of two separate squares in this one, and the unknown tile happens to be a three. If we had placed a mine there, the twos would be complete, and we would have lost to misjudgment, trying to uncover a tile that seems safe.
TL;DR: Mines can be thought of as layered 3x3 squares, which can save time when generating and/or solving.