% !TEX program = xelatex\documentclass{article}\usepackage{chessboard}\usepackage[LSBC4,T1]{fontenc}\let\clipbox\relax\usepackage{../styles/style}\usepackage{../styles/langs}\usepackage{disclaimer}\usepackage{ulem}\begin{document}\setchessboard{smallboard, zero, showmover=false, boardfontencoding=LSBC4, hlabelformat=\arabic{ranklabel}, vlabelformat=\arabic{filelabel}}\mbox{}\\[-18mm]\mbox{}\section*{Main Part 4 (Scala, 11 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\noindentThis part is about searching and backtracking. You are asked toimplement Scala programs that solve various versions of the\textit{Knight's Tour Problem} on a chessboard.\medskip % Note the core, more advanced, part might include material you have not%yet seen in the first three lectures. \bigskip\IMPORTANTNONE{}\noindentAlso note that the running time of each part will be restricted to amaximum 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 codeyou 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 thatthe knight visits every field on an $n\times n$ chessboard once. Forexample 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 ]\noindentThis 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 everybigger board there is. A knight's tour is called \emph{closed}, if the last step in the touris within a knight's move to the beginning of the tour. So the aboveknight's tour is \underline{not} closed because the laststep 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\times5$ board. But there are on a $6\times 6$ board and on bigger ones, forexample\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 ]\noindentwhere the 35th move can join up again with the 0th move.If you cannot remember how a knight moves in chess, or never playedchess, below are all potential moves indicated for two knights, one onfield $(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}%\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from K%EATS. The one%supplied with github does not contain the correct code. See Scala coursework%section on KEATS.}\medskip\noindentThis Scala part comes with three reference implementations in form of\texttt{jar}-files. This allows you to run any test cases on your owncomputer. For example you can call Scala on the command line with theoption \texttt{-cp knight1.jar} and then query any function from the\texttt{knight1.scala} template file. As usual you have toprefix the calls with \texttt{M4a}, \texttt{M4b}, \texttt{M4c} and \texttt{M4d}.Since some of the calls are time sensitive, I included some timinginformation. For example\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]$ scala -cp knight1.jarscala> M4a.enum_tours(5, List((0, 0))).lengthTime needed: 1.722 secs.res0: Int = 304scala> M4a.print_board(8, M4a.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}\noindentUseful list functions: \texttt{.contains(..)} checkswhether an element is in a list, \texttt{.flatten} turns a list oflists into just a list, \texttt{\_::\_} puts an element on the head ofthe list, \texttt{.head} gives you the first element of a list (makesure 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; a useful list function: \texttt{.sortBy} sorts a listaccording to a component given by the function; a function can betested to be tail-recursive by annotation \texttt{@tailrec}, which ismade available by importing \texttt{scala.annotation.tailrec}.\medskip%%\newpage\subsection*{Tasks}You are asked to implement the knight's tour problem such that thedimension of the board can be changed. Therefore most functions willtake the dimension of the board as an argument. The fun with thisproblem is that even for small chessboard dimensions it has already anincredibly large search space---finding a tour is like finding aneedle in a haystack. In the first task we want to see how far we getwith exhaustively exploring the complete search space for smallchessboards.\medskip\noindentLet us first fix the basic datastructures for the implementation. Theboard dimension is an integer.A \emph{position} (or field) on the chessboard isa pair of integers, like $(0, 0)$. A \emph{path} is a list ofpositions. The first (or 0th move) in a path is the last element inthis list; and the last move in the path is the first element. Forexample the path for the $5\times 5$ chessboard above is representedby\[\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$, $\underbrace{\texttt{(2, 3)}}_{23}$, ..., $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}\]\noindentSuppose 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 elementoccurs only once in the path, and each move follows the rules of how aknight moves (see above for the rules).\subsubsection*{Task 1 (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[1 Mark]\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 searchfor 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 \times5$-board as a starting field and add up all tours, you obtain1728. A $6\times 6$ board is already too large to be searchedexhaustively.\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\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 boardsizes of up to $8 \times 8$.\bigskip%%\newpage\subsubsection*{Task 2 (file knight2.scala)}\noindentAs 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 smallboards takes too much time. There is a heuristics, called \emph{Warnsdorf'sRule} that can speed up finding a tour. This heuristics states that aknight is moved so that it always proceeds to the field from which theknight will have the \underline{fewest} onward moves. For example fora knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possibleonward 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}]\noindentWarnsdorf's Rule states that the moves on the board above should betried in the order\[(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)\]\noindentWhenever there are ties, the corresponding onward moves can be in anyorder. When calculating the number of onward moves for each field, wedo not count moves that revisit any field already visited.\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 3 (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.jarscala> M4c.tour_on_mega_board(70, List((0, 0)))Time needed: 9.484 secs....<<long_list>>...\end{lstlisting}%$ \mbox{}\hfill[1 Mark]\end{itemize}\subsubsection*{Task 4 (file knight4.scala)}\begin{itemize}\item[(10)] In this task we want to solve the problem of finding a single tour (if there exists one) on what is sometimes called ``mutilated'' chessboards, for example rectangular chessbords or chessboards where fields are missing. For this implement a search function \begin{center} \begin{tabular}{@{}l@{}} \texttt{def one\_tour\_pred(dim: Int, path: Path,}\\ \texttt{\phantom{def one\_tour\_pred(}n: Int, f: Pos => Boolean): Option[Path]} \end{tabular} \end{center} which has, like before, the dimension and current path as arguments, and in addtion it takes an integer, which specifies the length of the longest path (or length of the path after which the search should backtrack), and a function from positions to Booleans. This function acts as a predicate in order to restrict which onward legal moves should be considered in the search. The function \texttt{one\_tour\_pred} should return a single tour (\texttt{Some}-case), if one or more tours exist, and \texttt{None}, if no tour exists. For example when called with \begin{center} \texttt{one\_tour\_pred(7, List((0, 0)), 35, x => x.\_1 < 5)} \end{center} we are looking for a tour starting from position \texttt{(0,0)} on a 7 $\times$ 5 board, where the maximum length of the path is 35. The predicate \texttt{x => x.\_1 < 5} ensures that no position with an x-coordinate bigger than 4 is considered. One possible solution is \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] 0 13 22 33 28 11 20 23 32 1 12 21 34 27 14 7 16 29 2 19 10 31 24 5 8 17 26 3 6 15 30 25 4 9 18 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\end{lstlisting}%$where \texttt{print\_board} prints a \texttt{-1} for all fields thathave not been visited. \mbox{}\hfill[2 Marks]\end{itemize}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: