\documentclass{article}+
−
\usepackage{../style}+
−
\usepackage{chessboard}+
−
\usepackage[LSBC4,T1]{fontenc}+
−
+
−
+
−
\begin{document}+
−
+
−
\setchessboard{smallboard,+
−
               showmover=false,+
−
               boardfontencoding=LSBC4,+
−
               hlabelformat=\arabic{ranklabel},+
−
               vlabelformat=\arabic{filelabel}}+
−
+
−
+
−
+
−
\section*{Coursework 7 (Scala, Knight's Tour)}+
−
+
−
This coursework is worth XXX\% and is due on 21 November at 16:00. You+
−
are asked to implement a Scala program that solves the \textit{knight's+
−
  tour problem} on an $n\times n$ chessboard. This problem is about+
−
finding a tour such that the knight visits every field on the+
−
chessboard once. One 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 left-upper corner, then moves to field $(4,3)$,+
−
then $(5,1)$ and so on. 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 not closed (that is 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 is one on a $6\times+
−
6$ board.+
−
+
−
If you cannot remember how a knight moved in 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*{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+
−
+
−
+
−
\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: +
−