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, commandline 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 xdirection and one square in the ydirection
 one square in the xdirection and two squares in the ydirection
A knight's tour starts by convention in the upperleft 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 remainbecause 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 commandline arguments,
as described below. The program should work for any positive
integervalued 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 "singlechoice" 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:
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] 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:
No solution found for 3 rows and 3 columns!
Program Requirements
 Your program must take three commandline 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 3by3 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 rowmajor
order. That is, you should look through the array, from row 0 through
row ROWS1, and within each row from column 0 through column COLS1, 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.
 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.
 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 extracredit 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 twodimensional 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.
CSEE  201
 201 F'06  lectures  news  help
Wednesday, 25Oct2006 10:40:39 EDT