Introduction to Data Structures and Algorithms
Assignment 3 Part B: Recursion

  • Due 24 May , 7pm

What To Hand In

  • Part A
    • and (for the completion)
  • Part B

Do not rename these files.

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)

Minesweeper is a 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).

The Minesweeper class has code for most of the program, except for the key methods of
  • 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).

The Square 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 Minesweeper in order to make the game work.


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.