pep-material: comparison cws/cw02.tex

equal deleted inserted replaced

-:48d2cbe8ee5e
+:7a6a75ea9738
 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
+5$ board. But there are on a $6\times 6$ board and bigger, for example
 \chessboard[maxfield=e5,
 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
 text = \small 10, markfield=Z5,
 text = \small  5, markfield=a5,
 \noindent
 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
+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) and another on $(7, 7)$ (red):
+field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
 \chessboard[maxfield=g7,
 color=blue!50,
 linewidth=0.2em,
 markfields={f5, e6},
 setpieces={Ng7, Nb2}]
 \subsection*{Part 1 (6 Marks)}
-We will implement the knight's tour problem such that we can change
+You are asked to implement the knight's tour problem such that the
-quickly the dimension of the chessboard. The fun with this problem is
+dimension of the board can be changed.  Therefore most functions will
-that even for small chessbord dimensions it has already an incredably
+take the dimension as an argument.  The fun with this problem is that
-large search space---finding a tour is like finding a needle in a
+even for small chessbord dimensions it has already an incredably large
-haystack. In the first part we want to see far we get with
+search space---finding a tour is like finding a needle in a
-exhaustively exploring the complete search space for small dimensions.
+haystack. In the first task we want to see far we get with
+exhaustively exploring the complete search space for small
-Let us first fix the basic datastructures for the implementation.  A
+chessboards.\medskip
-\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
+\noindent
-should be the last element in this list; and the last move is the
+Let us first fix the basic datastructures for the implementation.  The
-first element. For example the path for the $5\times 5$ chessboard
+board dimension is an integer (we will never go boyond board sizes of
-above is represented by
+$100 \times 100$).  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}$, ..., (3, 2), $\underbrace{\texttt{(4, 4)}}_0$)}
+$\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
 \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.
+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 follow-on moves. If the follow-on moves are
+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 follow-on
+empty board, the legal-moves function should produce the onward
 positions
 \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.
+in this order.  If the board is not empty, then maybe some of the
-For a knight on field $(7, 7)$ and an empty board, the legal moves
+moves need to be filtered out from this list.  For a knight on field
-are
+$(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 (count-tours and
 enum-tours). They each take a dimension and a path as
-arguments. They exhaustively search for \underline{open} tours
+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
-collects all open tours in a list of paths.
+collects all open tours in a list of paths.\hfill[2 Marks]
 \end{itemize}
-\noindent \textbf{Test data:} For the marking, these functions will be
+\noindent \textbf{Test data:} For the marking, the functions in (1c)
-called with board sizes up to $5 \times 5$. If you only search for
+will be called with board sizes up to $5 \times 5$. If you only search
-open tours starting from field $(0, 0)$, there are 304 of them. If you
+for open tours on $5 \times 5$ board starting from field $(0, 0)$,
-try out every field of a $5 \times 5$-board as a starting field and
+there are 304 of them. If you try out every field of a $5 \times
-add up all open tours, you obtain 1728. A $6\times 6$ board is already
+5$-board as a starting field and add up all open tours, you obtain
-too large to search exhaustively: the number of open tours on
+1728. A $6\times 6$ board is already too large to be searched
-$6\times 6$, $7\times 7$ and $8\times 8$ are
+exhaustively.\footnote{For your interest, the number of open tours on
+$6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
-\begin{center}
+19591828170979904, respectively.}
-\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
 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}\\
+\textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\
-first(x\!::\!xs, f) & \dn & \begin{cases}
+\textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
 f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
-first(xs, f) & \textit{otherwise}\\
+\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}.\newline\mbox{}\hfill[1 Mark]
 \item[(2b)] Implement a first-tour function. Using the first-function
-from (2a), search recursively for an open tour. Only use the field
+from (2a), search recursively for an open tour.  As there might not
-$(0, 0)$ as a starting field of the tour. As there might not be such
+be such a tour at all, the first-tour function needs to return an
-a tour at all, the first-tour function needs to return an
+\texttt{Option[Path]}.\hfill[2 Marks]
-\texttt{Option[Path]}. For the marking, this function will be called
+\end{itemize}
-with board sizes up to $8 \times 8$.
-\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)}
-For open tours beyond $8 \times 8$ boards and also for searching for
+As you should have seen in Part 1, a naive search for open tours
-closed tours, an heuristic (called Warnsdorf's rule) needs to be
+beyond $8 \times 8$ boards and also for searching for closed tours
-implemented. This rule states that a knight is moved so that it
+takes too much time. There is a heuristic (called Warnsdorf's rule)
-always proceeds to the square from which the knight will have the
+that can speed up finding a tour. This heuristice states that a knight
-fewest onward moves.  For example for a knight on field $(1, 3)$,
+is moved so that it always proceeds to the square from which the
-the field $(0, 1)$ has the fewest possible onward moves.
+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 5, markfield=b1,
 text = \small 2, markfield=Z1,
 setpieces={Na3}]
 \noindent
-Warnsdorf's rule states that the moves sould be tried out in the
+Warnsdorf's rule states that the moves on the board above sould be
-order
+tried out in the order
 \[
 (0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
 \]

changeset 48	7a6a75ea9738
parent 46	48d2cbe8ee5e
child 50	9891c9fac37e