Introduction to Data Structures and Algorithms
Assignment 3 Part B: Recursion
Resources and links
What To Hand In
Do not rename these files.
- Part A
Department.java (for the completion)
- Part B
Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.
Minesweeper Game (Weight: 1/3)
very old video game in which the player tries to work out where the mines are
hidden on a grid. Each square in the grid starts off as hidden (dark green). The
player can mark any hidden square that they think contains a mine, and can expose
any hidden square that they think is safe.
- If the player exposes a square with a mine, they lose and the game is over. In this case, all the squares are opened up so that the player can see where all the mines are.
- If the player exposes a safe square that is next to one or more mines, then the square displays a number saying how many of the eight surrounding squares contain a mine.
- If the player exposes a safe square that is not next to a mine, then it "spreads" to all the connected squares that are also safe, and exposes them also.
If you aren't familiar with the game, you can run the demo, or play the KDE
version (KMines - in the Games menu, under Tactics and Strategy).
class has code for most of the program, except for the key
mark(row, col): The player has clicked on a square to mark it.
tryExpose(row, col): the player has clicked on a square to expose it
exposeSquareAt(row, col): expose the square at (row,col) and if it has no adjacent mines, spread the exposing to all connected safe squares. This method should be recursive, and needs to spread out horizontally, vertically, and diagonally.
hasWon(): check whether the player has won the game yet (exposed all the squares without a mine).
class has code for individual squares; you need to use it, but you
should not modify it.
Core and Completion:
Complete the four incomplete methods in
in order to make the
A good way to destroy the fun in a game is to make an AI helper that does
all the hard work for you, although constructing such an AI helper can be a
fun challenge in itself. Of course, an AI helper that is allowed to cheat
by looking inside the game is trivial - it should only be able to see what
the player can see.
Write a non-cheating method that can do what a good player would:
- It should be passed an 2D array of integers representing the visible state of the Minesweeper board. It should have -1 for all the hidden squares, 0 for all the empty exposed squares, and 1 - 8 for exposed squares that have adjacent mines.
- It should then work out which of the hidden squares are safe to expose and which of the hidden squares should be marked.
To test your AI helper, you will need to extend the MineSweeper code to
generate the grid of numbers for the visible state, and then draw the
recommended actions on the board.