
diff -r fdc2c6fb7a24 -r 9891c9fac37e cws/cw02.tex
--- a/cws/cw02.tex	Tue Nov 15 23:08:09 2016 +0000
+++ b/cws/cw02.tex	Wed Nov 16 14:37:18 2016 +0000
@@ -16,13 +16,23 @@
 
 \section*{Coursework 7 (Scala, Knight's Tour)}
 
-This coursework is about searching and backtracking, and worth
-10\%. The first part is due on 23 November at 11pm; the second, more
-advanced part, is due on 30 November at 11pm. You are asked to
-implement Scala programs that solve various versions of the
+This coursework is worth 10\%. It is about searching and
+backtracking. The first part is due on 23 November at 11pm; the
+second, more advanced part, is due on 30 November at 11pm. You are
+asked to implement Scala programs that solve various versions of the
 \textit{Knight's Tour Problem} on a chessboard. Make sure the files
 you submit can be processed by just calling \texttt{scala
-  <<filename.scala>>}.
+  <<filename.scala>>}.\bigskip
+
+\noindent
+\textbf{Important:} Do not use any mutable data structures in your
+submissions! They are not needed. This excluded the use of
+\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
+code! It has a different meaning in Scala, than in Java.  Feel free to
+copy any code you need from files \texttt{knight1.scala},
+\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.
  
 \subsection*{Disclaimer}
 
@@ -78,7 +88,8 @@
 knight's tour is \underline{not} closed (it is open) 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 bigger, for example
+5$ board. But there are on a $6\times 6$ board and on bigger ones, for
+example
 
 \chessboard[maxfield=e5, 
             pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
@@ -146,15 +157,15 @@
             markfields={f5, e6},
             setpieces={Ng7, Nb2}]
 
-\subsection*{Part 1 (6 Marks)}
+\subsection*{Part 1 (7 Marks)}
 
 You are asked to implement the knight's tour problem such that the
 dimension of the board can be changed.  Therefore most functions will
-take the dimension as an argument.  The fun with this problem is that
-even for small chessbord dimensions it has already an incredably large
-search space---finding a tour is like finding a needle in a
-haystack. In the first task we want to see far we get with
-exhaustively exploring the complete search space for small
+take the dimension of the board as an argument.  The fun with this
+problem is that even for small chessbord dimensions it has already an
+incredably large search space---finding a tour is like finding a
+needle in a haystack. In the first task we want to see how far we get
+with exhaustively exploring the complete search space for small
 chessboards.\medskip
 
 \noindent
@@ -183,9 +194,10 @@
 \subsubsection*{Tasks (file knight1.scala)}
 
 \begin{itemize}
-\item[(1a)] Implement a 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[(1a)] Implement an 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
   position all legal onward moves. If the onward moves are
@@ -193,15 +205,15 @@
   ``12-oclock'' 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
+  positions in this order:
 
   \begin{center}
   \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
   \end{center}
 
-  in this order.  If the board is not empty, then maybe some of the
-  moves need to be filtered out from this list.  For a knight on field
-  $(7, 7)$ and an empty board, the legal moves are
+  If the board is not empty, then maybe some of the moves need to be
+  filtered out from this list.  For a knight on field $(7, 7)$ and an
+  empty board, the legal moves are
 
   \begin{center}
   \texttt{List((6,5), (5,6))}
@@ -210,16 +222,16 @@
 
 \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 \underline{\bf open} tours
-  starting from the given path. The first function counts all possible
-  open tours (there can be none for certain board sizes) and the second
+  arguments. They exhaustively search for {\bf open} tours starting
+  from the given path. The first function counts all possible open
+  tours (there can be none for certain board sizes) and the second
   collects all open 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 only search
-for open tours on $5 \times 5$ board starting from field $(0, 0)$,
-there are 304 of them. If you try out every field of a $5 \times
+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)$,
+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
 1728. A $6\times 6$ board is already too large to be searched
 exhaustively.\footnote{For your interest, the number of open tours on
@@ -231,8 +243,9 @@
 \begin{itemize}
 \item[(2a)] Implement a first-function. This function takes a list of
   positions and a function $f$ as arguments. The function $f$ takes a
-  position as argument and produces an optional path. The idea behind
-  the first-function is as follows:
+  position as argument and produces an optional path. So its type is
+  \texttt{Pos => Option[Path]}. The idea behind the first-function is
+  as follows:
 
   \[
   \begin{array}{lcl}
@@ -245,12 +258,12 @@
   \]
 
   \noindent That is, we want to find the first position where the
-  result of $f$ is not \texttt{None}.\newline\mbox{}\hfill[1 Mark]
+  result of $f$ is not \texttt{None}, if there is one.\mbox{}\hfill[1 Mark]
   
-\item[(2b)] Implement a first-tour function. Using the first-function
-  from (2a), search recursively for an open tour.  As there might not
-  be such a tour at all, the first-tour function needs to return an
-  \texttt{Option[Path]}.\hfill[2 Marks]
+\item[(2b)] Implement a first-tour function that uses the
+  first-function from (2a), and searches recursively for an open tour.
+  As there might not be such a tour at all, the first-tour function
+  needs to return an \texttt{Option[Path]}.\hfill[2 Marks]
 \end{itemize}
 
 \noindent
@@ -258,13 +271,13 @@
 sizes of up to $8 \times 8$. 
 
 
-\subsection*{Part 2 (4 Marks)}
+\subsection*{Part 2 (3 Marks)}
 
 As you should have seen in Part 1, a naive search for open tours
-beyond $8 \times 8$ boards and also for searching for closed 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 heuristice states that a knight
-is moved so that it always proceeds to the square from which the
+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.
@@ -281,7 +294,7 @@
 
 \noindent
 Warnsdorf's rule states that the moves on the board above sould be
-tried out in the order
+tried in the order
 
 \[
 (0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
@@ -295,11 +308,20 @@
 \subsubsection*{Tasks (file knight3.scala)}
 
 \begin{itemize}
-\item[(3a)] orderered-moves
+\item[(3a)] Write a function ordered-moves that calculates a list of
+  onward moves like in (1b) but orders them according to the
+  Warnsdorf’s rule. That means moves with the fewest legal onward moves
+  should come first (in order to be tried out first).
+  
+\item[(3b)] Implement a first-closed-tour-heuristic function that searches for a
+  \textbf{closed} tour on a $6\times 6$ board. It should use the
+  first-function from (2a) and tries out onwards moves according to
+  the ordered-moves function from (3a). It is more likely to find
+  a solution when started in the middle of the board (that is
+  position $(dimension / 2, dimension / 2)$).
 
-\item[(3b)] first-closed tour heuristics; up to $6\times 6$
-
-\item[(3c)] first tour heuristics; up to $50\times 50$
+\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.
 \end{itemize}  
 
 \end{document}




