Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/