1 \documentclass{article}

     2 \usepackage{../style}

     3 \usepackage{chessboard}

     4 \usepackage[LSBC4,T1]{fontenc}

     5 

     6 

     7 \begin{document}

     8 

     9 \setchessboard{smallboard,

    10                showmover=false,

    11                boardfontencoding=LSBC4,

    12                hlabelformat=\arabic{ranklabel},

    13                vlabelformat=\arabic{filelabel}}

    14 

    15 

    16 

    17 \section*{Coursework 2 (Knight's Tour)}

    18 

    19 This coursework is worth XXX\% and is due on 21 November at 16:00. You

    20 are asked to implement a Scala program that solves the \textit{knight's

    21   tour problem} on an $n\times n$ chessboard. This problem is about

    22 finding a tour such that the knight visits every field on the

    23 chessboard once. One a $5\times 5$ chessboard, a knight's tour

    24 is as follows:

    25 

    26 \chessboard[maxfield=e5, 

    27             pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},

    28             text = \bf\small 24, markfield=a5,

    29             text = \small 11, markfield=b5,

    30             text = \small  6, markfield=c5,

    31             text = \small 17, markfield=d5,

    32             text = \small  0, markfield=e5,

    33             text = \small 19, markfield=a4,

    34             text = \small 16, markfield=b4,

    35             text = \small 23, markfield=c4,

    36             text = \small 12, markfield=d4,

    37             text = \small  7, markfield=e4,

    38             text = \small 10, markfield=a3,

    39             text = \small  5, markfield=b3,

    40             text = \small 18, markfield=c3,

    41             text = \small  1, markfield=d3,

    42             text = \small 22, markfield=e3,

    43             text = \small 15, markfield=a2,

    44             text = \small 20, markfield=b2,

    45             text = \small  3, markfield=c2,

    46             text = \small  8, markfield=d2,

    47             text = \small 13, markfield=e2,

    48             text = \small  4, markfield=a1,

    49             text = \small  9, markfield=b1,

    50             text = \small 14, markfield=c1,

    51             text = \small 21, markfield=d1,

    52             text = \small  2, markfield=e1

    53            ]

    54 

    55 \noindent

    56 The tour starts in the left-upper corner, then moves to field $(4,3)$,

    57 then $(5,1)$ and so on. A knight's tour is called \emph{closed}, if

    58 the last step in the tour is within a knight's move to the beginning

    59 of the tour. So the above knight's tour is not closed (that is it is

    60 open) because the last step on field $(1, 5)$ is not within the reach

    61 of the first step on $(5, 5)$. It turns out there is no closed

    62 knight's tour on a $5\times 5$ board. But there is one on a $6\times

    63 6$ board.

    64 

    65 If you cannot remember how a knight moved in chess, below are all

    66 potential moves indicated for two knights, one on field $(3, 3)$ and

    67 another on $(8, 8)$:

    68 

    69 

    70 \chessboard[color=blue!50,

    71             linewidth=0.2em,

    72             shortenstart=0.5ex,

    73             shortenend=0.5ex,

    74             markstyle=cross,

    75             markfields={b5, d5, a4, e4, a2, e2, b1, d1},

    76             color=red!50,

    77             markfields={g6, f7},

    78             setpieces={Nh8, Nc3}]

    79 

    80 

    81 \subsubsection*{Disclaimer}

    82 

    83 It should be understood that the work you submit represents

    84 your own effort. You have not copied from anyone else. An

    85 exception is the Scala code I showed during the lectures or

    86 uploaded to KEATS, which you can freely use.\bigskip

    87 

    88 

    89 \subsubsection*{Task}

    90 

    91 The task is to implement a regular expression matcher based on

    92 derivatives of regular expressions. The implementation should

    93 be able to deal with the usual (basic) regular expressions

    94 

    95 \noindent {\bf Important!} Your implementation should have

    96 explicit cases for the basic regular expressions, but also

    97 explicit cases for the extended regular expressions. That

    98 means do not treat the extended regular expressions by just

    99 translating them into the basic ones. See also Question 2,

   100 where you are asked to explicitly give the rules for

   101 \textit{nullable} and \textit{der} for the extended regular

   102 expressions.

   103 

   104 

   105 

   106 \end{document}

   107 

   108 %%% Local Variables: 

   109 %%% mode: latex

   110 %%% TeX-master: t

   111 %%% End: