diff -r 663c2a9108d1 -r 4de31fdc0d67 cws/main_cw04.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cws/main_cw04.tex Mon Nov 02 02:31:44 2020 +0000 @@ -0,0 +1,447 @@ +% !TEX program = xelatex +\documentclass{article} +\usepackage{chessboard} +\usepackage[LSBC4,T1]{fontenc} +\let\clipbox\relax +\usepackage{../style} +\usepackage{../langs} +\usepackage{disclaimer} + +\begin{document} + +\setchessboard{smallboard, + zero, + showmover=false, + boardfontencoding=LSBC4, + hlabelformat=\arabic{ranklabel}, + vlabelformat=\arabic{filelabel}} + +\mbox{}\\[-18mm]\mbox{} + +\section*{Preliminary and Core Part 9 (Scala, 4 + 6 Marks)} + +\mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\ +\mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\ +\mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\ +\mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\medskip\bigskip + +\noindent +This part is about searching and backtracking. You are asked to +implement Scala programs that solve various versions of the +\textit{Knight's Tour Problem} on a chessboard. The preliminary part (4\%) is +due on \cwNINE{} at 5pm; the core part (6\%) is due on \cwNINEa{} at 5pm.\bigskip +%Note the core, more advanced, part might include material you have not +%yet seen in the first three lectures. \bigskip + +\IMPORTANTNONE{} + +\noindent +Also note that the running time of each part will be restricted to a +maximum of 30 seconds on my laptop: If you calculate a result once, +try to avoid to calculate the result again. Feel free to copy any code +you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and +\texttt{knight3.scala}. + +\DISCLAIMER{} + +\subsection*{Background} + +The \textit{Knight's Tour Problem} is about finding a tour such that +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 +This 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 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 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, + 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 +where the 35th move can join up again with the 0th move. + +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 moves) and another on $(7, 7)$ (red moves): + +{\chessboard[maxfield=g7, + color=blue!50, + linewidth=0.2em, + shortenstart=0.5ex, + shortenend=0.5ex, + markstyle=cross, + markfields={a4, c4, Z3, d3, Z1, d1, a0, c0}, + color=red!50, + markfields={f5, e6}, + setpieces={Ng7, Nb2}, + boardfontsize=12pt,labelfontsize=9pt]} + +\subsection*{Reference Implementation} + +This Scala part comes with three reference implementations in form of +\texttt{jar}-files. This allows you to run any test cases on your own +computer. For example you can call Scala on the command line with the +option \texttt{-cp knight1.jar} and then query any function from the +\texttt{knight1.scala} template file. As usual you have to +prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}. +Since some of the calls are time sensitive, I included some timing +information. For example + +\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scala -cp knight1.jar +scala> CW9a.enum_tours(5, List((0, 0))).length +Time needed: 1.722 secs. +res0: Int = 304 + +scala> CW9a.print_board(8, CW9a.first_tour(8, List((0, 0))).get) +Time needed: 15.411 secs. + + 51 46 55 44 53 4 21 12 + 56 43 52 3 22 13 24 5 + 47 50 45 54 25 20 11 14 + 42 57 2 49 40 23 6 19 + 35 48 41 26 61 10 15 28 + 58 1 36 39 32 27 18 7 + 37 34 31 60 9 62 29 16 + 0 59 38 33 30 17 8 63 +\end{lstlisting}%$ + + +\subsection*{Hints} + +\noindent +\textbf{Preliminary Part} useful list functions: \texttt{.contains(..)} checks +whether an element is in a list, \texttt{.flatten} turns a list of +lists into just a list, \texttt{\_::\_} puts an element on the head of +the list, \texttt{.head} gives you the first element of a list (make +sure the list is not \texttt{Nil}); a useful option function: +\texttt{.isDefined} returns true, if an option is \texttt{Some(..)}; +anonymous functions can be constructed using \texttt{(x:Int) => ...}, +this function takes an \texttt{Int} as an argument.\medskip + + +\noindent +\textbf{Core Part} a useful list function: \texttt{.sortBy} sorts a list +according to a component given by the function; a function can be +tested to be tail-recursive by annotation \texttt{@tailrec}, which is +made available by importing \texttt{scala.annotation.tailrec}.\medskip + + + + +\subsection*{Preliminary Part (4 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 of the board as an argument. The fun with this +problem is that even for small chessboard dimensions it has already an +incredibly 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 +Let us first fix the basic datastructures for the implementation. The +board dimension is an integer. +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}$, ..., + $\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 +occurs only once in the path, and each move follows the rules of how a +knight moves (see above for the rules). + + +\subsubsection*{Tasks (file knight1.scala)} + +\begin{itemize} +\item[(1)] Implement an \texttt{is\_legal} function that takes a + dimension, a path and a position as arguments and tests whether the + position is inside the board and not yet element in the + path. \hfill[1 Mark] + +\item[(2)] Implement a \texttt{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-o'clock'' following in clockwise order. For example on an + $8\times 8$ board for a knight at position $(2, 2)$ and otherwise + empty board, the legal-moves function should produce the onward + 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} + + 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} + \mbox{}\hfill[1 Mark] + +\item[(3)] Implement two recursive functions (\texttt{count\_tours} and + \texttt{enum\_tours}). They each take a dimension and a path as + arguments. They exhaustively search for tours starting + from the given path. The first function counts all possible + tours (there can be none for certain board sizes) and the second + collects all tours in a list of paths. These functions will be + called with a path containing a single position---the starting field. + They are expected to extend this path so as to find all tours starting + from the given position.\\ + \mbox{}\hfill[2 Marks] +\end{itemize} + +\noindent \textbf{Test data:} For the marking, the functions in (3) +will be called with board sizes up to $5 \times 5$. If you search +for 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 tours, you obtain +1728. A $6\times 6$ board is already too large to be searched +exhaustively.\footnote{For your interest, the number of tours on + $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320, + 19591828170979904, respectively.}\smallskip + + +\subsection*{Core Part (6 Marks)} + + +\subsubsection*{Tasks (file knight1.scala cont.)} + +\begin{itemize} +\item[(4)] Implement a \texttt{first}-function. This function takes a list of + positions and a function $f$ as arguments; $f$ is the name we give to + this argument). The function $f$ takes a position as argument and + produces an optional path. So $f$'s type is \texttt{Pos => + Option[Path]}. The idea behind the \texttt{first}-function is as follows: + + \[ + \begin{array}{lcl} + \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}\\ + \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}, if there is one. Note that + `inside' \texttt{first}, you do not (need to) know anything about + the argument $f$ except its type, namely \texttt{Pos => + Option[Path]}. If you want to find out what the result of $f$ is + on a particular argument, say $x$, you can just write $f(x)$. + There is one additional point however you should + take into account when implementing \texttt{first}: you will need to + calculate what the result of $f(x)$ is; your code should do this + only \textbf{once} and for as \textbf{few} elements in the list as + possible! Do not calculate $f(x)$ for all elements and then see which + is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark] + +\item[(5)] Implement a \texttt{first\_tour} function that uses the + \texttt{first}-function from (4), and searches recursively for single tour. + As there might not be such a tour at all, the \texttt{first\_tour} function + needs to return a value of type + \texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark] +\end{itemize} + +\noindent +\textbf{Testing:} The \texttt{first\_tour} function will be called with board +sizes of up to $8 \times 8$. +\bigskip + +%%\newpage + +\noindent +As you should have seen in the earlier parts, a naive search for tours beyond +$8 \times 8$ boards and also searching for closed tours even on small +boards takes too much time. There is a heuristics, called \emph{Warnsdorf's +Rule} that can speed up finding a tour. This heuristics 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. + +\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 on the board above should be +tried in the order + +\[ +(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2) +\] + +\noindent +Whenever there are ties, the corresponding 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 knight2.scala)} + +\begin{itemize} +\item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of + onward moves like in (2) but orders them according to + Warnsdorf’s Rule. That means moves with the fewest legal onward moves + should come first (in order to be tried out first). \hfill[1 Mark] + +\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristics} + function that searches for a single + \textbf{closed} tour on a $6\times 6$ board. It should try out + onward moves according to + the \texttt{ordered\_moves} function from (6). It is more likely to find + a solution when started in the middle of the board (that is + position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] + +\item[(8)] Implement a \texttt{first\_tour\_heuristics} function + for boards up to + $30\times 30$. It is the same function as in (7) but searches for + tours (not just closed tours). It might be called with any field on the + board as starting field.\\ + %You have to be careful to write a + %tail-recursive function of the \texttt{first\_tour\_heuristics} function + %otherwise you will get problems with stack-overflows.\\ + \mbox{}\hfill[1 Mark] +\end{itemize} + +\subsubsection*{Task (file knight3.scala)} +\begin{itemize} +\item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is + the same function as in (8), \textbf{but} should be able to + deal with boards up to + $70\times 70$ \textbf{within 30 seconds} (on my laptop). This will be tested + by starting from field $(0, 0)$. You have to be careful to + write a tail-recursive function otherwise you will get problems + with stack-overflows. Please observe the requirements about + the submissions: no tricks involving \textbf{.par}.\medskip + + The timelimit of 30 seconds is with respect to the laptop on which the + marking will happen. You can roughly estimate how well your + implementation performs by running \texttt{knight3.jar} on your + computer. For example the reference implementation shows + on my laptop: + + \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scala -cp knight3.jar + +scala> CW9c.tour_on_mega_board(70, List((0, 0))) +Time needed: 9.484 secs. +...<>... +\end{lstlisting}%$ + + \mbox{}\hfill[1 Mark] +\end{itemize} +\bigskip + + + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: