Minesweeper solving algorithm
I am pretty sure most of you know about the minesweeper game. I wanted to code (in C#) my own minesweeper game and was looking for some input as to what would be a good algorithm for that game. I have been browsing over the web for quite some time now but could not find a good solution. Can anyone help me with it?
Answer
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.