Associated Topics || Dr. Math Home || Search Dr. Math

### Minesweeper Puzzle

```
Date: 10/24/2001 at 10:23:55
From: Jonathon
Subject: Logic puzzle

After playing Minesweeper, a friend of mine came up with an
interesting problem that I cannot solve no matter what I try. He does
not know the answer or even if an answer exists; it was just a
passing idea. I am not convinced there even is a clear answer, but
anyhow, here goes.

For a square Minesweeper board (MxM) there is N number of bombs. For
those who don't play Minesweeper, the way Minesweeper works is that
every square that does not have a bomb on it receives a number that
states how many bombs are on the squares immediately next to it
(in any direction).

For example, if X denotes a bomb, a 3X3 board could look like this:

X X X
X 8 X  sum of all numbers = 8      the maximum case for a 3X3 as far
X X X                              as I can tell is 2 3 2
X X X
2 3 2
sum total 14.

The question is whether for this general case (of an MxM board with N
bombs) you can find the maximum value of the sum of all the numbers
that are not bombs.

I tried solving it for 3X3 and 4X4 in hopes of finding a pattern, but
none emerged. I got lost trying anything of dimensions more than
that. Can it be solved, and if so how?
```

```
Date: 12/04/2001 at 17:07:58
From: Doctor Peterson
Subject: Re: Logic puzzle

Hi, Jonathon.

This problem has been on my mind from time to time, and I want to make
sure you get some kind of answer, since no one appears to have
responded after more than a month. It's really a rather interesting
little question, and though I don't have a real answer, you might like
to hear a few of the thoughts it has generated.

First, another math doctor noted an interesting symmetry: what we can
call the "complement" of a bomb pattern (replacing bombs with empty
spaces and empty spaces with bombs) has exactly the same sum, which I
will call the "score" of the pattern. For your example,

2 3 2
x x x = 14
2 3 2

the "complement" is

x x x
4 6 4 = 14
x x x

Why does this happen? Because you can count the score either by
looking at each empty space and adding up the number of bombs in
neighboring spaces, or by looking at each bomb and adding up the
number of neighboring empty squares to which it will add a point.
These produce the same total, and will be swapped if you swap bombs
and empty spaces.

The only thing I can see that we gain from this is that we can choose
to look only at patterns in which no more than half the spaces have
bombs. Also, it provides a simple way to draw and score a pattern; I
just put circles in the places where I want to have bombs, and in each
circle I write the number of empty spaces around it:

+---+---+---+
|   |   |   |
+---+---+---+
|(4)|(6)|(4)| = 14
+---+---+---+
|   |   |   |
+---+---+---+

An observation I made is that you can recognize a "local maximum"
(that is, a pattern that has a higher score than any pattern obtained
from it by adding or removing bombs, and is therefore a possible
candidate for the absolute maximum) by certain rules. Look at each
bomb: if more than half of its neighbors are bombs, then the score can
be increased by removing that bomb. Look at each empty space: if more
than half of its neighbors are empty, then the score can be increased
by adding a bomb there. If neither is true, then you have a local
maximum; you can't increase the score by changing any one space. You
can extend this by considering what it would take to increase the
score by sliding a bomb into a neighboring empty space; this is
particularly likely if a space is exactly half surrounded by bombs.

(A local maximum is similar to the say water will find the lowest
point in a region, by flowing downhill to a lower area. It may not
always find the very lowest point in the whole region, but instead
flow into a high mountain lake surrounded by hills; but wherever water
collects will be a local minimum.)

This provides one way to try to find a maximum. Start by placing a
bomb anywhere, and proceed from space to space placing a bomb in any
square that is not yet at least half surrounded by bombs. Once you
have made this decision in every square, some spaces that had been
previously checked may have more neighbors now; go back over them and
check each space to see if the score can be increased, doing so where
possible. When you can go through every space and change nothing, you
have a local maximum.

One thing I've observed is that these optimal patterns are based on a
sort of tension, as often occurs in other problems where there is a
non-trivial maximum or minimum. On one hand, there is a "compression"
force making the bombs want to cluster in the middle, where they have
more neighbors than at the edges; on the other hand, there is an
"expansion" force making them want to leave space between them in
order to increase their count. Together these cause the pattern to be
about half full, and evenly distributed. In fact, my first thought was
that the optimum pattern might be a checkerboard:

+---+---+---+---+
|(2)|   |(3)|   |
+---+---+---+---+
|   |(4)|   |(3)|
+---+---+---+---+ = 24
|(3)|   |(4)|   |
+---+---+---+---+
|   |(3)|   |(2)|
+---+---+---+---+

But though this is a local maximum, each bomb has too few neighbors;
the score can be increased by sliding some bombs around to make
stripes:

+---+---+---+---+
|(2)|   |(4)|   |
+---+---+---+---+
|(3)|   |(6)|   |
+---+---+---+---+ = 28
|(3)|   |(5)|   |
+---+---+---+---+
|   |(3)|   |(2)|
+---+---+---+---+

You can imagine shaking a given pattern a bit and letting everything
fall back into place, like a crystal being reheated and forming a
purer crystal. Such analogies are often helpful in visualizing how
things work.

It appears to me that the pattern for all sizes may be this pattern of
alternating stripes, as in the 4x4 case, which is the best I've found:

+---+---+---+---+
|(2)|   |(4)|   |
+---+---+---+---+
|(3)|   |(6)|   |
+---+---+---+---+ = 30
|(3)|   |(6)|   |
+---+---+---+---+
|(2)|   |(4)|   |
+---+---+---+---+

At this point it might be useful to use a computer to test my
conjecture, and then come back to the theoretical side and see if I
can prove the stripe pattern is really optimal.

This is a nice example of how a new problem arises in math. We think
about some object in reality, or in a game, or in some existing area
of math, ask a question about it, and then look for ways to study the
object. We develop a terminology for talking about it and procedures
for testing claims, make conjectures and look for ways to prove them.
Often we can make analogies to known areas of math, which may either
provide a way to solve the new problem using existing methods, or
provide a new way to look at the existing ideas that may be fruitful
in the old field. I don't know that this will turn out to be _that_
interesting, but it is certainly fun to pursue as far as we've gone,
and seems likely to hold a few more little surprises. Who knows? You
may someday hear that someone has written a book about Minesweeper
patterns, and you will have been the start of it!

Thanks for a fun problem.

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search