\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 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.
 
\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. 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: