\documentclass{article}+
−
\usepackage{chessboard}+
−
\usepackage[LSBC4,T1]{fontenc}+
−
\usepackage{../style}+
−
+
−
\begin{document}+
−
+
−
\setchessboard{smallboard,+
−
               showmover=false,+
−
               boardfontencoding=LSBC4,+
−
               hlabelformat=\arabic{ranklabel},+
−
               vlabelformat=\arabic{filelabel}}+
−
+
−
+
−
+
−
\section*{Coursework 7 (Scala, Knight's Tour)}+
−
+
−
This coursework is about depth-first search in Scala 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+
−
\textit{Knight's Tour Problem} on a chessboard. Make sure the files+
−
you submit can be processed by just calling \texttt{scala+
−
  <<filename.scala>>}.+
−
 +
−
\subsection*{Disclaimer}+
−
+
−
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+
−
+
−
\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:+
−
+
−
+
−
\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+
−
           ]+
−
+
−
\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.+
−
+
−
+
−
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,+
−
            linewidth=0.2em,+
−
            shortenstart=0.5ex,+
−
            shortenend=0.5ex,+
−
            markstyle=cross,+
−
            markfields={b5, d5, a4, e4, a2, e2, b1, d1},+
−
            color=red!50,+
−
            markfields={g6, f7},+
−
            setpieces={Nh8, Nc3}]+
−
+
−
+
−
+
−
+
−
\subsubsection*{Task}+
−
+
−
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+
−
+
−
\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.+
−
+
−
+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−