MineSweeper for Lazy People

This is a copy of the original page (http://seanwhalen.home.comcast.net/~seanwhalen/minesweeper/), now part of the archive of
Onlinespiele-sammlung.de


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 

 

 

 

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 

 

 

 

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:
 



 

 

 

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.