Steve’s Blog

Just another compsci weblog

Minesweeper Solver in Lisp

Everyday I wake up for work at 6:00am and get home at around 8:00pm. Since this only leaves me with two hours of spare time I try to get something constructive done during both 70 minute train rides. As much as I try, however, a little Minesweeper always manages to get played. While playing the other day, I was examining a small subset of the grid when I noticed that when I calculated all the possible mine positions for that isolated subset, it became apparent that there was a spot that couldn’t have a mine (normally when I play, I only examine a single cell to determine where mines may or may not be located). It was during this game that I decided to write a Minesweeper solver.
And it works pretty simply. When you examine a particular cell containing a number in a game of Minesweeper, it tells you how many adjacent spaces contain mines. For example, if you were to come across this configuration:

  A B C
1|? 0 0
2|0 1 ?
3|0 ? 0

You would know that there is one bomb which lies in either location A1, B3, or C2. Later it will become useful to also note which spaces do not contain mines. This will break each possibility into two groups: one group contains the spaces which have mines, the other contains spaces which do not. So our example above would be stored as:

mine-group: (A1), not-mine-group: (B3 C2)
mine-group: (B3), not-mine-group: (A1 C2)
mine-group: (C2), not-mine-group: (A1 B3)

As it turned out, writing code to divide these three unknown spaces into two groups was the hardest part. The function which does it is called ‘GenCombo’, and the function works by being passed in a list of elements to be divided – (a b c) for example – and a list of the group sizes, which in the above case would be size one for the ‘mine’ group, and size two for the ‘not mine’ group. The function then recursively pops an element off the first list and appends it to a particular group.

Now that the program can determine the possible configurations of a particular cell, there must be a way to combine them in order to reduce the total number of mine configurations. The particular configuration that made me realize how to do this looked like this:

  A B C D
1|? ? ? 0
2|0 1 1 0
3|0 0 0 0

The possible configurations for the number at position B2 are as follows:

mine-group: (A1), not-mine-group: (B1 C1)
mine-group: (B1), not-mine-group: (A1 C1)
mine-group: (C1), not-mine-group: (A1 B1)

Lets call these combinations C(B2).

The possible configurations for the number at C1 are:

mine-group: (B1), not-mine-group: (C1)
mine-group: (C1), not-mine-group: (B1)

This is C(C1).

To combine these, we take each possible pairing for each possibility and check for contradictions. To demonstrate, lets combine the first two possible configurations. To do this, we simply combine both ‘mine’ groups together and combine both ‘not mine’ groups together.

  (mine-group: (A1), not-mine-group: (B1 C1))
+ (mine-group: (B1), not-mine-group: (C1))
= (mine-group: (A1 B1), not-mine-group: (B1 C1 C1))

As we can see, there is a contradiction in this example in that there is an element that appears both in the ‘mine’ group AND in the ‘not mine’ group. What about two other pairs?

  (mine-group: (B1), not-mine-group: (A1 C1))
+ (mine-group: (B1), not-mine-group: (C1))
= (mine-group: (B1 B1), not-mine-group: (A1 C1 C1))

Aha, there are no contradictions, making this a viable combination. In total, there is one other viable combination for this example:

mine-group: (C1 C1), not-mine-group: (A1 B1)

If one were to plug this input into the code, the output returned would be in this form:

(
	(		; possible configuration 1
		(B1)	; mine group
		(A1 C1)	; not mine group
	)
	(		; possible configuration 2
		(C1)	; mine group
		(A1 B1)	; not mine group
	)
)

As you can see, it’s an ugly parenthetical mess. However its actually very simple: The function returns a list of possible configurations. Within each of these configurations, there are two groups. The first is the ‘mine’ group, and the second is the ‘not mine’ group. Within each of the groups, there is a number of ordered pairs which points to a place on the game board.

And that’s basically it. The game board is stored as a list, so the above example would be stored as: ‘(? ? ? 0 0 1 1 0 0 0 0 0). A function goes through each element in the list and generates the possible configurations for each individual cell, which would look like this:

'(nil nil nil nil 
nil ( ((A1) (B1 C1)) ((B1) (A1 C1)) ((C1) (A1 B1)) ) ( ((B1) (C1)) ((C1) (B1)) ) nil 
nil nil nil nil)

Phew. Next, a function takes this result, removes the nils, and reduces the list using
the Combine2Possibilities function, which would produce the output listed above.

Despite the output of this function being very ugly, it’s pretty versatile. Using some additional printing code, you can display the output in a number of different ways. In the example code, the original game state is printed first. Following the calculations, a list of possible mine location sets is printed out. But this output is hardly useful, so after that is a list of definite mine positions – positions that appear in every possible mine location set, as well as a list of definite not-mine positions. At the bottom is the most readable of all: the original game state with all definite mines and not-mines added.

Minesweeper Solver
(Note that in the code locations are represented as an ordered pair, not A1, B1, etc,.)

At the bottom is an example of it’s output using the example data provided in the code. ‘n’ means ‘not a mine’ – it’s possible to calculate this value for certain positions (those with no surrounding ‘?’s) but I’ll leave that as an exercise for the reader :)

Board before solution:
        1 ? ? ? ?
        1 ? ? 3 ?
    1 1 2 ? ? ? ?
    1 ? ? ? ? 1 ?
    1 2 ? 3 ? ? ?
      1 ? ? ? ? ?
    1 2 2 1 1 1 1
    1 ? 1
    1 ? 1
Possible mine location sets:
((5 0) (8 0) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 0) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (8 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (8 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))

Definite mine locations:
((3 7) (7 5) (4 5) (5 3) (3 3) (5 0))

Definite not mine locations:
((3 8) (8 5) (6 5) (5 5) (4 4) (4 3) (6 2) (7 2) (8 2) (8 3) (7 4)
 (8 4) (5 1) (5 2))

Board after solution:
        1 X ? ? ?
        1 n ? 3 ?
    1 1 2 n n n n
    1 X n X ? 1 n
    1 2 n 3 ? n n
      1 X n n X n
    1 2 2 1 1 1 1
    1 X 1
    1 n 1
2 comments

2 Comments so far

  1. anon November 17th, 2008 4:36 am

    ick camel case and close-parens-on-separate-line

  2. 360 January 3rd, 2011 2:06 pm

    This is actually one of the few good and understandable tutorials on solving minesweeper using constraints.

    I’m also making a minesweeper solver program, but unfortunately i don’t understand LISP… I’d really appreciate if somebody would write this algorithm (or some parts) in pseudo-code, python, pascal or c-like language or give me some useful links…

    Thanks!!

Leave a reply