|
6
|
1 |
\documentclass{article}
|
|
|
2 |
\usepackage{chessboard}
|
|
|
3 |
\usepackage[LSBC4,T1]{fontenc}
|
|
39
|
4 |
\usepackage{../style}
|
|
6
|
5 |
|
|
|
6 |
\begin{document}
|
|
|
7 |
|
|
|
8 |
\setchessboard{smallboard,
|
|
|
9 |
showmover=false,
|
|
|
10 |
boardfontencoding=LSBC4,
|
|
|
11 |
hlabelformat=\arabic{ranklabel},
|
|
|
12 |
vlabelformat=\arabic{filelabel}}
|
|
|
13 |
|
|
|
14 |
|
|
|
15 |
|
|
36
|
16 |
\section*{Coursework 7 (Scala, Knight's Tour)}
|
|
6
|
17 |
|
|
39
|
18 |
This coursework is worth 10\%. The first part is due on 23 November
|
|
|
19 |
at 11pm; the second, more advanced part, is due on 30 November at
|
|
|
20 |
11pm. You are asked to implement Scala programs that solve various
|
|
|
21 |
versions of the \textit{Knight's Tour Problem} on a chessboard.
|
|
|
22 |
|
|
|
23 |
\subsection*{Disclaimer}
|
|
|
24 |
|
|
|
25 |
It should be understood that the work you submit represents
|
|
|
26 |
your own effort. You have not copied from anyone else. An
|
|
|
27 |
exception is the Scala code I showed during the lectures or
|
|
|
28 |
uploaded to KEATS, which you can freely use.\bigskip
|
|
|
29 |
|
|
|
30 |
\subsection*{Background}
|
|
|
31 |
|
|
|
32 |
The \textit{Knight's Tour Problem} is about finding a tour such that
|
|
|
33 |
the knight visits every field on a $n\times n$ chessboard once. For
|
|
|
34 |
example on a $5\times 5$ chessboard, a knight's tour is as follows:
|
|
|
35 |
|
|
6
|
36 |
|
|
|
37 |
\chessboard[maxfield=e5,
|
|
|
38 |
pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
|
|
|
39 |
text = \bf\small 24, markfield=a5,
|
|
|
40 |
text = \small 11, markfield=b5,
|
|
|
41 |
text = \small 6, markfield=c5,
|
|
|
42 |
text = \small 17, markfield=d5,
|
|
|
43 |
text = \small 0, markfield=e5,
|
|
|
44 |
text = \small 19, markfield=a4,
|
|
|
45 |
text = \small 16, markfield=b4,
|
|
|
46 |
text = \small 23, markfield=c4,
|
|
|
47 |
text = \small 12, markfield=d4,
|
|
|
48 |
text = \small 7, markfield=e4,
|
|
|
49 |
text = \small 10, markfield=a3,
|
|
|
50 |
text = \small 5, markfield=b3,
|
|
|
51 |
text = \small 18, markfield=c3,
|
|
|
52 |
text = \small 1, markfield=d3,
|
|
|
53 |
text = \small 22, markfield=e3,
|
|
|
54 |
text = \small 15, markfield=a2,
|
|
|
55 |
text = \small 20, markfield=b2,
|
|
|
56 |
text = \small 3, markfield=c2,
|
|
|
57 |
text = \small 8, markfield=d2,
|
|
|
58 |
text = \small 13, markfield=e2,
|
|
|
59 |
text = \small 4, markfield=a1,
|
|
|
60 |
text = \small 9, markfield=b1,
|
|
|
61 |
text = \small 14, markfield=c1,
|
|
|
62 |
text = \small 21, markfield=d1,
|
|
|
63 |
text = \small 2, markfield=e1
|
|
|
64 |
]
|
|
|
65 |
|
|
|
66 |
\noindent
|
|
39
|
67 |
The tour starts in the right-upper corner, then moves to field $(4,3)$,
|
|
|
68 |
then $(5,1)$ and so on. There are no knight's tours on $2\times 2$, $3\times 3$
|
|
|
69 |
and $4\times 4$ chessboards, but for every bigger board there is.
|
|
|
70 |
|
|
|
71 |
|
|
|
72 |
A knight's tour is called \emph{closed}, if
|
|
6
|
73 |
the last step in the tour is within a knight's move to the beginning
|
|
39
|
74 |
of the tour. So the above knight's tour is \underline{not} closed (it is
|
|
6
|
75 |
open) because the last step on field $(1, 5)$ is not within the reach
|
|
|
76 |
of the first step on $(5, 5)$. It turns out there is no closed
|
|
39
|
77 |
knight's tour on a $5\times 5$ board. But there are on a $6\times
|
|
|
78 |
6$ board.\bigskip
|
|
6
|
79 |
|
|
39
|
80 |
\noindent
|
|
|
81 |
If you cannot remember how a knight moved in chess, or never played
|
|
|
82 |
chess, below are all potential moves indicated for two knights, one on
|
|
|
83 |
field $(3, 3)$ and another on $(8, 8)$:
|
|
6
|
84 |
|
|
|
85 |
|
|
|
86 |
\chessboard[color=blue!50,
|
|
|
87 |
linewidth=0.2em,
|
|
|
88 |
shortenstart=0.5ex,
|
|
|
89 |
shortenend=0.5ex,
|
|
|
90 |
markstyle=cross,
|
|
|
91 |
markfields={b5, d5, a4, e4, a2, e2, b1, d1},
|
|
|
92 |
color=red!50,
|
|
|
93 |
markfields={g6, f7},
|
|
|
94 |
setpieces={Nh8, Nc3}]
|
|
|
95 |
|
|
|
96 |
|
|
|
97 |
|
|
|
98 |
|
|
|
99 |
\subsubsection*{Task}
|
|
|
100 |
|
|
|
101 |
The task is to implement a regular expression matcher based on
|
|
|
102 |
derivatives of regular expressions. The implementation should
|
|
|
103 |
be able to deal with the usual (basic) regular expressions
|
|
|
104 |
|
|
|
105 |
\noindent {\bf Important!} Your implementation should have
|
|
|
106 |
explicit cases for the basic regular expressions, but also
|
|
|
107 |
explicit cases for the extended regular expressions. That
|
|
|
108 |
means do not treat the extended regular expressions by just
|
|
|
109 |
translating them into the basic ones. See also Question 2,
|
|
|
110 |
where you are asked to explicitly give the rules for
|
|
|
111 |
\textit{nullable} and \textit{der} for the extended regular
|
|
|
112 |
expressions.
|
|
|
113 |
|
|
|
114 |
|
|
|
115 |
|
|
|
116 |
\end{document}
|
|
|
117 |
|
|
|
118 |
%%% Local Variables:
|
|
|
119 |
%%% mode: latex
|
|
|
120 |
%%% TeX-master: t
|
|
|
121 |
%%% End:
|