Knight's Tour Project

Contents of This Web Page

What and When

Due Date:
This assignment is due on the date of Class 7 for your section. Consult that syllabus page for your section's meeting date.

Note that the due date is the class following your first exam for the course. The exam will be based in part on the project, in the sense that working on the project is a good way to review for the exam.

Deliverables:
Send a tar file of your "clean" project directory, containing a Makefile, your source code files, and a text file containing a project report. See the Project Management web page for information on making a clean project directory and submitting the assignment. See the Project Report section below for information about the report.

Project Description

This project is based on, but is not the same as, Exercises 4.24 and 4.25 in the textbook. Read those two exercises carefully before working on the project.

You are to write two functions that use different algorithms to solve the chess problem known as the Knight's Tour and a driver program that exercises the two algorithms. One function, which is to be named brute(), is to implement the brute-force algorithm described in Exercise 4.25, and the other function, which is to be named heuristic(), is to implement the algorithm described in Exercise 4.24c. You may also implement the algorithm described in Exercise 4.24d if you wish, but it is not expected, and is not required.

The two functions for the two algorithms are both to take an int between 0 and 63 indicating the square on which to start the tour, and are to return an int between 0 and 63 telling how many moves were made before the tour could continue no further. You may map the starting square number to a particular cell on the board any way you wish as long as each value maps onto a different square.

The main program is to call each algorithm some large number of times, such as 64,000, and is to count how many tours of each length each algorithm makes. Each tour should start on a different square, so the number of times each function is called should be a multiple of 64.

The main program is also to determine the average time it takes the two algorithms to perform a tour and to make a single move. We are providing you with two functions, startTiming() and stopTiming(), for you to use to make the timing measurements.

The functions main(), brute(), and heuristic() must each be defined in its own source file. The names of the source files must be tour.cc, brute.cc, and heuristic.cc respectively.

Files Supplied to You

The directory ~vickery/CS-200/Project_1 contains several files you will use to help develop the project. Begin work on the project by creating your own project directory and copying all the files in Dr. Vickery's project directory into it. If you type the command, make, a complete executable version of the project will be built. The name of the executable file will be tour.

This tour program outputs more than a screenful of information, so you might want to capture its output in a file: 

     $ tour > tour.out
In this case, the output from the tour command has been redirected to the file named tour.out, which you can examine with more or a text editor. Refer to the Using Unix web page if you are not familiar with I/O redirection.

Also, this tour program accepts the number of tours each algorithm is to run as an optional command line argument: 

     $ tour 64 > tour.out
Your program is not required to take a command line argument.

Each of the files given to you is described here:

Makefile
This is a copy of the default Makefile for this course (~vickery/CS-200/Makefile) which has been tailored to this project.

You do not need to modify this file, but it needs to be present for the make command to work properly as you work on the project.

Here is an overview of what make will do when this Makefile is in your project directory:

Among other things, the Makefile contains a list of targets, which are the names of files or operations that you might want to "make." The targets in this Makefile are named tour, testTiming, clean, and depend. Since tour is the first target specified in the Makefile, that is the one that is made by default when you type the make command with nothing else on the command line.

The rule for making tour in the Makefile is to execute the command: 

g++ -g tour.o board.o brute.o heuristic.o timing.o -o tour
Remember, you don't type in this command, you type "make" and make executes this command for you.

As you should know from class, this command doesn't cause anything to be compiled because only .o files are listed. The compiler driver just links all the files listed with the standard library and produces an executable file named tour.

The power of make is that before executing the command above it will check if there are any files with .cc extensions that might might need to be compiled to produce any of the indicated .o files. Thus, when you create your own brute.cc file in the project directory and execute make, it will find your file and will also determine that your file was edited more recently than brute.o was compiled, and make will automatically create a new brute.o file by executing this command for you: 

g++ -g -c brute.cc
Make will then execute the g++ command given earlier to link all the .o files together. At this point, the brute.o file that we supplied to you (see below) will be replaced by your own file with the same name. Of course you can always get another copy of the one we supplied from ~vickery/CS-200/Project_1 if you want to.

As you might guess, this description of how make handles brute.cc and brute.o applies to all the files in the project. Since you won't create files named board.cc or timing.cc, make will always link the board.o and timing.o files that we supplied you. But as you work on the project (See the Development Strategy section below), you will create your own versions of tour.cc and heuristic.cc, and make will compile and link your new code as you develop it, even though the only command you ever give for building the project is just plain make.

tour.h
This header file contains the function prototypes for heuristic() and brute().

Note: You must include this file in all three of your source code files using the #include preprocessor command.

timing.h
This header file contains the function prototypes for two functions, startTiming() and stopTiming(). You do not have to write eather of these functions, but you need to call them from your driver program to do the timing analysis required for this assignment. (If you want to look at the source code for these function definitions, it is available in ~vickery/CS-200/timing.cc.)

Note: You can find out how long a section of code takes to execute by calling startTiming() before entering the code to be measured and by calling stopTiming() after the section finishes. The value returned by stopTiming() is given in microseconds (millionths of a second), but the granularity of the clock on qcunix1 is 1/1024 second (976.56 microseconds), so you will not get a meaningful value unless you execute a lot of code between the point where you start timing and the point at which you stop. For example, if you try to find out time the execution of one call to your brute() function, you will almost always get a value of 0.00, and sometimes will get a value of 976.56, neither of which is correct. (The correct answer is undoubtedly somewhere in between.) On the other hand, if you measure the time it takes to call brute() 10,000 times and divide the result by 10,000 you will get a good estimate of the average time per call.

