pep-material: comparison cws/cw02.tex

equal deleted inserted replaced

-:fdc2c6fb7a24
+:9891c9fac37e
 \mbox{}\\[-18mm]\mbox{}
 \section*{Coursework 7 (Scala, Knight's Tour)}
-This coursework is about searching and backtracking, and worth
+This coursework is worth 10\%. It is about searching and
-10\%. The first part is due on 23 November at 11pm; the second, more
+backtracking. The first part is due on 23 November at 11pm; the
-advanced part, is due on 30 November at 11pm. You are asked to
+second, more advanced part, is due on 30 November at 11pm. You are
-implement Scala programs that solve various versions of the
+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}
 It should be understood that the work you submit represents
 your own effort. You have not copied from anyone else. An
 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 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},
 text = \small 10, markfield=Z5,
 text = \small  5, markfield=a5,
 markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
 color=red!50,
 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
+take the dimension of the board as an argument.  The fun with this
-even for small chessbord dimensions it has already an incredably large
+problem is that even for small chessbord dimensions it has already an
-search space---finding a tour is like finding a needle in a
+incredably large search space---finding a tour is like finding a
-haystack. In the first task we want to see far we get with
+needle in a haystack. In the first task we want to see how far we get
-exhaustively exploring the complete search space for small
+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 boyond board sizes of
 \subsubsection*{Tasks (file knight1.scala)}
 \begin{itemize}
-\item[(1a)] Implement a is-legal-move function that takes a dimension, a path
+\item[(1a)] Implement an is-legal-move function that takes a
-and a position as argument and tests whether the position is inside
+dimension, a path and a position as argument and tests whether the
-the board and not yet element in the path. \hfill[1 Mark]
+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
 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 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
+If the board is not empty, then maybe some of the moves need to be
-moves need to be filtered out from this list.  For a knight on field
+filtered out from this list.  For a knight on field $(7, 7)$ and an
-$(7, 7)$ and an empty board, the legal moves are
+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 (count-tours and
 enum-tours). They each take a dimension and a path as
-arguments. They exhaustively search for \underline{\bf open} tours
+arguments. They exhaustively search for {\bf open} tours starting
-starting from the given path. The first function counts all possible
+from the given path. The first function counts all possible open
-open tours (there can be none for certain board sizes) and the second
+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
+will be called with board sizes up to $5 \times 5$. If you search
-for open tours on $5 \times 5$ board starting from field $(0, 0)$,
+for open tours on a $5 \times 5$ board starting only from field $(0, 0)$,
-there are 304 of them. If you try out every field of a $5 \times
+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
 $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
 19591828170979904, respectively.}
 \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
+position as argument and produces an optional path. So its type is
-the first-function is as follows:
+\texttt{Pos => Option[Path]}. The idea behind the first-function is
+as follows:
 \[
 \begin{array}{lcl}
 \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\
 \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
 \end{cases}
 \end{array}
 \]
 \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
+\item[(2b)] Implement a first-tour function that uses the
-from (2a), search recursively for an open tour.  As there might not
+first-function from (2a), and searches recursively for an open tour.
-be such a tour at all, the first-tour function needs to return an
+As there might not be such a tour at all, the first-tour function
-\texttt{Option[Path]}.\hfill[2 Marks]
+needs to return an \texttt{Option[Path]}.\hfill[2 Marks]
 \end{itemize}
 \noindent
 \textbf{Testing} The first tour function will be called with board
 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
+that can speed up finding a tour. This heuristic states that a knight
-is moved so that it always proceeds to the square from which the
+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,
 text = \small 2, markfield=Z1,
 setpieces={Na3}]
 \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)
 \]
 do not count moves that revisit any field already visited.
 \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
-\item[(3b)] first-closed tour heuristics; up to $6\times 6$
+Warnsdorf’s rule. That means moves with the fewest legal onward moves
+should come first (in order to be tried out first).
-\item[(3c)] first tour heuristics; up to $50\times 50$
+\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[(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}
 %%% Local Variables:

changeset 50	9891c9fac37e
parent 48	7a6a75ea9738
child 59	8e866d0af03a