Lab 4: Exercises in Recursion

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:

- the number of permutations,
- the value of factorial(
`ITEMS`), which should be the same as the number of permutations, - the number of derangements, and
- the number of permutations divided by the number of derangements, which should be close to
*e*.

You might also want to print out the value of *e* for comparison. In Java, *e*
is represented by the constant `Math.E`.