Project Outline

The goal of this project is to use a graph to represent a problem and then strategize ways to solve the problem. We will be using the graph class from the first programming project to represent our graphs. You can still display the graph by displaying the adjacency matrix. This project is based on "Shannon's Switching Game", a project from the Applied Graph Theory and Algorithms class at UCSC.*

I have been contacted by a master gardener who has a problem at all the gardens that she manages. The woodchucks eat the flower bulbs in the flower gardens and the vegetables in the vegetable garden. She has found a way to map out the tunnels of the woodchucks between their hole and the gardens. She doesn't want to harm the woodchucks, just stop the woodchucks from getting to her garden. She has found a way to completely destroy a tunnel between two intersection points. The woodchuck has also found a way to reinforce his tunnel so that the gardener cannot destroy the tunnel.

Your job is to write a simulation that takes in the description of the tunnels and intersections. The first phase of this project is to design the program. We will do this in class on Thursday of Sixth Week. Once we have a design, we will write up the rest of the project specifications. The second phase will be to create the simulation so that two humans may play the game - one acting as the gardener, one the woodchuck. The second phase will be due on Thursday of Eighth week. The final phase of the project will be to allow the computer to take over the job of either the gardener or the woodchuck or both. You will need to develop different strategies to help the woodchuck or the gardener to win.

You may work on this project in groups but I think you will get more out of this project if you work alone.

As with most programming projects, be sure that the work turned in is your own. You are welcome to discuss problems with other groups, but please do NOT look at another group's code or let another group look at your code. You should also acknowledge any assistance you recieve on this project somewhere in your documentation.

Be sure to document your project using the standards of this department. In other words, there should be lots of comments throughout your code describing what you are doing and why. Javadocs would be a great addition to your program.

1. We will be using your graph class from the previous programming project. Since a way to input and output a graph already exists there will be only minor modifications needed. You may want to add things specific to the project (such as a way to denote the Gardener or the Woodchuck hole) or make the output easier to use for the game.

2. You will need to add one (or more) methods to your graph class. The method that is most needed is to determine who won. The woodchuck wins if there is a reinforced path from the Garden to the Woodchuck hole. The Gardener wins if there is no path from the Garden to the Woodchuck hole.

3. You will also need a class (or the main) to handle the simulation. The simulation should randomly choose who will begin, ask for the edge to be destroyed/reinforced and then ask the graph to modify that edge, The simulation should allow turns to be taken in destroying/reinforcing edges until someone has wowon.

4. It may be useful to create a method in your graph class that inputs a rather large graph that you can use to test your program along the way. You may have a special input when the user is asked for the number of vertices that triggers this large graph to be used for the game. If you do use this option, document in the comments how to use it so I can use it for grading.

5. For the next portion of this project you will be implementing at least 3 strategies that the Gardener or Woodchuck can use. You will also need to modify your program so that any number of players can be involved in the game (0 - 2). The easiest strategy to use will be the random strategy. That will count as one of your 3 strategies.

How to turn in your code:

• By Thursday of Eighth week - E-mail me the java files or the project zipped no later than 8:30 am. I will only grade that it works for small graphs (or the graph that you have hard coded for an example). I will not be grading design and comments at this point although comments within your code help you write the code easier. You may also be farther in your project than the requirements for this section - I will just test that two players can play the game. (10 points - 2 points off for every half day it is late)

• By Thursday of Tenth Week - Email me the java files or the project zipped no later than noon. Remember that I will be grading comments (10 points) and design (10 points) as well as how well it works (20 points).