Bryland Schoenck

MineSweeper contains a grid of cells in which a certain number of those cells contain mines. If you click on a mine, you lose. Your goal is to uncover the whole board and flag mines along the way. The numbers indicate the number of mines in a 3x3 area around it.

To put simply this is a MineSweeper solver, it determines the most and least likely cells to contain a bomb. MineSweeper is unfortunatly not a solved game; meaning no matter what strategy you put in place, you cannot guarenetee a win. Although, with certain strategy and/or probablistic calculations the rate of success can vastly improve, which is the goal of this solver.

The core principle, that will work in all senarios is the combinational computation. This simply finds all possible mine combinations given the current board state and compares the number of times a mine is in each cell. This solution gives themost accurate probablity of each cell being a mine. This solution is only used on the hidden cells that are ajacent to revealed cells as the others can be simply determined by: number of bombs left divided by number of cells left. The major downside of this strategy is the immeanse amount of time needed to compute all these combinations as it is an exponential time algorithm. Now that we have our strategy, we can add small fixes to improve the preformance and reduce the complexity of the computations needed.

The first major improvement is the logical calculation. This is a deterimistic approch to solving MineSweeper as it will deterimineif a cell is safe or a mine but not in between. Before we do our combinational calculation, we first see if we can find any cellsthat we can for sure deterimine if they are safe or not. This will reduce the number of cells and bombs we need to take into account when calculating. This improvement works by looking at each numbered cell and observing how many hidden cells are remaining in its 3x3 area and comparing it to the number of mines left for the number to be satisfied. For example; if we looked at a cell with a 4, if that cell had 3 hidden cells and 1 flagged cell (i.e. already determined to be a mine), we then know those 3 hidden cells also must be mines. This works in reverse as well looking for safe cells.

The other major improvement is the segragation step. This cuts up the bordering hidden tiles into groups to be calculated together. These groups are determined by their connectivity to each other as the effects of one cell in the group can impact the chances of other cells in the group. This helps by breaking the larger exponential computation into smaller, more managable computations. These groups can further help as we can deterimine which group is being manipulated by keeping track of our segragated groups and not recalculating groups that haven't changed.

There are many other small improvements that have been used to further decrease the computational time but ultimately they are just shaving off small bits from this massive exponetial calculation. Sometimes, we will run into situations, espeacially as we increase the board size and the number of mines, where non of our improvments can help and will take massive amounts of time to compute.

No, this "solver" does not solve MineSweeper, there will be occasions and situations where it could come down to a fifty-fifty chance, or it'll have to take a gamble on the least likely cell. Excperienced players, with enough time, could beat the win percentage of the sovler as this tool does not implement high level strategy, like prefenceally picking corner and edge cells. But what this tool can do, is play boards quickly (given no extreme cases occur) and be used as a teaching tool to those who wish to learn or improve at one of my favorite games; MineSweeper.