Minesweeper solver

$ ./minesweeper -n -b 0 game.txt

The argument '-b 0' is the easiest predefined board. The predefined boards are:

1. 8x8 grid with 40 mines (beginner)
2. 16x16 grid with 40 mines (normal)
3. 30x16 grid with 99 mines (expert)
4. 78x21 grid with 450 mines (insane)

An example of a game.txt file is:

Minesweeper 8x8 grid with 10 mines
........
........
........
........
........
........
........
........

Solution encrypted with seed 1327442006
8 34?1.1
!32? !31
833 3315
1 2!275*
*5.4826?
28?88?8.
3?13!212
 425!*.*

To make a move edit the first grid of '.'s to either a '?' if you think tile is not a mine or a '!' if you think it is.

For example, we could replace a random '.' with a '?':

........
........
........
........
....?...
........
........
........

We then process our input from game.txt using minesweeper:

$ ./minesweeper -v game.txt

This changes the game.txt file by replacing '?'s with numbers signifying how many bombs surround that tile.

The first grid of our game.txt file now looks like this:

........
........
........
........
....*...
........
........
........

This means we have hit a bomb and lost the game. Or we could just replace the '*' with a '!' and pretend it never happened.

Continue editing the game.txt file by replacing '.'s with '!'s or '?'s, and processing the game.txt file.

To apply the automatic solver use minesweeper_solver:

$ ./minesweeper_solver -v game.txt

The automatic solver will replace as many '.'s as possible. If the solver cannot make any moves it will make a guess.

Move around with the arrow keys, mark mines with space and mark not-mines with enter.

Start new games by pressing '0', '1', '2' or '3'.

Start automatically solving the game by pressing 'a'. More keys are explained in the help menu (accessed through 'h').

This method searches for two simple situations:

1. When a tile is surrounded by x mines and where x mines have been marked on neighboring tiles. In this situation we can mark the unknown neighboring tiles as being not mines.

!..    !??
.1. -> ?1?
...    ???

1. When a tile is surrounded by x mines and where the sum of the unknown neighboring tiles and the neighboring tiles being mines is x. In this situation we can mark the unknown neighboring tiles as being mines.

!2.    !2!
132 -> 112
 1.     1!

This method works by stepping through all tiles and, when either of these situations occurs, mark neighboring tiles. Continue to step through all tiles until a complete search of the tiles did not find either of the situations.

This methods assumes a unknown tile either is or is not a mine. We then use the previous step to propagate knowns and unknowns. If we end up in an invalid state, we know the original unknown tile is the opposite of our assumption.

An invalid state is a game that contains a situation where a tiles indicated number of neighboring mines is in conflict with the actual neighboring tiles. There are two such invalid situations for a tile:

1. A tile has no unknown neighbors and the indicated number of neighboring mines is not equal to the number of actual neighboring mines.
2. There is a greater number of actual neighboring mines than the indicated number of neighboring mines.

...  Board  
111  

.?.  Assume (0,1) is not a mine
111  

!?!  Propagate knowns and unknowns
111  (1,1) is invalid as it has 2 neighboring mines

...    !..    !??
111 -> 111 -> 111 -> Invalid state for tile (2,1)

This method works by assuming every unknown tile is both a mine and not a mine. When this step gives us new information, we propagate knowns and unknowns and. We continue these steps until no assumptions were proven false.

This method iterates through all permutations of unknown tiles being set as a mine and being set as not a mine. If a specific tile is always either a mine or not a mine for all valid permutations, we know that the tile is or is not a mine, respectively.

This is the solution mentioned on Wikipedia's Minesweeper page.

This step can solve situations our previous steps cannot. An example of this is (from Wikipedia):

 1.
12.
...

There are 5 unknown tiles (.). This means there are 2⁵ = 32 permutations. Of these permutations, 4 lead to valid boards.

0 1 0 1 0
0 1 1 0 0
1 0 0 1 0
1 0 1 0 0

The fifth number in these 4 permutations is always 0, meaning not a mine. This, in turn, means we now know one of the tiles is not a mine:

 1.
12.
..?

This method has an exponential running time in the number of unknown tiles. To minimizes the number of unknown tiles we separate them into clusters. Tiles in different clusters can not affect each other, and can therefore be solved separately from each other. This optimization lets us go from 10 unknowns (2¹⁰ = 1024 permutations) to 2 * 5 unknowns (2⁵ + 2⁵ = 64 permutations). This optimization, however, is not enough. We also have to ignore clusters with more than 15 unknown tiles.

If the previous methods cannot give us the answer, guessing is all that is left.

A guess is defining a tile as not being a mine. Making the guess involve these considerations:

1. The number of neighboring non-mines.
2. The number of neighboring unknowns.
3. The number of neighboring mines.
4. The chance of the tile not being a mine.
5. Whether knowing a tile results in further propagation (from step 1).

The chance of the tile not being a mine is based on either:

• The number of unknown tiles versus the number of mines left in the game.
• The worst chance based on neighboring tiles with a defined number of neighboring mines.

I converted these 5 considerations to values between 0 and 1 and gave each tile a score.

score = number_of_neighboring_non-mines * 0.3 +
        number_of_neighboring_unknowns  * 0.1 +
        number_of_neighboring_mines     * 0.3 +
        chance_of_not_hitting_a_mine    * 2.5 +
        lead_to_propagation             * 1.0

I modified these values until I stopped noticing particularly bad guesses.

4MB several minutes long gif file