Minesweeper Solver
An Assembly and C Based Program
Background
Minesweeper is a very popular game, which is freely available in multiple platforms. The objective of the game is simple: In a minefield, extract all the minefields without detonating any minefield. Please read the Wikipedia article which explains in detail how the game works. You can also play a free online version of the game.
This project was part of my ECE 2035 class - Programming for Hardware/Software Systems. Those who have played minesweeper realize that the game can be very hard to complete, and making an automated solver for the game is equally challenging when a randomly generated minefield is given as the input to the solver.
Algorithm
Here is a high level overview of how the solver works:
- First, pick a random square. Check to see if it is on the corner or on the boundary or inside. This will determine the number of unopened boxes or the boxes which can be flagged near the selected square.
- Make a necessary guess over there. It would open with either a mine in which case as well I am fine because it has to be a necessary guess. Otherwise as well I am fine and it opens with a count. The count will tell how many mines are near it.
- If the Number of unopened squares - Count = 0, then flag all the boxes around that count because those boxes for sure have a mine.
- If the Number of flags surrounding the square = count, then open all the neighborhood squares because they do not contain any mines.
- If the Number of unopened squares - Count > 0, then we cannot make a single box inference. Make a necessary guess then to open the box.
