For this week's lab, you will be working with several applications of recursion. In the first exercise, you will add recursion to a nearly complete version of the well-known MineSweeper game. In the second exercise, you'll be working with permutations and derangements, which refer to ways of arranging a list of items into different orders. There is also an opportunity for extra credit if you can implement another application of recursion in the MineSweeper game.
You can start the lab by creating a new project in your Eclipse workspace. Copy the folders mines and orderings from the directory /classes/f07/cs225/files_for_lab4 into the Eclipse project.
Your competed project is due at the beginning of lab next Tuesday. You should add the project to your CVS repository by then. The number of lines of code that you have to write for this lab is not large, but it will probably take you some time to figure out recursion and get the programs working. As usual, I will be available in my office or in the Math/CS computer lab on Monday from 7:00 to 9:00 PM. I also plan to be on campus on Thursday from about 10:00 until 3:00.
Note that for this lab, the classes that you be working with are defined in packages. The classes for the MineSweeper game are in a package named mines. This means that each class is defined in a file that begins with the declaration "package mines;", and the file is stored in a folder named mines. Similarly, the class for the second exercise is in a package named "orderings". Since "use of the default package is discouraged," I want you to start getting used to packages. Fortunately, in Eclipse, it hardly makes a difference whether you use the default package or a named package. If you wanted to compile or run the programs from the command line, it's a little more complicated: See the very last paragraph of Subsection 2.6.4 in the textbook.
In the usual (Microsoft) MineSweeper game, you click on squares that might or might not contain mines (only one mine per square). You know the total number of mines, but not which square they are in. If you click on a mine, you get blown up. If you click on a square that is free of mines, you are told how many mines there are in neighboring squares. This number is shown inside the square, and if there are no mines in any of the neighboring square then the square is just left blank. Neighbors here are the vertically, horizontally, and diagonally neighboring squares, so a square can have up to eight neighbors. The color of the square changes when you visit it, so you can tell which squares have been visited. You win the game by visiting all the squares that don't contain mines, without visiting any mined square. To help you keep track of where the mines are, you can mark a square with a "flag" to show that you think it contains a mine. Clicks on a flagged square are ignored, so you can't accidentally blow yourself up by clicking one inadvertently. You can flag a square by right-clicking or shift-clicking it; you can remove a flag by right-clicking or shift-clicking it a second time.
I once had an old Macintosh version of MineSweeper that works a little differently. In this version, you start at the upper left square of the minefield and have to make your way home, which is the lower right square, without getting blown up along the way. You can only visit a square that is next to one that you have already visited. ("Next to" here means above, below, to the left, or to the right; you can't move diagonally.) You win as soon as you safely reach the lower right square; you don't have to uncover every unmined square. The lower right square is guaranteed to be free of mines. Also, to get you started, the upper left square and its neighbors are also free of mines. I prefer this version of the game, and it's the version that you will work on for this lab.
The mines package already defines a working version of MineSweeper, but it is unsatisfactory in one respect: If you visit a square and the number of bombs in neighboring squares is zero, then you know automatically that its safe to click on every neighbor of that square. Since it can be done automatically, without thought, it would be nice if the computer would just do it. Furthermore, if one of the neighboring squares also has no mined neighbors, then you can automatically visit all the neighbors of that square. And so on.... This is a recursive procedure, and your job is to add a recursive method to the program to implement it. A completed, compiled version of the program can be found in the jar file MineSweeperComplete.jar in the directory /classes/f07/cs225/files_for_lab4, so you can see how much nicer the game is after the recursion is added.
Note that when you play the game, you start with a visited square in the upper left, and you have to work from there. Flagged squares, which you make by shift-clicking or right-clicking, are shown in pink with a "B" to indicate that you think there's a bomb there. If you step on a bomb, you lose the game, and the locations of all the bombs are shown in red.
The main method for MineSweeper is in the file MineSweeper.java, and you should run that file to see how it works. The game is actually implemented in the file MineField.java, and that is where you will be working. (The other file, MineMenus.java, implements the menu bar for the program, and you can ignore it.)
For this exercise, you only need to modify the method mark(row,col), which is defined at the very bottom of MineField.java. This method is called from elsewhere in the program when the user clicks on a square; when the method is called, it has already been checked that the user is allowed to click there and that there is no mine in that square. Currently, the mark method contains the single line "state[row][col] = STATE_VISITED;" which is meant to record the fact that the user has visited the square in the specified row and column. You have to modify mark() so that in addition to marking just the one square where the user clicked, it will also recursively mark neighboring square as visited if it is known that they don't contain any mines.
The MineField class uses the two-dimensional array named state to keep track of the state of each square on the board. The value of state[r][c] is the state of the square in row r and column c. The possible values are: STATE_FLAGGED, meaning that the user has flagged the square as probably containing a bomb; STATE_VISITED, meaning that the square has been visited and the user can see how many mines are in neighboring squares; and STATE_UNVISITED, which is the initial state and means that the square has not yet been visited or flagged.
There is also a two-dimensional boolean array named mined that records the positions of the mines. The value of mined[r][c] is true if there is a mine in the square in row r and column c. Note that a method bombCount(row,col) is already defined for counting the number of bombs in the neighbors of a given square, so you won't have to do this counting yourself. Remember that the basic idea is that if you visit a square at (row,col) and if bombCount(row,col) is zero, then you should also automatically visit all the neighbors of that square.
The recursive mark() method will be similar to the "blob-counting" method that we covered in class and that can also be found in Subsection 9.1.4 in the textbook. It will be rather short -- I did it in fifteen lines -- but it's tricky to get everything right. Remember that you need base cases and that you have to avoid infinite recursion.
The MineSweeper game creates a random board with a specified number of mines. At least two things can go wrong: First, it is possible that the game is already solved when it is first created. This can only happen after the recursive mark() method is implemented; once that's done, calling mark(0,0) to start the game might cause a chain of squares all the way home to be marked. Second, it's possible that there is no solution at all, that is all possible paths from the starting square to the home square are blocked by mines. The fist problem is more likely to occur when the number of mines is small, and the second is more likely to occur when the number is large.
When a game is started and the program creates a random board, it calls the method configOK() to check whether the randomly generated board is OK to use for a game. You can find configOK() just above mark() in the file MineField.java. Currently, this method only checks for the first problem. That is, it checks whether state[ROWS-1][COLS-1] == STATE_VISITED before the game has even started.
For extra credit, you should make it possible for configOK() to check for the second possible problem as well. That is, you should check whether there is a path of legal moves from the upper left square to the lower right square. This will require a recursive method. It will be similar to a maze-solving algorithm that we will look at in class.
(MineSweeperComplete checks for both problems, so any game that it generates is solvable but not solved to begin with. It might be a good idea to add one more test that is not implemented in my program: Avoid games that are "almost" already solved to begin with, by making sure that the number of initially visited square is not too big. Or maybe by making sure that no square that is less than a certain distance from the goal square is initially visited. You might want to add such a test. Note that it would not use recursion.)
For the second exercise of the lab, you will write recursive methods that generate permutations and derangements of the integers (0,1,...,N-1).
A permutation of these numbers is simply an arrangement of the numbers into some order. (We also count the original order as a permutation, called the "identity permutation.") The number of different permutations of N integers is factorial(N): There are N choices for the first number, then (N-1) for the second, then (N-2) for the third, and so on, so the total number of possibilities is (N)(N-1)(N-2)...(3)(2)(1), which is factorial(N).
A derangement of the numbers is simply a permutation in which no number occupies its original position. That is, 0 can't be in position 0, 1 can't be in position 1, and so on. There is a nice mathematical theory of derangements, which says that the number of derangements is about (1/e) times the number of permutations, where e is the base of the natural logarithms, e = 2.7182818.... The approximation gets better as N increases, but it's very good even for small values of N. To put it another way, if you divide the number of permutations of N items by the number of derangements of N items, the result is about equal to e.
Sometimes, it's useful to be able to generate all the permutations or derangements of a set. This can be done easily using a recursive algorithm. The program AllOrders.java, in package orderings, defines a closely related recursive method. The method sequences() in that class generates all sequence of length N made up of numbers selected from (0,1,...,N-1), with repetition allowed. The number of such sequences is N raised to the power N, which is much larger than factorial(N). (In the program, the value of N is given by a constant named ITEMS.) Here is the method; the comments explain what it does:
/**
* This recursive method generates sequences of integers selected from
* the range 0 to ITEMS-1. Whenever it finishes a complete sequence of length
* ITEMS, it increments the global variable sequenceCount, and, if PRINT
* is true, it outputs the sequence to standard output.
* @param listSoFar an array of length ITEMS that contains part of
* a sequence, or possibly a completed sequence, when this method is
* called. If the sequence is complete, it is simply counted and printed.
* Otherwise, this method adds each possible item onto listSoFar, calling
* itself recursively to complete the sequence.
* @param itemsInList The number of items in the sequence. This tells how many
* places in the array listSoFar have already been filled before the method is called.
*/
private static void sequences(int[] listSoFar, int itemsInList) {
if (itemsInList == listSoFar.length) { // The sequence is complete.
if (PRINT)
printList(listSoFar);
sequenceCount++;
}
else { // Add a new item to the list in all possible ways
for (int i = 0; i < ITEMS; i++) {
listSoFar[itemsInList] = i; // Add i onto the current sequence.
itemsInList++; // Since the length of the sequence has gone up by one.
sequences(listSoFar, itemsInList); // Complete sequence in all possible ways.
itemsInList--; // Removes i from end of sequence before doing next item.
}
}
}
This method is called from the main method with itemsInList set equal to zero, that is with no items initially in the list. (Note, by the way, that this recursive method is not the best way to generate sequences. If you look at the output from the program, you'll notice that it is essentially counting in the base N. The right way to generate all possible sequences of N items is to count in the base N and use the digits in each base-N number to tell you which items to put into the corresponding sequence.)
Your method for generating permutations will be very similar to this one. It just has to avoid putting duplicate items into the list. The nice way to do this is to add a second array parameter, used of type boolean[]. The value of used[i] should be true if and only if i is already in the list. If used[i] is true in the for loop, then i should not be added to the list. You just have to be careful to keep the values in the boolean array used correctly in sync with the contents of the the list.
The method for generating derangements is similar, but you should also be careful not to place i into position number i in the list.
Your completed program should have two methods, one that generates and counts permutations and one that generates and counts derangements. At the end of the program, output:
You might also want to print out the value of e for comparison. In Java, e is represented by the constant Math.E.