The game Minesweeper is a fun diversion, but even more fun would be to get the computer to solve it for us. I’ve written a basic solver for the version of Minesweeper from Simon Tatham’s excellent Portable Puzzle Collection, called Mines. My solver interacts with the game just like a human player would: by reading the screen’s contents and moving and clicking the mouse.

Here is a video of the solver in action.


Reading the screen

Reading the screen has two parts: getting the screen’s contents, and then interpreting them. The first part is simple in X, by using xdotool to find the window with the right name, xwddump to dump the window’s contents to a file, and Imagemagick’s convert to convert the image format into PNG.

Interpreting the contents is trickier. I followed the policy of “least robustness” — the reading will break if the window is too small, and relies on the specific way that Mines draws its board. Essentially, the steps are:

  1. Find the grid within the window by sending out a line diagonally from the top-left corner of the window until it hits the dark top or left edge. When we hit it, follow the edge back to the top-left corner of the grid.

  2. From the top-left grid corner, move into the top-left cell of the grid. Figure out its width by tracing the top edge of the cell until we hit the border of the cell to the right. Do this repeatedly until we hit the end of the grid. Now we know how many cells across are in the grid, and where they are positioned in the window.

  3. Do step 2 again, but in the vertical direction.

  4. Now we know where all the cells are in the window, and we can figure out where the numbers and flags are. We do this by looking at the colours of the pixels in the cells; fortunately each number has a unique colour. For example, if a cell has lots of blue pixels, then it contains the number “1”.

Working out where to move

The next step is to figure out which squares contain mines and which ones are safe. Other people have already come up with clever ways to do this (for example, see the Mines source code which contains a solver). I wanted something fast enough to watch, but simple and powerful. I first modelled the problem in MiniZinc.

int : width;
int : height;
int : w = width-1;
int : h = height-1;

% Does the cell contain a mine?
array [0..w, 0..h] of var bool : mined;

% Each clues is a triple (x,y,n), which means the cell at location
% (x,y) contains the number n.  If n is -1, then the cell contains a
% flag.
int : nclues;
array [1..nclues, 1..3] of int : clues;

constraint
  forall (c in 1..nclues)
    ( let { int : x = clues[c,1],
            int : y = clues[c,2],
            int : n = clues[c,3] }
      in if n == -1
         then mined[x,y] = true
         else mined[x,y] = false /\
              sum( [ bool2int(mined[x+i,y+j]) | i,j in [-1,0,1] ] ) == n
         endif );

I was pleased that the model is so simple. Now, to figure out if a cell is safe to click on, we “guess” that the cell has a mine in it. If the solver says that the problem is now unsolvable, then the guess was wrong which means that the cell is safe. The same thing can be done in the other direction: guess that the cell is safe, and if that’s impossible, then the cell must have a mine.

One truly wonderful feature of Mines that is not usually present in Minesweeper games is that it can generate “guaranteed solvable” puzzles. This is great for testing the solver, because it should be able to solve any puzzle that it’s faced with.

Making moves

Simulating mouse movement and clicking is easy with xdotool. A sample command looks like:

xdotool search --onlyvisible --name Mines
  mousemove --window %1 763 81 click 1
  mousemove --window %1 763 108 click 1
  mousemove --window %1 763 135 click 1
  mousemove --window %1 763 162 click 1

which means “find the window called Mines, move to pixel 763,81 in that window, then click, then move to 763,108 and click”, etc.

Going faster

With this set up, the solver can finish puzzles in about the same that it would take me to do it by hand. This is not good enough for me, so I tried to find the slowest part of the program and improve it.

A lot of time is spent in the thinking part, and a large component of that is due to the way I am using MiniZinc. For every cell that I test, I compile the MiniZinc program from scratch, and this is really slow.

Also, I’m not making good use of one of constraint programming’s strengths: constraint propagation. We’d be able to learn many safe and mined squares just by propagating the constraints without doing any search. Unfortunately this is currently impossible in MiniZinc.

I translated the model to be used with Gecode. With Gecode I can compile the program once, and I can ask it to do only propagation without search. I used the strategy of trying propagation first, and only if that learns nothing does the solver resort to a full search. The result is a much faster solver!

Conclusions, limitations and ideas

The end result is a solver that can usually finish a 30x16 grid with 99 mines (roughly equivalent to Windows Minesweeper expert mode) in about 20-30 seconds. However, there are some limitations.

  1. The solver doesn’t know how many mines are in the puzzle. This means that in some situations it gets stuck.

  2. At some window sizes it can’t read the grid properly.

  3. The interface is a bit rough around the edges and might crash if it sees something it isn’t expecting. Once it gets going and starts moving the mouse around and clicking madly, it can be difficult to interrupt.

The first limitation can be overcome by parsing the “Marked” line in the status bar at the bottom of the window. The other two could be fixed by a bit of programming effort.

The solver could be made faster by calling X library functions directly instead of dumping the window’s contents to a file and reading it back in. Also, the thinking part could be faster if it included some basic Minesweeper logic instead of always relying on the external constraint solver.

Get the source

The source code is available at GitHub. To compile it you will need GHC (and some packages from Cabal) and Gecode. To run it you will also need xdotool, xwddump and Imagemagick.