\documentclass{article}\usepackage{chessboard}\usepackage[LSBC4,T1]{fontenc}\usepackage{../style}\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 worth 10\%. It is about searching andbacktracking. The first part is due on 23 November at 11pm; thesecond, more advanced part, is due on 30 November at 11pm. You areasked to implement Scala programs that solve various versions of the\textit{Knight's Tour Problem} on a chessboard. Make sure the filesyou submit can be processed by just calling \texttt{scala <<filename.scala>>}.\bigskip\noindent\textbf{Important:} Do not use any mutable data structures in yoursubmissions! They are not needed. This excludes the use of\texttt{ListBuffer}s, for example. Do not use \texttt{return} in yourcode! It has a different meaning in Scala, than in Java.Do not use \texttt{var}! This declares a mutable variable. Feel free tocopy any code you need from files \texttt{knight1.scala},\texttt{knight2.scala} and \texttt{knight3.scala}. Make sure thefunctions you submit are defined on the ``top-level'' of Scala, notinside a class or object.\subsection*{Disclaimer}It should be understood that the work you submit representsyour own effort. You have not copied from anyone else. Anexception is the Scala code I showed during the lectures oruploaded to KEATS, which you can freely use.\medskip\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. Sucha tour is called \emph{open} tour. For example on a $5\times 5$chessboard, an open 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 ]\noindentThe 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 (it is open) 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}]\subsection*{Part 1 (7 Marks)}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 (we will never go beyond board sizes of$50 \times 50$). 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*{Tasks (file knight1.scala)}\begin{itemize}\item[(1a)] Implement an 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. \hfill[1 Mark]\item[(1b)] Implement a 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-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 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[(1c)] Implement two recursive functions (count-tours and enum-tours). They each take a dimension and a path as arguments. They exhaustively search for {\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.\hfill[2 Marks]\end{itemize}\noindent \textbf{Test data:} For the marking, the functions in (1c)will be called with board sizes up to $5 \times 5$. If you searchfor open 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 open tours, you obtain1728. A $6\times 6$ board is already too large to be searchedexhaustively.\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)}\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. So $f$'s type is \texttt{Pos => Option[Path]}. The idea behind the 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.\mbox{}\hfill[1 Mark]\item[(2b)] Implement a first-tour function that uses the first-function from (2a), and searches 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 boardsizes of up to $8 \times 8$. \subsection*{Part 2 (3 Marks)}As you should have seen in Part 1, a naive search for open toursbeyond $8 \times 8$ boards and also searching for closed tourstakes too much time. There is a heuristic (called Warnsdorf's rule)that can speed up finding a tour. This heuristic states that a knightis 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.\subsubsection*{Tasks (file knight3.scala)}\begin{itemize}\item[(3a)] Write a function ordered-moves that calculates a list of onward moves like in (1b) but orders them according to the Warnsdorf’s rule. That means moves with the fewest legal onward moves should come first (in order to be tried out first).\item[(3b)] Implement a first-closed-tour-heuristic function that searches for a \textbf{closed} tour on a $6\times 6$ board. It should use the first-function from (2a) and tries out onward moves according to the ordered-moves function from (3a). It is more likely to find a solution when started in the middle of the board (that is position $(dimension / 2, dimension / 2)$).\item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. It is the same function as in (3b) but searches for \textbf{open} tours. You have to be careful to write a tail-recursive version of the first-tour-heuristic function otherwise you will get problems with stack-overflows.\end{itemize} \end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: