Description
Introduction
In this program you will get a chance to use recursion to solve a problem that could not be done just as easily
or more efficiently with a loop. It is possible to solve this problem without recursion, but it would somewhat
more complicated, and would result in the same big-O space and time requirements as a recursive solution.
Depth-first search (DFS) is an algorithm for searching in non-linear data structures. There are a few different
ways to implement DFS, but here you’re going to implement a recursive DFS as part of a Minesweeper
game. We’ll discuss more about how to do this recursive search later.
The code for this assignment uses a few features of Java we haven’t used in this course before. They are: 2D
arrays and inner classes (we already wrote the inner class code for you). Two-dimensional arrays were
covered in section 7.6 of the textbook. Inner classes are covered in section 10.5, and their use for Listeners
(part of the Java GUI system) is covered in section 10.7.2. Event handling in general is covered in Section
10.7, but we wrote all the event-handling code for you.
Because this program has a GUI, the Vocareum environment is configured so you can open up a Linux
desktop, like we had for pa1, so you can test the complete program
The assignment files
Note: the blurbs below do not completely describe what each of these classes are, or how they fit together.
For more details on that, see the section on the class design.
The starter files we are providing for you on Vocareum are listed here. The files in bold below are ones you
create and/or modify and submit. The files are:
VisibleField.java Data representing what’s visible about the minefield and other data and methods
for the game. The interface has been specified for you; you need to complete the implementation of
this class.
MineField.java The hidden minefield. The interface has been specified for you; you need to
complete the implementation of this class.
MineSweeper.java The main program. We have written this class for you. Do not change it.
MineSweeperFixed.java A version of the program that uses a hard-coded mine field instead of
randomly placed mines. (For testing purposes.) You may modify this file (e.g., to add more test mine
field configurations) or not; we won’t be grading it.
GameBoardPanel.java The GUI for the game. We have written this class for you. Do not change it.
images/facesmile.gif Image used by the program.
images/facedead.gif Image used by the program.
MineFieldTester.java and VisibleFieldTester.java Test programs you may create to test your
two classes. You are not required to submit these files. These are described further in the section on
n.ExTfq
Development Hints.
README See section on Summary of requirements for what to put in it. Before you start the assignment
please read the following statement which you will be “signing” in the README:
“I certify that the work submitted for this assignment does not violate USC’s student
conduct code. In particular, the work is my own, not a collaboration, and does not involve
code created by other people, with the exception of the resources explicitly mentioned in
the CS 455 Course Syllabus. And I did not share my solution or parts of it with other
students in the course.”
The assignment
Write the main logic of a program to play the game Minesweeper. To keep the scope of this assignment
reasonable, we have created the object-oriented design for this program, and have implemented the GUI for
you.
Minesweeper is a game where mines are hidden in various random locations in a two-dimensional minefield.
The player has to figure out where all the mines are without exploding a mine. They do this by repeatedly
uncovering locations, and guessing mine locations, until they uncover all of the non-mine locations (win) or
they explode a mine (lose). This is more than a game of chance, because when a non-mine square is
uncovered it displays the number of mines adjacent to that square. You can use that information to figure out
where the mines are (or at least narrow down their locations).
The rest of this section describes the game in somewhat gory detail. You do not need to know all of the
details (e.g., of exactly how the display changes) to actually play the game yourself. And the first part of
your homework is to go out and play several games of minesweeper to get an idea of how it works. If you
have never played before, you probably want to start out with beginner mode (9 x 9 field, 10 mines). There
are many versions of this game. It’s been on Windows forever, and probably is still. Here is a free web-based
version. There are also a few free smart-phone minesweeper apps. Just don’t get hooked, like I did, or you’ll
never get to your assignment!
Note: The user interface for our implementation is a little more simplistic than in the real game. For example
for our game the player can’t change the size of the minefield or number of mines for a game. (You would
have to change the program itself to do that.)
Uncovering a square. The player uncovers a square with a left-click on a button at that location. If it’s nonmine location, what shows up at that square is the number of adjacent hidden mines (a number 1 – 8 because
diagonals are considered adjacent). If there are no mines adjacent to this square, it displays no number. If the
player uncovers a mine instead, it explodes, and they lose the game.
ZDarray
A game after player opens the first square. It’s showing that two of the squares surrounding that square have mines in
them. Our game has a 9 x 9 field, with 10 mines.
Automatic opening of empty regions. To make it less tedious for the user, when they open a square that has
no adjacent mines, the game automatically opens all the squares in that region that aren’t adjacent to mines
until it gets to the boundary of the field, or squares that are adjacent to other mines. Here is an example that
illustrates the effect:
The player only clicked once, at the location: 2nd row, 7th column. It wasn’t adjacent to any mines, so the program
automatically opened the rest of the squares shown.
(This automatic opening of parts of the field is where your recursive search is going to come into play.)
Guessing a mine location. Based on the opened squares, if the player can then deduce the location of a
mine, they can mark that unopened location as a mine-guess (right-click), to help them figure out where
more mines are and are not. (In our interface, the mine guess is denoted by a yellow square.)
Marking what may be a mine location. Usually a player would guess a mine location only when they
could actually deduce that a mine goes there. However, there is a third state a covered mine location can
have, and that’s to just mark it with a question mark, to show that it’s something they are thinking might be a
mine, but aren’t sure about. Marking a location this way does not affect the number of mine guesses.
If a mine is covered, one right click puts it as a mine guess (yellow), and another right click puts it as a
question (shows ?, not yellow), and a third right click puts it back to the regular covered state.
m
S covered
uncovered Location I marked
nightdick mineguess
questionmark
regular
coveredstate
This player has made a few guesses (yellow) and marked a few spots they are unsure of with a question mark. The
large empty area (shown as pushed in buttons), was automatically opened by the program when the player earlier
clicked on just one of those empty spots. The top left shows the number of mines left to guess.
Number of mines left display. When the game starts the number of mines still to be guessed is displayed at
the upper left of the window, so the user knows how close they are to finishing. Guessing a mine (i.e.,
marking that location, as described above), will reduce that number by one whether the guess was correct or
not. Although a user can guess more mines than there actually are, the display only goes down to zero (no
negative number displayed). Note: some versions of the game out there let the displayed number go to
negative, but our version will not.
The user can win without it reaching zero, because the win-condition is to open all the non-mine locations,
not to guess any particular number of mines. The next diagram illustrates this situation.
Winning game display. When a player successfully opens all of the non-mine locations, the field display
changes to show where the other mines are (it shows them as guesses, in yellow). I.e., these would be any
unopened squares that weren’t already yellow. The top middle of the window will show the happy face, and a
message about winning will appear on the upper right of the window.
O numMines
This player just won the game (indicated by “You won!” message at upper right) . The number of guesses made was 7
(upper left display shows 10 – 7 = 3), but once they opened all the 71 (9*9 – 10) non-mine squares they won. It shows
10 yellow squares, because on a win, all of the squares with mines are shown as guesses.
Losing game display. When a player opens a mine location, that mine explodes, and they lose the game.
The exploded mine is shown by a red square. Any previously made incorrect guesses are shown with an X
though them, the correctly guessed mine locations are still shown as guesses (yellow), and the other
unopened mines are shown as “mines” (a black square, in our implementation). The top middle of the
window will show the sad face, and a message about losing will appear on the upper right of the window.
mine squares yellow red black
non mine
squares
b
yellow yellowwith X
numbers blank
if opened
This player just lost the game at the very end. They guessed 9 squares correctly, the last one incorrectly, and then
opened the last unopened square, which was a mine. The red one is the mine they clicked on, the X is the incorrect
guess.
Another game just lost. The black squares are mines that the player hadn’t yet guessed at the point that they lost. The
X’s are incorrect guesses. The’s 3 other yellow ones were the correct guesses. The red square is the exploded mine.
Playing the game again. The user can play another game by clicking on the happy/sad face. It goes back to
a happy face at the start of the new game, the game board shows all squares as unopened, and shows the
original number of mines in the display of how many left to guess (top left).
Initial mine placement. On each game played, the mine locations are chosen at random, thus will be
different for each game. The game works such that the first square opened is guaranteed not be a mine. To
get that behavior the program can’t choose the mine locations until the user opens the first square.
Clicking on an already-opened square. In our game clicking on a square that has already been opened will
do nothing — this is different than other versions of the game you will play. (In other versions of the game
clicking on an open square that has a number on it is a shortcut for opening all the neighboring non-guessed
squares.)
We are giving you the overall design to use, as well a lot of the code, so you should read on before you dive
into this problem.
The Class Design
We have done the class design for you. Normally in a GUI program it’s desirable to separate the part of the
program that does the computation and stores data from the part of the program dealing with the display and
input. This organization is called the Model-View-Controller design pattern. This way it’s easier to change
the look and feel of the program without having to touch the code that does the computation: e.g., we could
use our MineField and VisibleField classes, below, unchanged, with a non-graphical, console-based
interface. The design given here has that separation. The part you are implementing, MineField and
VisibleField, comprises the Model. (PA1 also had such a design: the computation happened in
CoinTossSimulator, and display of the computation was in CoinSimComponent and the Bar class used by
CoinSimComponent.
The simple UML (Unified Modeling Language) class diagram below shows these relationships between the
classes in our design. An arrow from class A to class B means that class A depends on class B (or put other
ways, “has to know about”, or “uses”). To keep it simpler, we showed the inner classes as contained inside
their enclosing class. The classes in green are the ones you are implementing for the assignment.
Here is an overview of this design, stating which classes are responsible for which part of the program, and
what the dependencies are between the various classes:
GameBoardPanel This JPanel subclass contains all the display elements and listeners in the program.
It has a two-dimensional array of SquareView objects for all of the buttons on the minefield board.
During the normal mode of operation, it creates the MineField and VisibleField objects. (So it
depends on those other two classes.) This class has already been completed for you.
This is the GUI for the program: it contains the display and controls for a game, and the minefield
display (grid of “buttons”). It’s the View and Controller in the MVC design pattern, whereas the Model
consists of the the VisibleField and MineField. You do not need to understand every line of code in
GameBoardPanel to complete this assignment; a lot of it is minutiae of setting up and updating Java
Swing components. However, it will be helpful if you know when and why the various methods you
are implementing get called from methods in this class and its inner classes. So here’s more about its
design. It has two named inner classes:
SquareView. The view class for a single square. There is one of these objects for each square on
the board. Although it looks like a button, this is actually a JLabel, because it’s easier to use a
JLabel to respond to both left and right clicks. It also uses your VisibleField accessors to find
out the state of the square it’s displaying. We wrote this class for you.
SquareListener. The controller class for a single square. There is one for each square on the
board. Its one public method, mouseClicked, detects if it was a left or right click, and dispatches
it to its private method openSquare (left click), or changeGuessStatus (right click). This class
depends on the SquareView, GameBoardPanel, MineField, and the VisibleField. We wrote
this class for you. Listeners are described in a little more detail below.
While there is a view and controller for each individual square, the design has no separate “Square”
class to model a square. The state of all of the squares is in the VisibleBoard class. The view and
controller for a square know their own location; they call VisibleBoard methods, passing in their
location to specify their square.
The listener for the other button on the board (the smiley face, to start a new game) is an anonymous
inner class. That means it doesn’t have a name, because it’s just used in one place. It’s in the
setupTopPanel method of the GameBoardPanel class.
MineSweeper class. This class has main. It sets up the frame and GameBoardPanel. It depends on the
GameBoardPanel.
MineField class. Has locations of the mines for a game. This is the “hidden” part of the minefield.
This class is mutable, because we sometimes need to change it once it’s created. Its mutators are:
populateMineField. Once the user clicks once, this is called to place the random mines,
preventing a mine from going into the clicked location.
resetEmpty. Put the minefield into its starting state (before that first click).
This class does no I/O. Doesn’t depend on any other classes.
VisibleField class. This is the data that’s being displayed at any one point in the game (i.e., visible
field, because it’s what the user can see about the minefield). It does no drawing on the screen itself.
Client can call getStatus(row, col) for any square to find out the current display status. It actually
has data about the whole current state of the game, including the underlying mine field
(getMineField()). Other accessors related to game status: numMinesLeft(), isGameOver(). It also
has mutators related to moves the player could do (resetGameDisplay(), cycleGuess(), uncover()),
and changes the game state accordingly.
It, along with the MineField (accessible in mineField instance variable), forms the Model for the
game application, whereas GameBoardPanel is the View and Controller, in the MVC design pattern.
That MineField can be accessed (or modified) from outside this class via the getMineField accessor.
This class does no I/O. Depends on the MineField class.
What’s a listener?A listener is a GUI component that has a function that gets called whenever a certain user
action happens (e.g., a mouse click or a key pressed). It’s usually associated with a particular component:
e.g., the component might be a button, and the listener has the code that gets executed when that button is
pressed). The application programmer fills in the body of this function for a subclass of the appropriate Java
listener class.
A sample use-case of MineSweeper
Let’s go through what happens with the classes for a particular action. The following is another type of UML
diagram called a sequence diagram that shows the message-passing (aka, method calls) between objects to
carry out a particular action. You read the diagram from top to bottom. The use-case being described in this
sequence diagram is that the user left-clicks a minefield square for the first time in a game. The last thing
that happens in this sequence is the window being updated, with the call to repaint).
Use case: user opens the first square.
We can relate this specific diagram to the general idea of communication between classes in the MVC
pattern:
The blue steps shows the Controller updating the Model
The red steps shows the Controller telling the View that the Model changed.
The green steps show the View asking the Model for its updated state.
And the parts in the black boxes on the right side of the diagram are annotations describing what happens in
the Model (i.e., the part you are implementing).
Algorithm hints
There are two parts of solving this problem that may be challenging. We’ll give you some hints on how to
solve those part here.
Choosing the initial mine locations
You can use a straightforward technique to choose random mine locations. That is, choose a random
location, and if that location already has a mine on it, keep choosing another random location until you get a
location that doesn’t have a mine on it. Because of a precondition on the 3-parameter MineField constructor,
that the number of mines has to be less than one-third of the total number of possible mine locations, there is
a very low probability that choosing locations this way will result in very many false tries.
Recursively finding an open area
You are required to use recursion in your solution to the problem of finding an open area with no mines in it.
As mentioned earlier, you will be using a variation on depth-first search to do this. More specifically, you
will be using the flood-fill algorithm, which is used in graphics for completely filling in an enclosed area
with a particular color, pixel-by-pixel (which itself is a specialization of the algorithm for finding a
connected component in a graph). The pseudocode for flood-fill in this Wikipedia article should give you a
good start for figuring out how to solve this problem applied to minesweeper. The parts of the article you
will need are from the start of the section “The Algorithm” through “Stack-based recursive implementation”
(the “stack” mentioned is not explicitly created, but is the underlying call stack used in all recursion). The
algorithm presented there assumes 4-way connectivity, while, of course, here we have 8-way connectivity.
Development Hints
You are encouraged to write private helper methods to make your code clearer. (That’s true for any program
for this course.) In particular here, the recursive search part of your code will almost certainly be a private
helper function.
Here is a possible plan for how you might develop your code:
1. Get the 1-arg constructor and all accessors for the MineField class working before you write or test
the other methods. You may also, optionally, add a toString method to help you see that your fields
got initialized properly (the only change to the MineField interface that we will accept). Your tests
should be in a MineFieldTester class you create, that creates several MineField objects whose data
come from hard-coded arrays, and calls the accessors on them to figure out whether they were created
correctly.
2. You could then proceed to implement a subset of your VisibleField class, so you can test it on minefields with known mine locations using a VisibleFieldTester you create, and in a more limited way
(but easier to see results) with MineSweeperFixed, a main program we provided for you that uses a
hard-coded minefield. You can also modify MineSweeperFixed to use different fixed minefields of
your own creation).
The subset you could create is to make a game that doesn’t automatically open the empty areas
(doesn’t implement the recursive search part), but requires the user to open each square manually.
3. Once you are sure this version of VisibleField works you could add the recursive search feature to
it, and retest with a modified VisibleFieldTester and with MineSweeperFixed.
4. Now you can add the MineField functionality for random mine placement, and retest on a modified
VisibleFieldTester and with MineSweeper.
Summary of requirements
As on the previous assignment, there are several requirements for this assignment related to design, testing,
and development process strewn throughout this document. We’ll summarize those and the functional
requirements here:
implement MineField and VisibleBoard classes according their public interfaces. This includes not
adding any new public methods (besides toString), or adding/changing/removing any public named
constants. You are welcome to add any necessary private named constants or private helper functions.
MineField and VisibleBoard must work correctly with the rest of the given minesweeper code.
use recursion to implement the automatic opening of empty squares.
festers
Mr
your code will also be evaluated on style, documentation, and design. We will deduct points for
programs that do not follow all of the published style guidelines for this course (they are also linked
from the Assignments page).
add necessary information to the README file. A reminder of what goes in it: This is the place to
document known bugs in your program. That means you should describe thoroughly any test cases
that fail for the the program you are submitting. (You do not need to include a history of the bugs you
already fixed.) You also use the README to give the grader any other special information, such as if
there is some special way to compile or run your program. You will also be signing the certification
shown near the top of this document.
A note about grading of this assignment
Because the code you are writing has no I/O, much of the grading of the assignment will involve autograding that submits your MineField and VisibleMineField classes to our own unit-tests. So you will need
to spend some effort unit-testing these classes yourself: making sure that they work to specification, not only
that they happen to work with the given MineSweeper program.
Furthermore, to be able to compare your results to predictable expected results, many of our tests will use
the non-random version of your code (i.e., using the 1-parameter MineField constructor, the one that takes a
2D array). If this constructor doesn’t work for your program, you will lose a significant amount of credit on
this assignment, because these tests will fail.
Similar to other unit-tests we have discussed in this class, the structure of many of these test cases we will
subject your code to are:
call a mutator (or constructor)
test that the object is in the correct state from that mutator by:
calling all of the accessors, testing that actual results match the expected results
If you have not done such tests yourself, you might not be sure that the code works correctly. This is a more
thorough and systematic test than just running the game a few times on arbitrary input.
For more about developing your program, see the Development Hints section.
Submitting your program
You will be submitting completed versions of MineField.java, VisibleField.java, and README. Make
sure your name and loginid appear at the start of each file. Reminder: if you developed your code locally on
your laptop, before submitting you will need to upload your code to Vocareum, and compile and re-test it
using the Linux Desktop on Vocareum before submitting it.
Please try submitting the first time at least a day before the final submission deadline so you have time to fix
your program based on any failed tests.
When click the “Submit” button in your PA3 Vocareum work area, it will check that you have the correct
files in your work area and whether they compile. In addition, it will test whether your MineField has a
correct 1-arg constructor and whether the accessors return correct values for a MineField created with that
constructor. Please remember to check the submission report.
Passing these submit checks is not necessary or sufficient to submit your code (the graders will get a copy of
what you submitted either way). (It would be necessary but not sufficient for getting full credit.) However, if
your final submitted version does not pass all the tests we would expect that you would add some
explanation of that in your README and resubmit with the updated README. One situation where it
might fail would be if you only completed a subset of the assignment (and your README would document
what subset you completed.)
You are allowed to submit as many times as you like, but we will only grade the last one submitted. If you
are unsure of whether you submitted the right version, there’s a way to view the contents of your last submit
in Vocareum after the fact: see the item in the file list on the left called “Latest Submission”.
26 217 Arrays 7336
1015 Inner classes 1487
