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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum