This is a sample MineSweeper app that I've been working on.
You can mail feedback to: seanwhalen@comcast.net
If all you see is a gray box, then you probably need to download Java
from:
Sun
Microsystems'
Java page.
Source code for the game is available here:
Zipped
Minesweeper source files.
The Basics:
To start
a game, press "New" from the options menu. The game is
identical to the Minesweeper game that ships with MS Windows.
When you think you know where a mine is,
right-click
on the square to mark it. If you think a square is safe,
left-click on it
to make it disappear. You win the game when you have marked all
the mines
accurately.
If you want a hint, press the hint
button. If
the hint software finds a safe square it will turn green. If it
finds a
mine for you, the square will turn pink. You'll need to right- or
left-click on square that lights up, as appropriate.
The hint engine is programmed to only use the
information
that is shown on the screen, so sometimes it gets stuck and has to
guess.
When the hint engine is running in Robot Mode, the “Start” button becomes a “Pause” button. Hitting the “Pause” button will stop the application and let you take over again. The “Pause” button sets a flag in the Robot thread that tells it to quit.
The Details:
The hint engine works by looping through all
the
squares on the screen. Squares that have not yet been revealed
are
ignored. Squares that don't border on any bombs are skipped over
also.
Each revealed square that borders some number of bombs is
analyzed as it
if were the center square in a group of nine. The code counts the
number
bordering squares that have already been flagged.
At this point, there are 3 basic rules that are
applied:
First, the it checks to see if the number of bombs
neighboring the square is equal to the number of bordering squares that
have
already been flagged. If so, then all remaining unrevealed
squares are
safe and can be tapped.
In the picture below, the center square is being
analyzed.
It has one neighboring bomb, and one neighboring flag.
Therefore,
all unknown squares (the "X"s) are safe and can be tapped:
|
|
X |
|
1 |
X |
|
|
X |
If that rule was not successful, the system checks
to see if
the number of unrevealed neighboring squares is equal to the number of
bombs
bordering the square, minus the number of bordering squares already
flagged.
If those numbers are equal, then all the unrevealed neighboring
squares
are bombs and they can be flagged.
In the picture below, the center square is
known to
have 2 neighboring bombs. It also only has 2 neighboring squares.
Therefore all the unknown squares (again, the "X"s) can be
flagged as bombs.
|
X |
X |
|
2 |
2 |
|
|
|
The third rule is a means of reusing information
gathered
while applying the second rule above. The analysis of a square might
not lead
to a definite conclusion about safe squares or bombs for that square,
but it
can produce information useful in the analysis of other nearby squares
by
passing along a fact like "cells X1Y1 and X2Y1
must contain 1 bomb". If the next square being analyzed only
touches
one other square, then that fact can be put to use.
In the picture below, nothing can be absolutely
determined
by analyzing the cells surrounding the cell with the "1" (left of
center). But the code can determine that the "X" squares south
and south-east of it have a bomb. That information is passed to
the cell
containing the "2".
When the "2" cell is analyzed its number is
reduced by the number of bombs known to be in the unrevealed squares
related to
the "1" cell that was analyzed before it. So, the "2"
is treated as if it were a "1", and those two "X"s are
ignored. That leaves a bomb count of "1" and only one
"X" square (lower right) to think about. Therefore, the square
in the lower right is known to be a bomb.
|
z |
|
|
|
1 |
2 |
1 |
|
X |
X |
X |
When the hint engine loops through the cells again, it will find the
"1" in the right-center, and based on the first rule, the
"X" to it's south-west will be determined to be safe and it will be
tapped.
|
z |
|
|
|
1 |
2 |
1 |
|
X |
X |
|
Then it will start over with the original "1". Now there's
adequate information to determine that the bomb is due south:
|
|
|
|
|
1 |
2 |
1 |
|
|
|
|
That's it! Repeat as necessary until all the
bombs are
discovered or no more inferences can be made.
Really Deep Details (technical
description):
Scanning the perimeter of a cell is done by using a
structure that stores the offsets needed to touch the 8 surrounding
cells.
This is a two dimensional integer array (8,2) where there are 8
pairs of
2 numbers and the 2 numbers range from -1 to +1. The index starts
at zero
for due north and continues clockwise to seven, which is north-west.
The
offset for the cell directly north is 0,-1 and the offset for the cell
above
and to the right is +1,-1. Going up is a negative move on the
Y-axis because
the origin point is in the upper left.
Here's a table that shows how the Box array is filled:
7(-1,-1) |
0(0,-1) |
1(1,-1) |
6(-1, 0) |
Center |
2(1, 0) |
5(-1, 1) |
4(0,1) |
3(1,1) |
So, for
example,
the code to count how many of the cells around cell (i,j) have already
been
flagged uses the box structure like this:
for (int b =0; b <= box.length -1; b++){
if( API.getIsFlagged( i+ box[b][0], j+ box[b][1]) )
flagCount++;
}
When the box array is built certain sets of offsets
are
considered special. Special in this case means that they, as a
set,
completely fall inside the perimeter of some other cell. In the
example
above, the cells to south and south-east of the first "1" fall
completely within the perimeter of the cell with the "2" in it.
In general, any pair cells to the south and south-east of a cell
will
also be to the south-west and south of the next cell to the east.
To store them, the index values of the Box array for
those
offsets are added together as a bitmap, and the bits are used as an
index into
a hashMap, referred to as the sharingMap. The sharingMap stores
the bits
and a pair of integers representing an offset that points to the cell
that those
cells can be shared with. In other words, information about cells
to the
south and south-east of some point can be shared with a cell to the
east of
that point.
Here's some code that shows the sharingMap being
used:
minePoint[] shareTo = new
minePoint[1];
shareTo[0] = new
minePoint(1,
0); //share to the east, which is X+1, Y+0.
boxSet =(int)Math.pow(2,4) +
(int)Math.pow(2,3) ;
sharingMap.put(Integer.toString( boxSet ) ,shareTo );
The sharingMap lets the system know what cells are available to share
data
with, given a set of unrevealed squares along the perimeter of any cell.
A note here about the code: The sharingMap
stores an array of points, not just one single
point. This is because information about sets of squares can be
relevant
to more than one other cell. For instance, again referring to the
last
colored example above, information about cells to the south and
south-east is
clearly relevant to the cell to the east -- that's the example that was
worked
out -- but that information is also relevant to the cell 2 points down
on the Y
axis. So, the system can get a little more bang for the buck by
adding a
second element in the ShareTo array that gets put in the sharingMap:
shareTo[1] = new minePoint(0,
2);
//point 2 spaces south.
Here is an example of how that could be useful. When
the
system analyzes the "1" cell below, it will come up empty, no
conclusion available. But information about the 2 neighboring
"X"s can be passed to the "4", which is 2 columns over.
With information about those 2 "X"s, the system can make a
solid conclusion about the other squares surrounding the "4".
Just passing the information south, to the second "1", doesn't
do any good, because that "1" doesn't benefit from the passed
information, in this layout.
So, because only 1 of the uncolored "X"s
is a mine, the other 3 "X"s surrounding the "4" can be determined to
be bombs:
|
|
X |
|
1 |
X |
4 |
X |
1 |
X |
X |
|
How is the sharingMap used? When the system
searches
for bombs by comparing the number of neighboring unrevealed squares to
a
cell's number of neighboring bombs, it also adds up the index
numbers from
the Box array where it finds unrevealed squares. If that
subroutine can't
make a determination about the location of a bomb, it passes back the
indexes
that it worked with from the Box array. The index numbers are
passed back
as a bitmap as mentioned above.
Then the code tests to see if the bits are for a set
of
points that can be shared by looking in the sharingMap, like this:
boolean bitsSharable =
sharingMap.containsKey(Integer.toString(bits));
if ( bitsSharable ){
...etc...
}
If those bits are sharable then the code pulls the array of points
(really,
offsets) to share with. Then it calls rule#1 and rule#2 again
with the
adjusted X/Y coordinates. So those are the structures: an
array, a
bitmap, and a hashMap of bits and arrays.
Here you might be thinking, "hey, so is it
recursive?", and the literal answer is something like "probably next
week", but it deserves some pre-code discussion anyway. It is
certainly imaginable that cell B can pass information on to cell C if
and only
if cell B is itself helped out by cell A, and recursion is one answer
to this
situation. Picture that as an eastward push of information
A->B->C.
Bear in mind that C might not be able to use B's
information. C
might really need information from D, so recursion is nice, but doesn't
really
guarantee that the system will route its information to every cell that
can use
it.
In the example below, the "4" cell in the center
can flag its north and south squares only if it gets information from
both the
east and the west.
|
|
X |
|
|
1 |
X |
4 |
X |
1 |
1 |
X |
X |
X |
1 |
This suggests that an additional hashMap could be used that uses
the X/Y
coordinates of cells with information coming to them, along with a
structure
that stores the bits of the squares being described, and the number of
bombs the
squares those bits point to contain. Recall that the bits are a
bitwise
sum of numbers that are index values into the Box array, which stores
the 8
pairs of offset values that help refer to cells bordering the cell
being
analyzed.
With such a Map, every revealed cell on the board
would get
a chance to contribute to the extra information a particular cell has.
It
would look a little like this:
KEY(x/y) |
Bits |
Bombs |
3/9 |
3 (n, ne) |
1 |
7/4 |
12(e, se) |
1 |
7/4 |
96(w, sw) |
1 |
8/6 |
24(s, se) |
2 |
If a Key like "7/4" is already found in the table,
the data stored for that key can be replaced with one that has one
additional
element. The chart above shows Bits and Bombs as 2 separate
fields, but in
code they would either be two properties of an object or two fields in
an (n,2)
integer array.
Recursion could be part of filling such a table, along with plain old
looping.