
diff -r 9cfa37c91444 -r 8399976b77fe cws/cw02.tex
--- a/cws/cw02.tex	Sun Nov 13 17:14:29 2016 +0000
+++ b/cws/cw02.tex	Mon Nov 14 03:25:14 2016 +0000
@@ -6,16 +6,17 @@
 \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 about depth-first search in Scala and worth
+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
@@ -28,94 +29,269 @@
 It should be understood that the work you submit represents
 your own effort. You have not copied from anyone else. An
 exception is the Scala code I showed during the lectures or
-uploaded to KEATS, which you can freely use.\bigskip
+uploaded to KEATS, which you can freely use.\medskip
 
 \subsection*{Background}
 
 The \textit{Knight's Tour Problem} is about finding a tour such that
-the knight visits every field on a $n\times n$ chessboard once and
-only once. For example on a $5\times 5$ chessboard, a knight's tour is
-as follows:
+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 (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, for example
 
 \chessboard[maxfield=e5, 
             pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
-            text = \bf\small 24, markfield=a5,
-            text = \small 11, markfield=b5,
-            text = \small  6, markfield=c5,
-            text = \small 17, markfield=d5,
-            text = \small  0, markfield=e5,
-            text = \small 19, markfield=a4,
-            text = \small 16, markfield=b4,
-            text = \small 23, markfield=c4,
-            text = \small 12, markfield=d4,
-            text = \small  7, markfield=e4,
-            text = \small 10, markfield=a3,
-            text = \small  5, markfield=b3,
-            text = \small 18, markfield=c3,
-            text = \small  1, markfield=d3,
-            text = \small 22, markfield=e3,
-            text = \small 15, markfield=a2,
-            text = \small 20, markfield=b2,
-            text = \small  3, markfield=c2,
-            text = \small  8, markfield=d2,
-            text = \small 13, markfield=e2,
-            text = \small  4, markfield=a1,
-            text = \small  9, markfield=b1,
-            text = \small 14, markfield=c1,
-            text = \small 21, markfield=d1,
-            text = \small  2, markfield=e1
+            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
-The tour starts in the right-upper corner, then moves to field $(4,3)$,
-then $(5,1)$ 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.
+where the 35th move can join up again with the 0th move.
+
+If you cannot remember how a knight moved in chess, or never played
+chess, below are all potential moves indicated for two knights, one on
+field $(2, 2)$ (blue) and another on $(7, 7)$ (red):
 
 
-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 step on field $(1, 5)$ is not within the reach
-of the first step on $(5, 5)$. 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.\bigskip
-
-\noindent
-If you cannot remember how a knight moved in chess, or never played
-chess, below are all potential moves indicated for two knights, one on
-field $(3, 3)$ and another on $(8, 8)$:
-
-
-\chessboard[color=blue!50,
+\chessboard[maxfield=g7,
+            color=blue!50,
             linewidth=0.2em,
             shortenstart=0.5ex,
             shortenend=0.5ex,
             markstyle=cross,
-            markfields={b5, d5, a4, e4, a2, e2, b1, d1},
+            markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
             color=red!50,
-            markfields={g6, f7},
-            setpieces={Nh8, Nc3}]
+            markfields={f5, e6},
+            setpieces={Ng7, Nb2}]
+
+\subsection*{Part 1 (6 Marks)}
+
+We will implement the knight's tour problem such that we can change
+quickly the dimension of the chessboard. 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 part we want to see far we get with
+exhaustively exploring the complete search space for small dimensions.
 
+Let us first fix the basic datastructures for the implementation.  A
+\emph{position} (or field) on the chessboard is a pair of integers. A
+\emph{path} is a list of positions. The first (or 0th move) in a path
+should be the last element in this list; and the last move 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}$, ..., (3, 2), $\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*{Task}
+\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.
+
+\item[(1b)] Implement a legal-moves function that calculates for a
+  position all legal follow-on moves. If the follow-on moves are
+  placed on a circle, you should produce them starting from
+  ``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 follow-on
+  positions
 
-The task is to implement a regular expression matcher based on
-derivatives of regular expressions. The implementation should
-be able to deal with the usual (basic) regular expressions
+  \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}  
+
+\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{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.
+\end{itemize}
 
-\noindent {\bf Important!} Your implementation should have
-explicit cases for the basic regular expressions, but also
-explicit cases for the extended regular expressions. That
-means do not treat the extended regular expressions by just
-translating them into the basic ones. See also Question 2,
-where you are asked to explicitly give the rules for
-\textit{nullable} and \textit{der} for the extended regular
-expressions.
+\noindent \textbf{Test data:} For the marking, these functions will be
+called with board sizes up to $5 \times 5$. If you only search for
+open tours starting from field $(0, 0)$, there are 304 of them. 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 search exhaustively: the number of open tours on
+$6\times 6$, $7\times 7$ and $8\times 8$ are
+
+\begin{center}
+\begin{tabular}{ll}  
+  $6\times 6$ & 6637920\\
+  $7\times 7$ & 165575218320\\
+  $8\times 8$ & 19591828170979904
+\end{tabular}
+\end{center}
+
+\subsubsection*{Tasks (file knight2.scala)}
+
+\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:
+
+  \[
+  \begin{array}{lcl}
+  first(\texttt{Nil}, f) & \dn & \texttt{None}\\  
+  first(x\!::\!xs, f) & \dn & \begin{cases}
+    f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
+    first(xs, f) & \textit{otherwise}\\
+                              \end{cases}
+  \end{array}
+  \]
+
+\item[(2b)] Implement a first-tour function. Using the first-function
+  from (2a), search recursively for an open tour. Only use the field
+  $(0, 0)$ as a starting field of the tour. As there might not be such
+  a tour at all, the first-tour function needs to return an
+  \texttt{Option[Path]}. For the marking, this function will be called
+  with board sizes up to $8 \times 8$.
+\end{itemize}  
 
 
+\subsection*{Part 2 (4 Marks)}
+
+For open tours beyond $8 \times 8$ boards and also for searching for
+closed tours, an heuristic (called Warnsdorf's rule) needs to be
+implemented. This rule states that a knight is moved so that it
+always proceeds to the square from which the knight will have the
+fewest onward moves.  For example for a knight on field $(1, 3)$,
+the field $(0, 1)$ has the fewest possible onward moves.
+
+\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 sould be tried out in the
+order
+
+\[
+(0, 1), (0, 5), (2, 5), (3, 4), (3, 2)
+\]
+
+Whenever there are ties, the correspoding 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)] orderered-moves
+
+\item[(3b)] first-closed tour heuristics; up to $6\times 6$
+
+\item[(3c)] first tour heuristics; up to $50\times 50$
+\end{itemize}  
 
 \end{document}
 




