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 - <>}. + <>}.\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}