--- 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}