Due Wednesday, September 16, 2009 at 11am. The whole assignment is worth 100 points.
Minesweeper is a familiar game to many, since it comes preinstalled on many operating systems. If 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 separate steps.
We have provided you with javadocs which help to explain the supplied code. In addition, the javadocs for Solver illustrate the methods we expect in your submitted code. (Note: These are just the minimum method requirements; if you feel the need to write helper methods, you can, though you probably won't need any for this assignment.) If you have any questions regarding the assignment, don't hesitate to post on the Bulletin Board: that's what it is there for.
Here are some files you will need:
Sections in this document:
Before you begin, you need to tell DrJava where to find the hw1.jar
file. Under Edit -> Preferences, click the Add button under Resource Locations -> Extra Classpath
and type the full path of the jar file.
We will put problems with DrJava and their solutions on a separate page as we encounter them. Check there first if you have a problem.
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, use Tools -> History -> Load Interactions History as Script. The output below shows each interaction (marked with a >) followed by the result from that interaction.
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) > game.printBoard() // Show current state of board (Mine has been triggered) 00001@101@ // The complete board is displayed. 0111111011 01@1011100 // The mine we triggered is at (2,2) 011101@100 2210011100 @@21111000 23@11@2100 011112@100 0111011100 01@1000000
You should think of each cell as being in one of three different states:
Note that these three states are mutually exclusive - for example, if a cell is "marked" then it is neither explored nor unexplored.
Now that you have a basic understanding of the Minesweeper class's
functionality, use the javadocs
to explore the different methods that we have provided. After looking
at the javadocs you should be ready to think about how to write a
solver. As shown below, there is a very simple solution that makes
exclusive use of the hint method; we'll use it as a
starting point. You should copy this code and save it in a file called
Solver.java. (Alternatively, you can
simply download the template Solver.java.)
class Solver {
public Minesweeper game;
public Solver () {
game = new Minesweeper(10,10,10);
}
public int solve() {
while (!game.isSolved()) {
game.hint();
}
return game.getNumHints();
}
}
Welcome to DrJava. > Solver s = new Solver(); > s.solve() 90
Of course, this "solution" consists entirely of cheating! Let's try to find a way to minimize the number of hints we are required to use.
The idea is to make as much progress as possible using logical
deduction, and to only ask for a hint when we get
stuck. Consequently, the supplied Solver.java actually looks
like this:
class Solver {
public Minesweeper game;
public Solver () {
game = new Minesweeper(10,10,10);
}
public int solve() {
while (!game.isSolved()) {
game.hint();
makeAllDeductions();
}
return game.getNumHints();
}
/** Make as much progress as possible towards solving
* the board, until we win or get stuck.
*/
public void makeAllDeductions() {
}
}
(If you are creating your own copy of Solver.java from scratch,
you should modify it to look like this as well.)
makeAllDeductions() doesn't actually make any
deductions yet! Later in the assignment you will be able to remedy
this. We'll begin by building some of the tools needed to be able to
reason about cells in the board and whether or not they contain bombs.
Solver.java)
/** Determine the number of neighbors of cell (r,c) that have been
* marked as bombs. */
public int markedNeighbors(int r, int c) {
int marked = 0;
for (int i = Math.max(r-1, 0); i <= Math.min(r+1,game.getHeight()-1); i++) {
for (int j = Math.max(c-1,0); j <= Math.min(c+1,game.getWidth()-1); j++) {
if (!(i==r && j==c)) {
if (game.isMarked(i,j)) {
marked++;
}
}
}
}
return marked;
}markedNeighbors iterates through the indices adjacent to
the given location, being careful to stay within the boundaries of the
board and to skip counting the center location itself, and counts the
number of marked cells encountered. markedNeighbors has
been provided for you
in Solver.java, or you
can copy and paste it into your own Solver.java.
For the first part of the assignment, your job is to write a method
similar to markedNeighbors that determines how many of
the neighboring cells have not been explored.
Your method should look like:
/** Return the number of neighbors of cell (r,c) that have not yet been explored. */
public int unexploredNeighbors(int r, int c) {
...
}unexploredNeighbors should be very
similar to the implementation of markedNeighbors: only
the innermost counting logic needs to be changed. Remember, the
number of unexplored neighbors does NOT include marked cells.
> Solver s = new Solver() > s.unexploredNeighbors(1,1) 8 > s.unexploredNeighbors(0,0) 3 > s.game.explore(1,2) > s.unexploredNeighbors(1,1) 7
Solver.java)Once we can count the number of marked neighbors, we can make
deductions about them and explore the rest of the board. There are
two kinds of deductions we can make: we can conclude that some
cells are safe to explore, or we can conclude that some cells
certainly contain bombs.
First, if a cell has the same number of marked neighbors and
neighboring 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 are not
marked as bombs. 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 r, int c) {
boolean changed = false;
if (game.isExplored(r, c)) {
// # of marked neighbors is equal to # of neighbors containing bombs
if (markedNeighbors(r,c) == game.getNeighboringBombs(r,c)) {
for (int i = Math.max(r-1, 0); i <= Math.min(r+1, game.getHeight()-1); i++) {
for (int j = Math.max(c-1,0); j <= Math.min(c+1, game.getWidth()-1); j++) {
if (!(i==r && j==c)) {
if (!game.isMarked(i,j) && !game.isExplored(i,j)) {
changed = true;
game.explore(i,j);
}
}
}
}
}
}
return changed;
}
exploreNeighbors has been provided for you
in Solver.java, or you
can copy and paste it into your own.
Second, 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 nearby bombs is equal to the sum of the number of unexplored neighbors and the number of marked neighbors.
For the second part of the assignment, write and test this method,
in the same Solver.java file:
/** The neighbors of a cell can *all* be marked as bombs if
* the cell has been explored and the number of nearby bombs is equal to the
* sum of the number of unexplored neighbors and the number of marked
* neighbors.
*
* @return whether any neighbors were marked as bombs.
*/
boolean markNeighborsAsBombs(int r, int c) {
...
}
> 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........ **........ .......... .......... .......... ..........
Solver.java)We now have the pieces to make a complete solver.
The first step is to use exploreNeighbors
and markNeighbors on all of the explored cells. 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() {
...
}makeAllDeductions()
method which is called from solve(): it should repeatedly
check the board for updates until no more updates can be made.
> 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
Solver.java) The behavior of explore in the Minesweeper game that
we have supplied is different from the standard one. To make things
simple, explore just looks at a single cell. However,
when there are no neighboring bombs, we know that all of the
neighboring cells are safe for exploration. If those cells in turn also have no neighboring bombs, then all of those cells' neighbors are also safe for exploration, etc. A smarter approach is to
continue exploring outward as long as we encounter cells with no
neighboring bombs.
Welcome to DrJava. > Solver s = new Solver() > s.deepExplore(4,4) > s.game.printBoard() .......... ...111.... ...101.... ..1101.... ..1001.... ..2111.... .......... .......... .......... .......... >Your task is to implement a
deepExplore method for
the Solver class.
public void deepExplore (int r, int c) {
...
}
This problem requires more thought than the previous problems - don't be alarmed if you can't think of how to do it immediately.
There is a suite of tests available to you from any of the SEAS
Linux-based computers on campus. To take advantage of them, you must
get your code onto a SEAS computer (for example,
eniac.seas.upenn.edu), then log on yourself and run the
test script.
The first step is to get your code onto the space you are given on the SEAS computers. (If you are developing your code in one of the computer labs on-campus, this step is not needed; open up a terminal and skip to the next step.) Otherwise, you should follow the instructions (found under "Resources" on the main CIS120 web page) for transferring files to eniac and logging in to eniac remotely. Under KDE, the terminals can be found under Applications -> System -> Terminal in the chameleon menu.
Now that the code is on a SEAS computer, you can run the tests.
Navigate to the directory that has Solver.class and run
~cis120/pub/bin/test01. For example, my username is
wagnerdm and I built my solution in
~/classes/120/minesweeper, so my session would look
something like this:
wagnerdm@plus:~> cd classes/120/minesweeper wagnerdm@plus:~> ~cis120/pub/bin/test01 CIS120 Homework 01 Test Results for null: ----------------------------------- Question 1: Cell Neighbors ---------------------------------- Test - Sample Interactions: Passed - 4.0 points Test - Checking unexplored neighbors: Passed - 5.0 points (etc.)If you want to see more details about any tests that fail, take a look at
Tester.java, which
defines the actual tests that are run. You don't need to
understand Tester.java at all. Just search for the name
of the test that failed and see what it does.
For example, suppose that the test script reports that the test
"Unexplored neighbors: Corner II" has failed. Searching
through Tester.java for this test, we find this:
q1.addTest("Unexplored neighbors: Corner II", 5, new Tester("q1_test5"));
This means we must look for the test called q1_test5.
Searching again, we find:
public void q1_test5() {
Solver s = new Solver();
s.game.reset();
s.game.explore (9, 1);
assertEquals (error("unexploredNeighbors"), 2, s.unexploredNeighbors (9, 0));
}
This test creates a new solver, resets the board, and explores the
cell at (9,1). The last line is the most important: it asserts that
after performing these operations, the result
of s.unexploredNeighbors(9,0) ought to be 2,
and if it isn't, some error message
about "unexploredNeighbors" ought to be shown. So in this
case, you need to figure out why unexploredNeighbors is
giving the wrong result after creating a Solver and
exploring (9,1).