School of Engineering and Applied Science Department of Computer Science CSci 133 -- Algorithms and Data Structures I http://www.seas.gwu.edu/~csci133/spring04 Prof. Michael B. Feldman mfeldman@gwu.edu

Before Starting:

Once your SEASCF account is up and running, you must run the same setup procedure that students do in CSci 53. You can do this using a Secure Shell session, from any Internet-connected computer, to hobbes.seas.gwu.edu. A version of the setup procedure is HERE. When you have completed the setup procedure, you are ready to continue with the next section.

The Project:

In this project you'll develop a program to do the data management for an adaptation of a very simple 1-person game called Stratagem. The original Stratagem was invented recently by Kristin Heckman, a GW graduate student who just completed her doctoral program and used this game as part of her dissertation in Artificial Intelligence.

Stratagem is played on a board with four rows and four columns. The rows and columns are number 0-3. There are thus 16 cells. At the start of the game, 15 cells are occupied by game pieces (like checkers); the empty cell is chosen randomly and can be any one of the 16. A typical initial game might look like this:

The Moves:

1. The move can be horizontal (along a row) or vertical (along a column).
2. Diagonal moves are not allowed.
3. Each move must jump over one occupied cell; the piece in that cell is then removed from the board.

Examples:

Now which possible moves are valid? ((0,0),(1,0)) is one. So are ((0,1),(1,1)) and ((2,3),(2,2)). After ((0,1),(1,1)), the board is:

One more example: if (0,1) is initially unoccupied:

then the moves ((2,1),(1,1)) and then ((2,3), (2,2)) go as follows:

Representing the Game:

Valid and Invalid Moves:

• any of the input coordinates are off the board (<0 or >3), or
• a coordinate of the destination cell would be off the board, or
• the move is not horizontal (the jumped row isn't the same as the start row) and not vertical (the jumped column isn't the same as the start column), or
• the jumped cell isn't adjacent to the start cell, or
• the start cell is not occupied, or
• the jumped cell is not occupied, or
• the destination cell is occupied

Your Program:

Your program will read and process moves from the human user at the keyboard, continuing until the user presses Control-C. The main logic of the program is expressed in this pseudocode:

initialize game board
loop forever
{
  read a move from the keyboard
  if the move is invalid
  {
    write an error message
  }
  else
  {
    execute the move
  }
}

The file programs53/Stratagem.java contains a partial solution, that reads one move and executes it, using the Screen class to put the board in the center of the screen and display the moves. This is 161 lines long. Copy this file and programs53/Screen.java, compile and run them, and use Stratagem as a starting point for your project. In your program, use the bottom few lines of the screen for data input and program messages.

Note that this partial program doesn't validate its inputs; your solution must do so. HINT: the most straightforward approach is to expand the "if" in the pseudocode into a series of "else if" blocks that test the invalidity conditions, like

if (move fails first condition)
{
  write message
}
else if (move fails second condition)
{
  write message
}
else if (move fails second condition)
{
  write message
}
. . .
else
{
  move is valid; execute it
}

What to submit:

1. a printed listing (.txt) file of your program
2. an e-mail message to Prof. Feldman and to Mohamed, containing your source code for the program, in case we wish to compile and run it. Do NOT send an attachment--instead, paste the source code into the text of the message. The e-mail must be sent before class on the due date; late submissions will be subject to the usual 20%-per-week "late fee".
   

Grading:

Grading for this first project will be 0-20 points: program correctness, 0-16; code style and layout, 0-4.