board.h
We are supplying some utility functions that you may or may not choose to use. If you do use them, you will need this header file for the function prototypes. These utilities assume there are global arrays of int named chessBoard[8][8] and accessibility[8][8]. The function clearBoard() sets each element of chessBoard to zero, the function printBoard() (which is included only as a debugging aid) prints the chessBoard array, and the function initAccess() initializes the accessibility array to the values given in Exercise 4.24c.

Note: The functions brute() and heuristic() that we are supplying both call clearBoard(), and heuristic() also calls initAccess(). Thus, to use the object modules we supply, you must be sure to link board.o with them. The main function that we supply will not call either of these two functions for you, so you will either have to call them from your own brute() and heuristic() functions or do those two operations yourself somehow.

tour.o
brute.o
heuristic.o
These are pre-compiled versions of the driver program and the two functions you are to code. Don't look for the source code for these modules; writing that is your assignment!
board.o
timing.o
These are the object modules for the chessboard and timing utility functions that you will link to your own object modules.
timingTest.cc
This is not really part of the project, it is a sample program that illustrates the use of the timing utilities.

Development Strategy

The main reason we are supplying you with object modules is so you won't have to write all the code for the project at once, which makes debugging extremely difficult. Instead, you will develop your program in a sequence of steps. During each step you will work on just one source module at a time, so that you will always have just one place to look for bugs. (The other reason for supplying you with object modules is to give you real-world experience in integrating your code with that written by other people.)

The first module you should work on is brute.cc because brute() is simpler to implement than either main() or heuristic(). You might want to have your brute() call printBoard() just before it returns to make sure the tour looks correct while you are debugging your code. Your function should use the global variables chessBoard, horizontal, and vertical (see below).

It is a project requirement that the file containing your brute() function definition is named brute.cc and that your brute.o links with the other object modules we provided to produce an executable program named tour.

Once you have brute() working, you should write your own version of tour.cc that exercises both brute() and heuristic(). You will still use our copy of heuristic.o at this stage.

As mentioned earlier, your tour.o must work with our brute.o and heuristic.o, and your heuristic.o must work with our tour.o. (If I missed any permutations here, they are required too!)
NOTE: Your tour.cc will have to define the following global variables: 

int             chessBoard[8][8];
int             accessibility[8][8];
const int       horizontal[8] = {  2,  1, -1, -2, -2, -1, 1, 2 };
const int       vertical[8] =   { -1, -2, -2, -1,  1,  2, 2, 1 };
Finally, write your own version of heuristic.cc. You can receive a passing grade for the project even if you do not complete this part of the assignment.

Documentation Required

There are no strict guidelines for how to document your code. You must put some comments at the very beginning that identify the file, what function(s) is (are) defined in it, and your name. Beyond that, write your code so it is neat and easy to read. Use meaningful variable names. Provide comments that introduce the various sections of your functions, but you do not need to supply line-by-line comments, and you generally do not need comments about your data. You can look at ~vickery/CS-200/timing.cc for an idea of how I like to document code.

Don't forget that you are required to provide a text file that tells users what your program does and how to use it. If you have not already done so, you should look at the Project Management web page for information on writing this file, and the Project Files section of that page in particular.

Project Report

Let's start with what the Project Report is not. It is not a report on programming or on C++. It is a report that compares the performance of the two algorithms you implemented for doing Knight's Tours.

The project report is to be based on the data you collected from your program. Even if you are unable to complete the programming assignment successfully, you will still be able to construct a working program from the object modules we supplied you and to write your report based on that.

Write your report in the format of a research paper. It is to be submitted as a text file, and should be formatted so it will be easy to read on the screen. Do not try to submit a document that you prepared with a word processor unless you are careful to convert it to the format of a Unix text file.

The report will be graded on English usage as well as on content, so be sure to use complete sentences that are gramatically correct with words spelled correctly. (You can use the spell command to check your file for spelling errors.)

The report is not to be very long. A few sentences for each of the sections listed below is enough.

Report Format

Give the report a meaningful title, which should be centered in the first line of the file. Put your name centered on the second line, and put the day of the week your section meets centered on the third line.

The report is to have the following sections, each of which is to be labeled as indicated here:

Introduction
Describe the purpose of the project in your own words. Remember, the purpose of the project as far as the report is concerned is to measure the performance of the two algorithms. It has nothing to do with programming or C++.
Method
Summarize the two algorithms and tell how your main program tested the two algorithms.
Results
Summarize the data you collected, but do not interpret the data. If you want to get fancy and prepare a table or graph, you may do so, but nothing like that is required or expected.
Discussion
Discuss the results you obtained and draw any conclusions that are supported by your data.

Submit the Project

You are to submit this assignment by following the instructions given in the Project Management Web page. The only files that are to be in your project directory when you tar it are the .cc files that you wrote, your tour.1 user documentation file, and the text file containing your report. It's all right if there is a copy of our Makefile is there too, since the make clean command will not remove it automatically.

From this project on, we would like you to use the name of your Unix account (like "abcqc") as the name of your tar file and to indicate what assignment you are submitting in the Subject: line of your mail message.

Dr. Christopher Vickery
Mr. Ruben Lusiniants
Queens College of CUNY
Dr. Vickery's Home Page