UMBC CS 104
UMBC CMSC 104 * CSEE | 104 | current 104

Project 8 - A Knight's Tour

CMSC 104, Fall 2002

Due Date: 5:30 pm, Tuesday, 12/10.

Point Value:

The first part of the project is worth 20 points as normal. The additional parts of the project as marked are worth 20 points of EXTRA CREDIT.

Objectives:

To become more familiar with:




(20 Points) Can a knight move around a chess board touching each square exactly once? Create a program called knight.c that simulates a knight moving around a chess board.

A chess board is an 8x8 grid of squares and a knight moves around the board according to one of the following rules:


For the first part of the project, your program is expected to conduct the knight's tour 100 times, recording each tour length (a tour is defined as the number of moves through the board until the knight cannot move anymore), the average tour length, the longest tour length, and a printout of the longest tour. The tour should use the random.h library to select the starting position, and for each move, select one of the possible available moves randomly. In essence, you should end up with 100 different tours.

You are required to turn in a printout of your C code, along with a printout of two different runs of your program. To generate the the output file, use output redirection (>) as we discussed in class.

(20 Points Extra Credit) Modify your knight.c program by creating a new version called smart_knight.c. The extra credit should behave exactly like the the first part of the project, but the knight should use some knowledge about the nature of the chess board. In particular, the knight can know before the tour starts, how many moves are "possible" from any given position on the board. Then, instead of randomly moving around the board, the knight can intelligently move based on this knowledge. Which positions should be attempted to be visited first . . . ? Can the knight touch every square exactly once?

To receive all of the extra credit points, you should turn in a one-to-two paragraph description of your strategy for smartly moving the knight around the board, the C code, and two printouts of different runs of your program.

All materials submitted for grading MUST be on white paper, with black ink, and typeset (not handwritten). Handwritten materials will not be accepted.

No late work will be accepted! No exceptions! The project is due on the last day of class, 10 December 2002 at 5:30 pm.

GOOD LUCK!!!



Last Modified: Monday, 02-Dec-2002 09:48:24 PM EST