diff -r 293ea84d82ca -r 62389faa66e4 cws/cw02.tex --- a/cws/cw02.tex Fri Jan 27 14:55:56 2017 +0000 +++ b/cws/cw02.tex Wed Feb 01 13:54:55 2017 +0000 @@ -27,7 +27,7 @@ \noindent \textbf{Important:} Do not use any mutable data structures in your -submissions! They are not needed. This excludes the use of +submissions! They are not needed. This means you cannot use \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your code! It has a different meaning in Scala, than in Java. Do not use \texttt{var}! This declares a mutable variable. Feel free to @@ -35,7 +35,8 @@ \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the functions you submit are defined on the ``top-level'' of Scala, not inside a class or object. Also note that the running time of -each part will be restricted to a maximum of 360 seconds. +each part will be restricted to a maximum of 360 seconds on my +laptop. \subsection*{Disclaimer} @@ -48,9 +49,8 @@ \subsection*{Background} The \textit{Knight's Tour Problem} is about finding a tour such that -the knight visits every field on an $n\times n$ chessboard once. Such -a tour is called \emph{open} tour. For example on a $5\times 5$ -chessboard, an open knight's tour is: +the knight visits every field on an $n\times n$ chessboard once. For +example on a $5\times 5$ chessboard, a knight's tour is: \chessboard[maxfield=d4, @@ -90,7 +90,7 @@ A knight's tour is called \emph{closed}, if the last step in the tour is within a knight's move to the beginning of the tour. So the above -knight's tour is \underline{not} closed (it is open) because the last +knight's tour is \underline{not} closed because the last step on field $(0, 4)$ is not within the reach of the first step on $(4, 4)$. It turns out there is no closed knight's tour on a $5\times 5$ board. But there are on a $6\times 6$ board and on bigger ones, for @@ -199,12 +199,12 @@ \subsubsection*{Tasks (file knight1.scala)} \begin{itemize} -\item[(1a)] Implement an is-legal-move function that takes a +\item[(1a)] Implement an \texttt{is-legal-move} function that takes a dimension, a path and a position as argument and tests whether the position is inside the board and not yet element in the path. \hfill[1 Mark] -\item[(1b)] Implement a legal-moves function that calculates for a +\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 @@ -227,19 +227,19 @@ \item[(1c)] Implement two recursive functions (count-tours and enum-tours). They each take a dimension and a path as - arguments. They exhaustively search for {\bf open} tours starting - from the given path. The first function counts all possible open + arguments. They exhaustively search for tours starting + from the given path. The first function counts all possible tours (there can be none for certain board sizes) and the second - collects all open tours in a list of paths.\hfill[2 Marks] + collects all tours in a list of paths.\hfill[2 Marks] \end{itemize} \noindent \textbf{Test data:} For the marking, the functions in (1c) will be called with board sizes up to $5 \times 5$. If you search -for open tours on a $5 \times 5$ board starting only from field $(0, 0)$, +for tours on a $5 \times 5$ board starting only from field $(0, 0)$, there are 304 of tours. If you try out every field of a $5 \times -5$-board as a starting field and add up all open tours, you obtain +5$-board as a starting field and add up all tours, you obtain 1728. A $6\times 6$ board is already too large to be searched -exhaustively.\footnote{For your interest, the number of open tours on +exhaustively.\footnote{For your interest, the number of tours on $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320, 19591828170979904, respectively.} @@ -271,7 +271,7 @@ is; your code should do this only \textbf{once}!\\\mbox{}\hfill[1 Mark] \item[(2b)] Implement a first-tour function that uses the - first-function from (2a), and searches recursively for an open tour. + first-function from (2a), and searches recursively for a tour. As there might not be such a tour at all, the first-tour function needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks] \end{itemize} @@ -283,9 +283,9 @@ \subsection*{Part 2 (3 Marks)} -As you should have seen in Part 1, a naive search for open tours +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) +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 @@ -331,7 +331,7 @@ 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 \textbf{open} tours. You have + 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] \end{itemize}