Solving Minesweeper
This is a work in progress! (highly recommend for now using a PC and not mobile to view)
Why do this? Uhm not sure, it's sort of interesting.
The purpose of this accompanying article is to provide further context and to allow to showcase individual features easily.
Any visual examples with side-by-side game grids, the grid on the right is simply an uncovered version of the left hand side grid.
Implement the Game
Generate the Grid
Generating the grid for the game is done by creating a simple 2d array where each inner array represents a row. Each element within the inner array represents the state of a particular cell in the grid.
- Implement probabilistic auto solve (with visualisation)
- Implement optional sound effects
- Implement scoreboard
5/5
Place the Bombs
The second step is to ensure that N cells contain a bomb where N is the number of bombs for that specific game. An additional rule is that the first cell clicked by a player on starting the game should never contain a bomb. Because of the additional rule bomb placement can only be done directly after the first player click. Simply every cells position is added to an array except the position of the cell the user clicked. That array is simply shuffled using the Fisher-Yates Shuffler. The last N cells in the shuffled array then have their cell state update to true for isBomb.
20/20
Technically this visualisation is a bit of a lie. It does not include every shuffle done by the Fisher-Yates shuffling algorithm but simply shows the starting bomb positions and end bomb position (but here you go with my lies anyway)
5/5
Calculate neighbor cells and number of neighbor bombs.
To play Minesweeper every cell must know how many bombs are in its adjacent cells. This can only be calculated after the bombs have been placed obviously which occurs on the player's first click. Simply loop through every cell, calculate the position of its adjacent cells and also the total number of adjacent bombs. (for a twist I also added a borderless mode which has made the code significantly more disgusting to read)
5/5
Animation showing how the grid is looped through and every neighbor's position is calculated.
5/5
Borderless mode implementation, a cell on the left can have a bomb for a neighbor on the right, same for top-bottom and for all corners too.
5/5
Animation showing how the grid is looped through and every neighbor's position is calculated but for borderless.
5/5
Make the Game Playable
Finally to be able to play the game you must be able to reveal cells by left clicking, additionally right clicking a cell should allow a user to place a flag indicating they think the cell has a bomb. If the user is able to uncover all non-bomb cells they win, if the user uncovers a cell that has a bomb however they lose.
5/5
Automatically Reveal Neighbor Cells when 0 Neighbor Bombs
And finally, a functionality that is normally implemented in Minesweeper is the "recursive reveal". If a player clicks a cell that contains no neighboring bombs all adjacent cells should be automatically uncovered. If any of the adjacent cells also have no neighboring bombs then it's neighbors can be uncovered and so on...
5/5
For visualisation purposes you can see how the recursive reveal is implemented.
5/5
Constraint Propagation Auto Solver
Most of the time when a player is able to with certainty uncover a cell knowing it is not a bomb or place a flag on a cell as they know it is a bomb they are utilising constraint propagation.
If a cell indicates it only has 2 bombs adjacent to it and there are only 2 uncovered cells then we can with certainty flag those cells as having bombs.
Alternatively if a cell only has 2 bombs and 2 of it's adjacent cells are already flagged then we can with certainty uncover the remaining cells.
By applying these 2 constraints we able to uncovered more of the grid, each time we uncover more of the grid we can apply the constraints again (hench the propagation)
For someone who is very adept at Minesweeper it could be good practice to play with the constrain propagation turned on. This only leaves the more challenging problems to solve and anything that would be trivial is already computed away.
15/15
If my explanation didn't make any sense the animation should make it clearer (I hope)
15/15