diff -r 018b9c12ee1f -r f7bcb27d1940 cws/cw02-bak.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw02-bak.tex	Thu Nov 15 03:35:38 2018 +0000
@@ -0,0 +1,365 @@
+\documentclass{article}
+\usepackage{chessboard}
+\usepackage[LSBC4,T1]{fontenc}
+\let\clipbox\relax
+\usepackage{../style}
+\usepackage{disclaimer}
+
+\begin{document}
+
+\setchessboard{smallboard,
+               zero,
+               showmover=false,
+               boardfontencoding=LSBC4,
+               hlabelformat=\arabic{ranklabel},
+               vlabelformat=\arabic{filelabel}}
+
+\mbox{}\\[-18mm]\mbox{}
+
+\section*{Coursework 7 (Scala, Knight's Tour)}
+
+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 21 December at 11pm. You are
+asked to implement Scala programs that solve various versions of the
+\textit{Knight's Tour Problem} on a chessboard. Note the second part
+might include material you have not yet seen in the first two
+lectures. \bigskip
+
+\IMPORTANT{}
+Also note that the running time of each part will be restricted to a
+maximum of 360 seconds on my laptop: If you calculate a result once,
+try to avoid to calculate the result again. Feel free to copy any code
+you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
+\texttt{knight3.scala}.
+
+\DISCLAIMER{}
+
+\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. For
+example on a $5\times 5$ chessboard, a knight's tour is:
+
+\chessboard[maxfield=d4, 
+            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+            text = \small 24, markfield=Z4,
+            text = \small 11, markfield=a4,
+            text = \small  6, markfield=b4,
+            text = \small 17, markfield=c4,
+            text = \small  0, markfield=d4,
+            text = \small 19, markfield=Z3,
+            text = \small 16, markfield=a3,
+            text = \small 23, markfield=b3,
+            text = \small 12, markfield=c3,
+            text = \small  7, markfield=d3,
+            text = \small 10, markfield=Z2,
+            text = \small  5, markfield=a2,
+            text = \small 18, markfield=b2,
+            text = \small  1, markfield=c2,
+            text = \small 22, markfield=d2,
+            text = \small 15, markfield=Z1,
+            text = \small 20, markfield=a1,
+            text = \small  3, markfield=b1,
+            text = \small  8, markfield=c1,
+            text = \small 13, markfield=d1,
+            text = \small  4, markfield=Z0,
+            text = \small  9, markfield=a0,
+            text = \small 14, markfield=b0,
+            text = \small 21, markfield=c0,
+            text = \small  2, markfield=d0
+           ]
+           
+\noindent
+The tour starts in the right-upper corner, then moves to field
+$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
+$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
+bigger board there is. 
+
+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 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
+example
+
+\chessboard[maxfield=e5, 
+            pgfstyle={[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+            text = \small 10, markfield=Z5,
+            text = \small  5, markfield=a5,
+            text = \small 18, markfield=b5,
+            text = \small 25, markfield=c5,
+            text = \small 16, markfield=d5,
+            text = \small  7, markfield=e5,
+            text = \small 31, markfield=Z4,
+            text = \small 26, markfield=a4,
+            text = \small  9, markfield=b4,
+            text = \small  6, markfield=c4,
+            text = \small 19, markfield=d4,
+            text = \small 24, markfield=e4,
+            % 4  11  30  17   8  15 
+            text = \small  4, markfield=Z3,
+            text = \small 11, markfield=a3,
+            text = \small 30, markfield=b3,
+            text = \small 17, markfield=c3,
+            text = \small  8, markfield=d3,
+            text = \small 15, markfield=e3,
+            %29  32  27   0  23  20 
+            text = \small 29, markfield=Z2,
+            text = \small 32, markfield=a2,
+            text = \small 27, markfield=b2,
+            text = \small  0, markfield=c2,
+            text = \small 23, markfield=d2,
+            text = \small 20, markfield=e2,
+            %12   3  34  21  14   1 
+            text = \small 12, markfield=Z1,
+            text = \small  3, markfield=a1,
+            text = \small 34, markfield=b1,
+            text = \small 21, markfield=c1,
+            text = \small 14, markfield=d1,
+            text = \small  1, markfield=e1,
+            %33  28  13   2  35  22 
+            text = \small 33, markfield=Z0,
+            text = \small 28, markfield=a0,
+            text = \small 13, markfield=b0,
+            text = \small  2, markfield=c0,
+            text = \small 35, markfield=d0,
+            text = \small 22, markfield=e0,
+            vlabel=false,
+            hlabel=false
+           ]
+
+
+\noindent
+where the 35th move can join up again with the 0th move.
+
+If you cannot remember how a knight moves in chess, or never played
+chess, below are all potential moves indicated for two knights, one on
+field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
+
+
+\chessboard[maxfield=g7,
+            color=blue!50,
+            linewidth=0.2em,
+            shortenstart=0.5ex,
+            shortenend=0.5ex,
+            markstyle=cross,
+            markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
+            color=red!50,
+            markfields={f5, e6},
+            setpieces={Ng7, Nb2}]
+
+\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 of the board as an argument.  The fun with this
+problem is that even for small chessboard dimensions it has already an
+incredibly 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
+Let us first fix the basic datastructures for the implementation.  The
+board dimension is an integer (we will never go beyond board sizes of
+$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
+example the path for the $5\times 5$ chessboard above is represented
+by
+
+\[
+\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
+  $\underbrace{\texttt{(2, 3)}}_{23}$, ...,
+  $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}
+\]
+
+\noindent
+Suppose the dimension of a chessboard is $n$, then a path is a
+\emph{tour} if the length of the path is $n \times n$, each element
+occurs only once in the path, and each move follows the rules of how a
+knight moves (see above for the rules).
+
+
+\subsubsection*{Tasks (file knight1.scala)}
+
+\begin{itemize}
+\item[(1a)] Implement an \texttt{is\_legal\_move} function that takes a
+  dimension, a path and a position as arguments and tests whether the
+  position is inside the board and not yet element in the
+  path. \hfill[1 Mark]
+
+\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-o'clock'' following in clockwise order.  For example on an
+  $8\times 8$ board for a knight at position $(2, 2)$ and otherwise
+  empty board, the legal-moves function should produce the onward
+  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}
+
+  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))}
+  \end{center}
+  \mbox{}\hfill[1 Mark]
+
+\item[(1c)] Implement two recursive functions (\texttt{count\_tours} and
+  \texttt{enum\_tours}). They each take a dimension and a path as
+  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 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 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 tours, you obtain
+1728. A $6\times 6$ board is already too large to be searched
+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.}\bigskip
+
+\noindent
+\textbf{Hints:} useful list functions: \texttt{.contains(..)} checks
+whether an element is in a list, \texttt{.flatten} turns a list of
+lists into just a list, \texttt{\_::\_} puts an element on the head of
+the list, \texttt{.head} gives you the first element of a list (make
+sure the list is not \texttt{Nil}).
+
+\subsubsection*{Tasks (file knight2.scala)}
+
+\begin{itemize}
+\item[(2a)] Implement a \texttt{first}-function. This function takes a list of
+  positions and a function $f$ as arguments; $f$ is the name we give to
+  this argument). The function $f$ takes a position as argument and
+  produces an optional path. So $f$'s type is \texttt{Pos =>
+    Option[Path]}. The idea behind the \texttt{first}-function is as follows:
+
+  \[
+  \begin{array}{lcl}
+  \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\  
+  \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
+    f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
+    \textit{first}(xs, f) & \textit{otherwise}\\
+                              \end{cases}
+  \end{array}
+  \]
+
+  \noindent That is, we want to find the first position where the
+  result of $f$ is not \texttt{None}, if there is one. Note that
+  `inside' \texttt{first}, you do not (need to) know anything about
+  the argument $f$ except its type, namely \texttt{Pos =>
+    Option[Path]}. There is one additional point however you should
+  take into account when implementing \texttt{first}: you will need to
+  calculate what the result of $f(x)$ is; your code should do this
+  only \textbf{once} and for as \textbf{few} elements in the list as
+  possible! Do not calculate $f(x)$ for all elements and then see which 
+  is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
+  
+\item[(2b)] Implement a \texttt{first\_tour} function that uses the
+  \texttt{first}-function from (2a), and searches recursively for a tour.
+  As there might not be such a tour at all, the \texttt{first\_tour} function
+  needs to return a value of type
+  \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]
+\end{itemize}
+
+\noindent
+\textbf{Testing:} The \texttt{first\_tour} function will be called with board
+sizes of up to $8 \times 8$.
+\bigskip
+
+\noindent
+\textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a
+list according to a boolean function; a useful option function:
+\texttt{.isDefined} returns true, if an option is \texttt{Some(..)};
+anonymous functions can be constructed using \texttt{(x:Int) => ...},
+this functions takes an \texttt{Int} as an argument.
+
+
+%%\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 even on small
+boards takes too much time. There is a heuristic, called \emph{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.
+
+\chessboard[maxfield=g7,
+            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+            text = \small 3, markfield=Z5,
+            text = \small 7, markfield=b5,
+            text = \small 7, markfield=c4,
+            text = \small 7, markfield=c2,
+            text = \small 5, markfield=b1,
+            text = \small 2, markfield=Z1,
+            setpieces={Na3}]
+
+\noindent
+Warnsdorf's Rule states that the moves on the board above should be
+tried in the order
+
+\[
+(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
+\]
+
+\noindent
+Whenever there are ties, the corresponding onward moves can be in any
+order.  When calculating the number of onward moves for each field, we
+do not count moves that revisit any field already visited.
+
+\subsubsection*{Tasks (file knight3.scala)}
+
+\begin{itemize}
+\item[(3a)] Write a function \texttt{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). \hfill[1 Mark]
+  
+\item[(3b)] Implement a \texttt{first\_closed-tour\_heuristic}
+  function that searches for a
+  \textbf{closed} tour on a $6\times 6$ board. It should use the
+  \texttt{first}-function from (2a) and tries out onward moves according to
+  the \texttt{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)$). \hfill[1 Mark]
+
+\item[(3c)] Implement a \texttt{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 function of the \texttt{first\_tour\_heuristic} function
+  otherwise you will get problems with stack-overflows.\\
+  \mbox{}\hfill[1 Mark]
+\end{itemize}  
+\bigskip
+
+\noindent
+\textbf{Hints:} a useful list function: \texttt{.sortBy} sorts a list
+according to a component given by the function; a function can be
+tested to be tail recursive by annotation \texttt{@tailrec}, which is
+made available by importing \texttt{scala.annotation.tailrec}.
+
+
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: