CIS 120 Homework 1: Minesweeper

Due Friday January 25, 2008 at 5 PM. There are three required problems in this homework.

Important notes:

• If your file doesn't compile, you will not earn any credit for the assignment.
  
• The homework can earn a total of 100 homework points as described below.
• File, class, and method names should be exactly as described below. However, you may if needed add helper variables and methods.
• Each method's return type, as well as the number, order, and types of parameters must be as specified. Parameter names don't have to be the same.

Introduction

Minesweeper is a game many are familiar with, as it is often preloaded on most operating systems. If however, you do not have experience with it, spend a few minutes reading the Wikipedia article. The version of minesweeper we will be using for this assignment is slightly simplified. We will provide you with the files needed to actually play minesweeper, however it will be your job to write a solver. In order to help you we have broken the problem down into three separate steps, each of which is ultimately necessary to completely solve a given minesweeper board.

Furthermore, we have provided you with Javadocs, which can be used to gain a clearer understanding of the supplied code and of the code we expect from you. The javadocs for Solver illustrates the methods we expect in your code (note: These are just the minimum method requirements, if you feel the need to write helper methods, go ahead!) As always if there are any questions regarding this writeup, the javadocs or problems with your implementation of the homework don't hesitate to post on the Bulletin Board: that's what it is there for.

Here are some files you will need:

• hw1.jar

• Javadocs

Problem 1: Looking at Cell Neighbors (30 points; files to submit: Solver.java)

Before you begin, you need to tell DrJava where to find the hw1.jar file. Do this under Preferences, Resource Locations, Extra Classpath. Click the add button and type the full path of the jar file.

After loading the jar file, you have two options, one is to copy and paste each interaction shown below, while the other is to download the .hist file and run the interactions automatically.  To do the latter, under the DrJava Tools menu select
"Load interactions history as script...".  The output below shows each interaction (marked with a >) followed by the result from that interaction.  As well as the textual output below, the graphical GUI will also provide a consistant view of the game state.

Sample Interactions (Mine1.hist)

Welcome to DrJava.
> Minesweeper game = new Minesweeper(10,10,10);  // Create a game instance of (10 [mines], 10 [rows], 10 [columns])
> game.explore(1,1)                 	         // Look for mines at location (1 [row], 1 [column])
> game.printBoard()                              // Show current state of board
..........                                       // Row 0
.1........                                       // The cell at (1,1) has 1 mine nearby.
..........
..........
..........
..........
..........
..........
..........
..........					 // Row 9
> game.mark (2,1);                       	 // Mark a potential mine at (2 [row], 1 [column])
> game.hint()                            	 // Ask the game for a hint
> game.printBoard()
..........
.1........                              	 // What we knew before
.*........                               	 // Our guessed mine
..........
..........
..........
..........
.1........                              	 // The hint!
..........
..........
> game.explore(2,2)     	                 // Look for mines at location (2 [row], 2 [column]) (Causes you to step on a mine)
BOOM
> game.printBoard()     	                 // Show current state of board (Mine has been triggered)
00001@101@                              	 // The complete board is displayed.
0111111011
01@1011100					 // The mind we triggered is at (2,2)
011101@100
2210011100
@@21111000
23@11@2100
011112@100
0111011100
01@1000000

Now that you have a basic understanding of the Minesweeper class' functionality, use the javadocs and explore the different methods that we have provided. After looking at the javadocs you should now be ready to think about how to code a solver. There is a very simple solution, detailed below that makes use of the hint method so lets use that as a starting point. This class should be saved in a file called Solver.java.

class Solver {
 public Minesweeper game;
 public Solver () {
   game = new Minesweeper(10,10,10);
 }

 public int simpleSolver() {
   while (!game.isSolved()) {
       game.hint();
   }
   return game.getNumHints();
 }
}

Sample Interactions (Mine2.hist)  

Welcome to DrJava.
> Solver s = new Solver();
> s.simpleSolver()
90

While the above class works, it uses entirely too many hints and is really cheating, therefore we will try to find a way to minimize the number of hints we are required to use. The first step in making this adjustment is to find out how many neighbors to a particular cell have been marked as bombs. One way to do this is to check each of a cell's eight neighbors like the method below.

These neighboring cells are accessed as in the following picture:

/** Determine the number of neighbors of cell (i,j) that have been 
 *  marked as bombs. */
public int markedNeighbors1(int i, int j) {
   int marked = 0;
   if (game.isMarked(i-1, j-1))
      marked++;
   if (game.isMarked(i-1, j))
      marked++;
   if (game.isMarked(i-1, j+1)) 
      marked++;
   if (game.isMarked(i, j-1)) 
      marked++;
   // skip (i,j)
   if (game.isMarked(i, j+1)) 
      marked++;
   if (game.isMarked(i+1, j-1)) 
      marked++;
   if (game.isMarked(i+1, j))   
      marked++;
   if (game.isMarked(i+1, j+1)) 
      marked++;
   return marked;
 }

