Project 4 Fall '06

CMSC 201
Programming Project Four

The Knight's Tour

Out: Tuesday 11/7/06
Due Date: Sunday 11/19/06, before midnight

The design document for this project, design4.txt, is due: Before Midnight, Sunday 11/12/06

The Objective

The purpose of this assignment is to give you practice with arrays, command-line arguments, file handling, and recursion.

The Background

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

two squares in the x-direction and one square in the y-direction
one square in the x-direction and two squares in the y-direction

A knight's tour starts by convention in the upper-left square (position [0,0]), and moves around the board using legal knight moves, such that every square is visited exactly once. A closed knight's tour returns to the starting square. Here's a link with more information about the Knight's Tour problem. If you really want to know more about the nuts and bolts of the mathematics behind the Knight's Tour (and similar math puzzles), try the MathWorld page on the subject.

The Task

Your task is to write a program that will find a legal knight's tour (not necessarily a closed knight's tour) for a given board size, assuming that one exists. If no solution is found, then the program should print a message indicating that no legal solution exists.

Your program should use recursion to implement a backtracking search solution to this problem. Backtracking search works by starting from the initial position [0,0] and generating a list of successor moves. These moves are tried, one at a time. Each move generates a new position, which then leads to another set of successor moves. This process continues until either (a) a solution is found (the board has been entirely filled), or (b) a dead end is reached. Backtracking refers to the behavior of the program if a dead end is encountered (i.e., if the knight reaches a position where no legal moves remain--because all reachable squares have already been visited) before a solution is found. In this case, the recursive function will "bottom out" and should return a failure signal to the calling function. The recursion will "unwind" in this way to a point on the board where there is another legal move to try. If recursion "unwinds" all the way to the starting point, and no legal moves remain, then no solution exists.

The size of the board will be specified by two command-line arguments, as described below. The program should work for any positive integer-valued board dimensions. Here is a program trace showing how recursive backtracking search would work for a small 3x3 board. Note that the program records an unvisited board space with a "0" at that position on the board, and a visited space with the order in which it was visited. The program starts at [0,0], indicating that first square by recording a "1" in array position [0,0]. It then tries the first move it finds, which is to move the knight to [1,2] (recorded as "2"). This puts the program into a series of "single-choice" boards, where it only has one possible move. After 7 moves, at the 8th level of recursion, one square (the center square) is still empty, but it can't move there. It backtracks to the last move where it had more than one choice, which was the very first move, and tries the other choice, [2,1]. This leads to the same impasse: after 7 moves, the center square is empty, but the knight can't reach it. At this point, there are no more moves to try, and the program gives up.

% a.out [0] trying 0, 0 [1] trying 1, 2 [2] trying 2, 0 [3] trying 0, 1 [4] trying 2, 2 [5] trying 1, 0 [6] trying 0, 2 [7] trying 2, 1

Here's what the board looks like after the first seven moves:

1	4	7
6		2
3	8	5

There are no moves remaining, but the tour is incomplete. At this point, the program backtracks to the very first move (which was the only move where there was more than one choice). Here's what the board looks like after backtracking to the first move:

1

[1] trying 2, 1 [2] trying 0, 2 [3] trying 1, 0 [4] trying 2, 2 [5] trying 0, 1 [6] trying 2, 0 [7] trying 1, 2
Here's what the board looks like after trying the final seven moves, just before it backtracks all the way to the start, and discovers there are no moves remaining:

1	6	3
4		8
7	2	5

No solution found for 3 rows and 3 columns!

Program Requirements

Your program must take three command-line arguments that specify the dimensions of the board (rows and columns) and an output file, in the following format:
a.out <ROWS> <COLS> <OUTPUTFILE>
For example,
a.out 3 3 tour3x3.out
would look for a knight's tour on a 3-by-3 board, and put the output of the program into a file called tour3x3.out.
Your program must be implemented recursively, as discussed above.
Your program must use this function, which we have provided, to generate the sequence of moves to consider:
int FindNextMoves (int **board, int **nextMoves, int rows, int cols, int row, int col)
You should copy the files knightmoves.o and knightmoves.h from the directory /afs/umbc.edu/users/s/b/sbogar1/pub. This function takes the current board and a second array, the dimensions of these two arrays (rows and cols), and the current row and column of the knight. (Note that this function assumes the representation described previously, that the board has a "0" in each unvisited square, and a sequence number (greater than 0) in visited squares.) FindNextMoves fills in the second array with the possible next moves, by placing the value TRUE in the array at locations where the knight can legally move next, and FALSE where the knight cannot move. You must consider the moves in this array in row-major order. That is, you should look through the array, from row 0 through row ROWS-1, and within each row from column 0 through column COLS-1, to see what moves are possible. You must try the moves in that order. If you do not, you may find a valid solution that is not the "correct" solution for the project, and you will not receive full credit.
Your program must output the first solution it finds as a formatted ROWSxCOLS grid of numbers, representing the order of moves that the knight makes. Since the knight always starts at [0,0], the upper left corner will be designated as location 1. The other grid locations should contain the move number when the knight visits that location. If no solution is found, a failure message should be printed. The solution (or failure message) should be printed into the output file specified on the command line. See the sample run.
After printing the board (or a failure message), your program must output (to the output file) the following information. See the sample run.
1. The number of successor moves generated during search. This is the total number of all successor moves that were ever generated by the FindNextMoves function.
2. The number of positions actually visited (tested) during search. This is the number of successor moves that actually generated a recursive call to the search function.
Neither of these counts should include the initial knight position [0,0], since that position is not a successor to any other position.
You must use separate compilation for this project. You MUST have a file called proj4.c that contains main(), but you may have as many .c and .h files as you wish, with a minimum of 3 files.
For extra credit, you may provide a command line option "-opt" which attempts to find the "optimal tour"; that is, the one that requires the fewest moves to be tested in finding the solution. (Note that you don't need to actually find the optimal tour; you just need to implement a solution that is more likely to find the optimal tour than the default behavior of the program. You must also provide an explanation of why you think your algorithm will work.)
This extra credit program should be invoked as follows:
% a.out -opt
Note that the only difference between the extra-credit program and the "normal" version should be the order in which successor moves are tried. If you wish to receive extra credit for this option, you must indicate in your proj4.c file header that you have implemented this option, along with a short summary of how your program finds the optimal tour. (Be warned: This is quite a bit harder than the basic problem, so be sure that you have that completely working before you start working on the extra credit.)

Program Hints

Be sure to allocate space for the nextMoves array that you will pass to the FindNextMoves function, and to free the array when you no longer need that information.
You may want to use the functions Get2DSpace and Free2DSpace from the Lecture 16 notes to allocate and free up space for the board and the nextMoves array.
The knightmoves.o file contains two other functions you may find useful. LegalIndices() takes a current row and column, and the dimensions (rows and columns) of the board. It returns TRUE if the current row and column are legal array indices for the board, and FALSE otherwise. ClearArray takes a two-dimensional array (int **) and its dimensions (rows and cols), and sets all of the array's elements to zero. The function prototypes for these functions are given in knightmoves.h.

Sample Run

% a.out Usage: a.out ROWS COLS OUTPUTFILE % a.out 3 3 3x3soln.txt % cat 3x3soln.txt No solution found for 3 rows and 3 columns! Number of moves generated: 14 Number of moves tried: 14 % a.out 3 7 3x7soln.txt % cat 3x7soln.txt 1 4 7 18 15 10 13 6 19 2 9 12 21 16 3 8 5 20 17 14 11 Number of moves generated: 3825 Number of moves tried: 3818 % a.out 6 6 6x6soln.txt % cat 6x6soln.txt 1 8 5 20 3 10 6 19 2 9 34 21 15 28 7 4 11 32 18 25 16 33 22 35 29 14 27 24 31 12 26 17 30 13 36 23 Number of moves generated: 183667 Number of moves tried: 183634 %

Submitting the Program

To submit your program, type the following command at the Unix prompt

submit cs201 Proj4 followed by the .c and .h files necessary for compilation

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj4

Acknowledgements

Thanks to Matt Gaston for providing an earlier version of this assignment. Knights Tour animation borrowed from Dan Thomasson.

Wednesday, 25-Oct-2006 10:40:39 EDT