CSci 133 Project 1

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

Project #1

Due Date: beginning of class, Thursday, Feb. 2, 2006
This project depends on Lewis/Loftus, especially Section 6.3

The purpose of this project is to refresh your memories of programming since you took CSci 53, and to give students who took different introductory courses a chance to get up to speed with Java. Start working on this now, so you have a chance to ask questions about anything you don't understand!

In this project you'll develop a program to do the data management for a very simple 1-person game derived from chess, called the knight's tour. You do not need to know how to play chess to do this project!

Background:

Chess is an ancient board game. Early versions were played 1500 years ago in India, China, and Persia, and the current version is played all over the world. Wikipedia has a very good chess section at http://en.wikipedia.org/wiki/Chess. If you don't know chess and want to learn, a good Internet resource is http://www.chessclub.demon.co.uk/tutorial/play_chess.htm.

The game as we know it is played on a checkerboard with 8 rows, called ranks, and 8 columns, called files. The ranks are designated 1 through 8; the files are designated a through h. There are 6 types of pieces; each type of piece has its own rules for moving. A normal board, set up at the start of the game, looks like this:

Each kind of piece has its own rules for moving. For this project, we are interested only in the knight, whose moves are the most interesting.

The Knight's Moves

The knight is a horse-shaped piece, suggesting a medieval knight on horseback. Starting from any given square, it must stay on the board and may move only in an L-shaped patten, either

two ranks forward or backward, then one file left or right, or
two files left or right, then one rank forward or back

This picture shows the valid moves. If the knight is currently at d4, it may move to b3, b5, c2, c6, e2, e6, f3, or f5, and nowhere else.

The Knight's Tour

Pretend a white knight is the only piece on the board. The knight starts in some square (perhaps its normal start position, b1), and moves validly from square to square. The objective of the game is to land on each square exactly once; it cannot move to a square it has previously visited. The game is over when the knight has no moves left. A perfect game (which is rarely achieved!) covers all 64 squares.

You can see how this works, and play the game, by visiting http://www.borderschess.org/KnightTour.htm.

In this project we will represent the chessboard as a 2-dimensional array of pieces, displaying it in a simple text format. The pieces are denoted by e.g., BQ (Black Queen) and WN (White Knight). A normal game setup would look like

8 BR BN BB BQ BK BB BN BR

7 BP BP BP BP BP BP BP BP

6 .. .. .. .. .. .. .. ..

5 .. .. .. .. .. .. .. ..

4 .. .. .. .. .. .. .. ..

3 .. .. .. .. .. .. .. ..

2 WP WP WP WP WP WP WP WP

1 WR WN WB WQ WK WB WN WR

a b c d e f g h

A Knight's Tour setup might look like

8 .. .. .. .. .. .. .. ..

7 .. .. .. .. .. .. .. ..

6 .. .. .. .. .. .. .. ..

5 .. .. .. .. .. .. .. ..

4 .. .. .. .. .. .. .. ..

3 .. .. .. .. .. .. .. ..

2 .. .. .. .. .. .. .. ..

1 .. WN .. .. .. .. .. ..

a b c d e f g h

Your program will start the game with the knight at b1, then, repeatedly,

display the board, marking visited squares;
prompt the user for a move (a letter followed by a space and a digit);
if the file or the rank is out of range, display a message and ask the user to try again, if

if the file or the rank is out of range;
the move is not a valid knight's move;
the destination square is already occupied;

if the move is valid and the square has not been previously visited, mark the new square as visited and move the knight there

The program ends when the user presses ctrl-C.

It's easier to follow the game if, instead just displaying a sequence of WN icons, we display the number of the move. Using this approach, suppose the knight moves from b1 to c3 (a valid move); the next board display will look like:

8 .. .. .. .. .. .. .. ..

7 .. .. .. .. .. .. .. ..

6 .. .. .. .. .. .. .. ..

5 .. .. .. .. .. .. .. ..

4 .. .. .. .. .. .. .. ..

3 .. .. 2 .. .. .. .. ..

2 .. .. .. .. .. .. .. ..

1 .. 1 .. .. .. .. .. ..

a b c d e f g h

If the next move is (say) to e2, the next display will be

8 .. .. .. .. .. .. .. ..

7 .. .. .. .. .. .. .. ..

6 .. .. .. .. .. .. .. ..

5 .. .. .. .. .. .. .. ..

4 .. .. .. .. .. .. .. ..

3 .. .. 2 .. .. .. .. ..

2 .. .. .. .. 3 .. .. ..

1 .. 1 .. .. .. .. .. ..

a b c d e f g h

and so on until the game terminates.

The Java application programs133/KnightTour.java is a skeletal one that reads one move and positions the knight, using the Screen class to put the board in the center of the screen. You can copy this file and use it 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 skeletal program doesn't validate its inputs. As a reminder of how to read and validate the range of an input, you can study programs133/ShowInputLoop.java.

What to submit:

Submit your project according to the rules we used in CSci 53. See Systematic Software Development for a reminder. Deliverables should include:

Document for your analysis

Document for your algorithm with detailed explanations.

Code -- a listing (.txt) file (not a source file!)

Document for your test plan

Test Results -- a printout (turnin script)

Grading:

Grading for this first project will be 0-20 points, as in CSci 53: Analysis/Design: 0-6, Test Plan: 0-4, Program Implementation 0-6, Code style and layout, 0-4.