% !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*{Part 8 (Scala)}+ −
+ −
\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 is+ −
due on \cwEIGHT{} at 4pm; the core part is due on \cwEIGHTa{} at 4pm.+ −
Note the core, more advanced, part might include material you have not+ −
yet seen in the first three lectures. \bigskip+ −
+ −
\IMPORTANT{}+ −
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{CW8a}, \texttt{CW8b} and \texttt{CW8c}.+ −
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> CW8a.enum_tours(5, List((0, 0))).length+ −
Time needed: 1.722 secs.+ −
res0: Int = 304+ −
+ −
scala> CW8a.print_board(8, CW8a.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 heuristic, called \emph{Warnsdorf's+ −
Rule} that can speed up finding a tour. This heuristic 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\_heuristic}+ −
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\_heuristic} 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\_heuristic} 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> CW8c.tour_on_mega_board(70, List((0, 0)))+ −
Time needed: 9.484 secs.+ −
...<<long_list>>...+ −
\end{lstlisting}%$+ −
+ −
\mbox{}\hfill[1 Mark]+ −
\end{itemize} + −
\bigskip+ −
+ −
+ −
+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −