diff -r 716042628398 -r d306102fd33b cws/cw02.tex --- a/cws/cw02.tex Tue Nov 14 13:14:47 2017 +0000 +++ b/cws/cw02.tex Tue Nov 14 21:34:22 2017 +0000 @@ -188,7 +188,7 @@ \noindent Let us first fix the basic datastructures for the implementation. The board dimension is an integer (we will never go beyond board sizes of -$50 \times 50$). A \emph{position} (or field) on the chessboard is +$40 \times 40$). A \emph{position} (or field) on the chessboard is a pair of integers, like $(0, 0)$. A \emph{path} is a list of positions. The first (or 0th move) in a path is the last element in this list; and the last move in the path is the first element. For @@ -219,7 +219,7 @@ \item[(1b)] Implement a \texttt{legal-moves} function that calculates for a position all legal onward moves. If the onward moves are placed on a circle, you should produce them starting from - ``12-oclock'' following in clockwise order. For example on an + ``12-o'clock'' following in clockwise order. For example on an $8\times 8$ board for a knight on position $(2, 2)$ and otherwise empty board, the legal-moves function should produce the onward positions in this order: @@ -292,14 +292,14 @@ \textbf{Testing} The first tour function will be called with board sizes of up to $8 \times 8$. - +%%\newpage \subsection*{Part 2 (3 Marks)} -As you should have seen in Part 1, a naive search for tours -beyond $8 \times 8$ boards and also searching for closed tours -takes too much time. There is a heuristic, called Warnsdorf's rule -that can speed up finding a tour. This heuristic states that a knight -is moved so that it always proceeds to the field from which the +As you should have seen in Part 1, a naive search for tours beyond +$8 \times 8$ boards and also searching for closed tours even on small +boards takes too much time. There is a heuristic, called Warnsdorf's +rule that can speed up finding a tour. This heuristic states that a +knight is moved so that it always proceeds to the field from which the knight will have the \underline{fewest} onward moves. For example for a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible onward moves, namely 2. @@ -342,10 +342,12 @@ a solution when started in the middle of the board (that is position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] -\item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. - It is the same function as in (3b) but searches for tours. You have - to be careful to write a tail-recursive version of the first-tour-heuristic - function otherwise you will get problems with stack-overflows. \hfill[1 Mark] +\item[(3c)] Implement a first-tour-heuristic function for boards up to + $40\times 40$. It is the same function as in (3b) but searches for + tours (not just closed tours). You have to be careful to write a + tail-recursive version of the first-tour-heuristic function + otherwise you will get problems with stack-overflows.\\ + \mbox{}\hfill[1 Mark] \end{itemize} \end{document}