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 by click the following link: Minesweeper Video Game
To better understand how the game works, you can play a free online version of the game here.
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. Obviously, the output to this solver will be a minefield with all the squares/blocks with mines marked with flags/defused.
Even though solving minesweeper is a very challenging task, relaxing some constraints of the game can make the task of developing the solver less challenging and achievable. One such constraint is that the first guess has to be necessary guess because of lack of information regarding finding a square with no mine in it to start the game. The solver/algorithm will succeed if it makes a necessary guess of opening a square, even if it can has a mine in it because we do not have enough knowledge about the neighboring squares.
Algorithm
Here is a high level overview of how the solver works:
Source Code for the algorithm can be found here for both the MIPS 32 bit ISA assembly and C based program:
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 by click the following link: Minesweeper Video Game
To better understand how the game works, you can play a free online version of the game here.
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. Obviously, the output to this solver will be a minefield with all the squares/blocks with mines marked with flags/defused.
Even though solving minesweeper is a very challenging task, relaxing some constraints of the game can make the task of developing the solver less challenging and achievable. One such constraint is that the first guess has to be necessary guess because of lack of information regarding finding a square with no mine in it to start the game. The solver/algorithm will succeed if it makes a necessary guess of opening a square, even if it can has a mine in it because we do not have enough knowledge about the neighboring squares.
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.
- For single square, we can make the following inferences in points 4, 5 and 6.
- If the Number of unopened squares (check the boundary condition here to determine unopened boxes) - 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 square because they do not contain any mines.
- If the Number of unopened squares (check the boundary condition here to determine unopened boxes) - Count > 0, then we cannot make a single box inference. Make a necessary guess then to open the box. e.g. If there are zero mines, then continue and open all the boxes around it.
Source Code for the algorithm can be found here for both the MIPS 32 bit ISA assembly and C based program:
| Mineweeper Solver Mips 32 Bit Assembly Code |
| Minesweeper Solver In C.zip |