: この文書について...
CSL102: Introduction to Computer Science
II semester 2004-05
Backtracking algorithms: The Knight's tour
Assume an chess board with squares numbered from to
.
Assume a knight starts from the square and tries to traverse the entire chess
board by stopping on each square exactly once. The knight follows its
usual L-shaped move as in chess. Hence a knight on square can move to one of
the squares or only. A successful knight's tour is the path traversed
by the knight, represented as a list of squares. In general, depending upon the value of
and the starting point, there may exist 0 or more successful knight's tours.
Write a function knight_tour which takes as a parameter and outputs the list of
all possible successful knight's tours.
Note:
- You are not allowed to change any of the names given in
the signature. You are not even allowed to change upper-case letters
to lower-case letters or vice-versa.
- You may define any new functions you like in the structure besides those
mentioned in the signature.
- Your program should work with the given signature.
- You need to think of the most efficient way of implementing the
various functions given in the signature so that the function results
satisfy their definitions and properties.
- Since the evaluator is going to look at your source code before
evaluating it, you must explain your algorithms in the form of ML
comments, so that the evaluator can understand what you have implemented.
- Do not add any more decorations or functions or
user-interfaces in order to impress the evaluator of the program.
Nobody is going to be impressed by it.
- There is a serious penalty for copying. If it is felt that there is too
much similarity in the code between any two persons, then both are going
to be penalized equally. So please set permissions on your directories,
so that others cannot copy your programs.
: この文書について...
S Arun-Kumar
平成17年3月28日