\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)}

\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

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