This method is good, but notice that at every probed location, we are checking the same condition isMarked and we are performing the same action marked++. In an instance like this, where the same action is being repeated many times, it is good programming practice (and much less cumbersome) to use nested loops to check all of the neighbors of the cells. Note that when we use the loops, we have to skip the case where the loop indices are the same as i and j.

public int markedNeighbors2(int i, int j) {
  int marked = 0;
  for (int k = i-1; k <= i+1; k++) {
    for (int l = j-1; l <= j+1; l++) {
       if (! (k==i && l == j)) {  			//skip (i,j)
          if (game.isMarked(k,l)) {
             marked++;
          }
       }
    }
  }
  return marked;
}

One problem still remains though at the border of the grids, at what are known as corner cases (see below).

Sample Interactions (Mine3.hist)

Welcome to DrJava.
> Solver s = new Solver();
> s.markedNeighbors1(1,1)
0
> s.markedNeighbors2(1,1)   // markedNeighbors1 and markedNeighbors2 behave the same
0
> s.markedNeighbors2(0,0)

ArrayIndexOutOfBoundsException: -1
 at Minesweeper.isMarked(Minesweeper.java:104)
 at Solver.markedNeighborsLoop(Solver.java:46)
 at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
 at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
 at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
 at java.lang.reflect.Method.invoke(Method.java:585)

The cells on the edges and corners of the grid have fewer than eight neighbors, so we must not check all sides of those cells. One way to improve the markedNeighbors method is to see if the probed location is a valid location in the grid.

public int markedNeighbors3(int i, int j) {
   int marked = 0;
   // check the eight neighbors of the square, being careful of the edges.
   if (i>0 && j>0 && game.isMarked(i-1, j-1)) 
      marked++;
   if (i>0 && game.isMarked(i-1, j))
      marked++;
   if (i>0 && j<(game.getWidth()-1) && game.isMarked(i-1, j+1)) 
      marked++;
   if (j>0 && game.isMarked(i,   j-1))
      marked++;
   if (j<(game.getWidth()-1) && game.isMarked(i,   j+1))
      marked++;
   if (i<(game.getHeight()-1) && j > 0 && game.isMarked(i+1, j-1))
      marked++;
   if (i<(game.getHeight()-1) && game.isMarked(i+1, j))
      marked++;
   if (i<(game.getHeight()-1) && (j < game.getWidth()-1) && game.isMarked(i+1, j+1))
      marked++;
   return marked;
}

We can also improve the version that uses loops by being careful of the starting and ending indices of the loop. If we previously started with an index less than 0, we will now start with 0 instead. If we previously ended with an index that is greater than the last index of a row or column, we will now end with that index instead. (This is a version we should use in Solver.java so it is just called markedNeighbors).

/** Determine the number of neighbors of cell (i,j) that have been 
 *  marked as bombs. */
public int markedNeighbors(int i, int j) {
   int marked = 0;
   for (int k = Math.max(i-1, 0); k <= Math.min(i+1,game.getHeight()-1); k++) {
      for (int l = Math.max(j-1,0); l <= Math.min(j+1,game.getWidth()-1); l++) {
         if (!(k==i && l==j)) {
            if (game.isMarked(k,l)) {
               marked++;
            }
         }
      }
   }
   return marked;
 }

For the first part of the assignment, your job is to write a method similar to markedNeighbors above that determines how many of the neighboring cells have not been explored. This method must be correct, even at the corners and edges of the grid.

Your method should look like:

/** Return the number of neighbors of cell (i,j) that have not yet been explored. */
public int unexploredNeighbors(int i, int j) {
 ...
}

Sample Interactions (Mine4.hist)

> Solver s = new Solver()
> s.unexploredNeighbors(1,1)
8
> s.unexploredNeighbors(0,0)
3
> s.game.explore(1,2)
> s.unexploredNeighbors(1,1)
7

Problem 2: Reasoning about the grid (30 points; file to submit: Solver.java)

Once we can count the number of marked neighbors, we can make deductions about them and explore the rest of the board.

For example, if the game has told us that there are X neighbors containing bombs near a particular cell, and we have marked X of those neighbors as being bombs, we know that it is safe to explore the rest of the neighbors of that cell. The following method checks to see if this condition is true, and if it is, explores all neighbors that have not been marked as bombs and have not been previously explored. It returns whether any unexplored neighbors were found.

/** The neighbors of a cell can be explored if 
 * the cell has been explored and *all* of the nearby bombs have been marked.
 * @return whether any neighbors were explored.
 */
boolean exploreNeighbors(int i, int j) {
 boolean changed = false;
 if (game.isExplored(i, j)) {
    // # of marked neighbors is equal to # of neighbors containing bombs 
    if (markedNeighbors(i,j) == game.getNeighboringBombs(i,j)) {
       for (int k = Math.max(i-1, 0); k <= Math.min(i+1, game.getHeight()-1); k++) {
          for (int l = Math.max(j-1,0); l <= Math.min(j+1, game.getWidth()-1); l++) {
             if (!(k==i && l==j)) {
                if (!game.isMarked(k,l) && !game.isExplored(k,l)) {
                   changed = true;
                   game.explore(k,l);
                }
             }
          }
       }
    }
 }
 return changed;
}

Furthermore, we can use the information about the neighboring cells to conclude that some of those cells are bombs. The unexplored neighbors of a cell can *all* be marked as bombs if the cell has been explored and the number of marked neighbors + the number of unexplored neighbors is equal to the number of nearby bombs.

For the second part of the assignment, write and test this method, in the same file Solver.java:

/** The neighbors of a cell can *all* be marked as bombs if 
 * the cell has been explored and the number of unexplored neigbors is 
 * equal to the number of nearby bombs. If any such cells are found, mark them.
 *
 * @return whether any neighbors were marked as bombs.
 */
boolean markNeighborsAsBombs(int i, int j) {
 ...
}

Sample Interactions (Mine5.hist)

> Solver s = new Solver();
> s.markNeighborsAsBombs(5,5)       // Unexplored cell, doesn't do anything
false
> s.game.printBoard()
..........
..........
..........
..........
..........
..........
..........
..........
.......... 
..........
> s.game.explore(2,9)
> s.markNeighborsAsBombs(2,9)       // Can't mark any neighbors here
false
> s.game.printBoard()
..........
..........
.........0
..........
..........
..........
..........
..........
..........
..........
> s.game.explore(4,0)              // Explore (4,0) and several neighbors
> s.game.explore(3,0)
> s.game.explore(3,1)
> s.game.explore(4,1)
> s.game.printBoard()              
..........
..........
.........0
01........
22........
..........
..........
..........
..........
..........
> s.markNeighborsAsBombs(4,0)      // We found some bombs!
true
> s.game.printBoard()
..........
..........
.........0
01........
22........
**........ 
..........
..........
..........
..........

Problem 3: Final Solver Construction (40 points; file to submit: Solver.java)

We now have the pieces to make a solver:

The first step is to use exploreNeighbors and markNeighbors to look at all of the explored cells of the board and determine whether any of their neighbors can also be explored or be marked as bombs. This method should return whether any changes have been made to the board.

/** Examine all cells of the board using markNeighborsAsBombs and exploreNeighbors in row/column order.
 * @returns whether any updates were made to the board. */
public boolean checkBoard() {
 ...
}

The next step is to check the board over and over again until there are no more changes.

/** Repeatedly check the board until no change. */
public void makeAllDeductions() {
 ...
}

The final step is to create the solver that asks for a hint when it doesn't know what to do, and uses those hints to make deductions about the board.

/** Solve the game by simple reasoning, asking for hints when stuck. 
 * 
 * @returns the number of hints needed to solve the board. */
public int solve(){
   while (!game.isSolved()) {
      game.hint();
      makeAllDeductions();
   }
   return game.getNumHints();
}

For the last part of the assignment, your job is to fill out the code for checkBoard and makeAllDeductions.

Sample Interactions (Mine6.hist)

> Solver s = new Solver();
> s.checkBoard()
false
> s.game.printBoard()
..........
..........
..........
..........
..........
..........
..........
..........
.......... 
..........
> s.game.explore(5,5)
> s.game.explore(5,6)
> s.game.explore(5,7)
> s.game.explore(5,8)
> s.checkBoard()
true
> s.game.printBoard()
..........
..........
.......... 
..........
......1100
.....11000
......2100
.......100
......1100
......0000
> s.makeAllDeductions()
> s.game.printBoard()
00001@101@
0111111011
01@1011100
011101@100
2210011100
@@21111000
23@11@2100
011112@100
0111011100
01@1000000

Extra credit (file to submit: Minesweeper2.java)

Sample Interactions (Mine7.hist)

Welcome to DrJava.  
> Minesweeper2 game = new Minesweeper2(10,10,10)
> game.explore(4,4)
> game.printBoard()
..........
...111....
...101....
..1101....
..1001....
..2111....
..........
..........
..........
..........
> 

class Minesweeper2 extends Minesweeper {
  public Minesweeper2(int requestedBombs, int height, int width) {
    super(requestedBombs, height, width);
  }
  public void explore (int i, int j) {
      // Override this method to change the behavior of explore....
  }
}