The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I
Project #1

Due Date: beginning of class, September 13, 2001
This project depends on Chapter 1 and Section 4.1

The purpose of this project is to refresh your memories of programming since you took CSci 51, and to give students who took a different introductory courses a chance to get up to speed with Ada 95. 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.

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. A very good chess history website is http://misc.traveller.com/chess/history/. If you don't know chess and want to learn, a good Internet resource is http://queen.chessclub.com/sji/index.html; the pictures below are adapted from a picture on that site.

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..8; the files are designated a..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 by visiting http://home.earthlink.net/~tfiller/knight.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 will look like

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

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

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

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

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

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

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

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

       a   b   c   d   e   f   g   h

The program will start the game as above then, repeatedly,

  • display the board, indicating by WN all the previously visited squares;
  • prompt the user for a move, a letter followed by a number; make sure neither the file nor the rank are out of range;
  • if the move is a valid move for a knight and the square has not been previously visited, mark the new square as visited and move the knight there
Suppose the knight moves from b1 to c3 (a valid move); the next board display will look like

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

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

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

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

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

  3   ..  ..  WN  ..  ..  ..  ..  ..

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

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

       a   b   c   d   e   f   g   h

Now implement two improvements:

  • use a different "icon" (say, XX) to indicate a previously-visited square, so that the latest square visited can be easily seen
  • use the Screen package to put the board in the center of the screen and use the bottom few lines of the screen for data input and program messages.

    • What to submit:

    Submit your project in the form of a “Case Study” as described in Feldman/Koffman and done in CSci 51. You may
    attach this assignment sheet as a problem statement, then write the Analysis, Design, Test Planning, Implementation,
    and Testing sections, referring to this sheet where appropriate. Deliverables should include:
     
  •       Document for your analysis
  •       Document for your algorithm with detailed explanations.
  •       Code -- a listing (.lsb) 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 51: Analysis/Design: 0-6, Test Plan: 0-4, Program Implementation 0-6, Code style and layout, 0-4.