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}