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

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: