# HG changeset patch # User Christian Urban # Date 1479251289 0 # Node ID fdc2c6fb7a2469ee6fa66f8a03c6b0eeb9c9e4ea # Parent 70306f6c65b1530db51273ca9a05773fb5c2e6a8# Parent 7a6a75ea97381566e2ec413249497cdf4d1af19b merged diff -r 70306f6c65b1 -r fdc2c6fb7a24 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 70306f6c65b1 -r fdc2c6fb7a24 cws/cw02.tex --- a/cws/cw02.tex Tue Nov 15 23:04:52 2016 +0000 +++ b/cws/cw02.tex Tue Nov 15 23:08:09 2016 +0000 @@ -78,7 +78,7 @@ 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}, @@ -130,9 +130,9 @@ \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, @@ -148,23 +148,29 @@ \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. +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 +chessboards.\medskip -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 +\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 +$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 @@ -179,51 +185,46 @@ \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. - For a knight on field $(7, 7)$ and an empty board, the legal moves - are + 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 \begin{center} \texttt{List((6,5), (5,6))} - \end{center} + \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 -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} +\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 +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)} @@ -235,31 +236,38 @@ \[ \begin{array}{lcl} - first(\texttt{Nil}, f) & \dn & \texttt{None}\\ - first(x\!::\!xs, f) & \dn & \begin{cases} + \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}\\ - 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 - $(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} + 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] +\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 -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. +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 +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 +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}, @@ -272,8 +280,8 @@ setpieces={Na3}] \noindent -Warnsdorf's rule states that the moves sould be tried out in the -order +Warnsdorf's rule states that the moves on the board above sould be +tried out in the order \[ (0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)