284
|
1 |
% !TEX program = xelatex
|
6
|
2 |
\documentclass{article}
|
|
3 |
\usepackage{chessboard}
|
|
4 |
\usepackage[LSBC4,T1]{fontenc}
|
149
|
5 |
\let\clipbox\relax
|
39
|
6 |
\usepackage{../style}
|
213
|
7 |
\usepackage{../langs}
|
166
|
8 |
\usepackage{disclaimer}
|
379
|
9 |
\usepackage{ulem}
|
6
|
10 |
|
|
11 |
\begin{document}
|
|
12 |
|
|
13 |
\setchessboard{smallboard,
|
45
|
14 |
zero,
|
6
|
15 |
showmover=false,
|
|
16 |
boardfontencoding=LSBC4,
|
|
17 |
hlabelformat=\arabic{ranklabel},
|
|
18 |
vlabelformat=\arabic{filelabel}}
|
|
19 |
|
45
|
20 |
\mbox{}\\[-18mm]\mbox{}
|
6
|
21 |
|
356
|
22 |
\section*{Preliminary and Main Part 4 (Scala, 4 + 6 Marks)}
|
6
|
23 |
|
265
|
24 |
\mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\
|
|
25 |
\mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\
|
|
26 |
\mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\
|
284
|
27 |
\mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\medskip\bigskip
|
265
|
28 |
|
|
29 |
\noindent
|
306
|
30 |
This part is about searching and backtracking. You are asked to
|
284
|
31 |
implement Scala programs that solve various versions of the
|
311
|
32 |
\textit{Knight's Tour Problem} on a chessboard. The preliminary part (4\%) is
|
379
|
33 |
due on \sout{\cwNINE{}} \textcolor{red}{16 December} at 5pm; the core part (6\%) is due on \cwNINEa{} at 5pm.
|
355
|
34 |
Any 1\% you achieve in the preliminary part counts as your ``weekly engagement''.
|
|
35 |
\bigskip
|
347
|
36 |
%Note the core, more advanced, part might include material you have not
|
|
37 |
%yet seen in the first three lectures. \bigskip
|
50
|
38 |
|
347
|
39 |
\IMPORTANTNONE{}
|
|
40 |
|
|
41 |
\noindent
|
144
|
42 |
Also note that the running time of each part will be restricted to a
|
213
|
43 |
maximum of 30 seconds on my laptop: If you calculate a result once,
|
144
|
44 |
try to avoid to calculate the result again. Feel free to copy any code
|
|
45 |
you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
|
|
46 |
\texttt{knight3.scala}.
|
39
|
47 |
|
166
|
48 |
\DISCLAIMER{}
|
39
|
49 |
|
|
50 |
\subsection*{Background}
|
|
51 |
|
|
52 |
The \textit{Knight's Tour Problem} is about finding a tour such that
|
110
|
53 |
the knight visits every field on an $n\times n$ chessboard once. For
|
|
54 |
example on a $5\times 5$ chessboard, a knight's tour is:
|
45
|
55 |
|
|
56 |
\chessboard[maxfield=d4,
|
|
57 |
pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
|
|
58 |
text = \small 24, markfield=Z4,
|
|
59 |
text = \small 11, markfield=a4,
|
|
60 |
text = \small 6, markfield=b4,
|
|
61 |
text = \small 17, markfield=c4,
|
|
62 |
text = \small 0, markfield=d4,
|
|
63 |
text = \small 19, markfield=Z3,
|
|
64 |
text = \small 16, markfield=a3,
|
|
65 |
text = \small 23, markfield=b3,
|
|
66 |
text = \small 12, markfield=c3,
|
|
67 |
text = \small 7, markfield=d3,
|
|
68 |
text = \small 10, markfield=Z2,
|
|
69 |
text = \small 5, markfield=a2,
|
|
70 |
text = \small 18, markfield=b2,
|
|
71 |
text = \small 1, markfield=c2,
|
|
72 |
text = \small 22, markfield=d2,
|
|
73 |
text = \small 15, markfield=Z1,
|
|
74 |
text = \small 20, markfield=a1,
|
|
75 |
text = \small 3, markfield=b1,
|
|
76 |
text = \small 8, markfield=c1,
|
|
77 |
text = \small 13, markfield=d1,
|
|
78 |
text = \small 4, markfield=Z0,
|
|
79 |
text = \small 9, markfield=a0,
|
|
80 |
text = \small 14, markfield=b0,
|
|
81 |
text = \small 21, markfield=c0,
|
|
82 |
text = \small 2, markfield=d0
|
|
83 |
]
|
144
|
84 |
|
45
|
85 |
\noindent
|
212
|
86 |
This tour starts in the right-upper corner, then moves to field
|
45
|
87 |
$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
|
|
88 |
$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
|
74
|
89 |
bigger board there is.
|
45
|
90 |
|
|
91 |
A knight's tour is called \emph{closed}, if the last step in the tour
|
|
92 |
is within a knight's move to the beginning of the tour. So the above
|
110
|
93 |
knight's tour is \underline{not} closed because the last
|
45
|
94 |
step on field $(0, 4)$ is not within the reach of the first step on
|
|
95 |
$(4, 4)$. It turns out there is no closed knight's tour on a $5\times
|
50
|
96 |
5$ board. But there are on a $6\times 6$ board and on bigger ones, for
|
|
97 |
example
|
6
|
98 |
|
|
99 |
\chessboard[maxfield=e5,
|
147
|
100 |
pgfstyle={[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
|
45
|
101 |
text = \small 10, markfield=Z5,
|
|
102 |
text = \small 5, markfield=a5,
|
|
103 |
text = \small 18, markfield=b5,
|
|
104 |
text = \small 25, markfield=c5,
|
|
105 |
text = \small 16, markfield=d5,
|
|
106 |
text = \small 7, markfield=e5,
|
|
107 |
text = \small 31, markfield=Z4,
|
|
108 |
text = \small 26, markfield=a4,
|
|
109 |
text = \small 9, markfield=b4,
|
|
110 |
text = \small 6, markfield=c4,
|
|
111 |
text = \small 19, markfield=d4,
|
|
112 |
text = \small 24, markfield=e4,
|
|
113 |
% 4 11 30 17 8 15
|
|
114 |
text = \small 4, markfield=Z3,
|
|
115 |
text = \small 11, markfield=a3,
|
|
116 |
text = \small 30, markfield=b3,
|
|
117 |
text = \small 17, markfield=c3,
|
|
118 |
text = \small 8, markfield=d3,
|
|
119 |
text = \small 15, markfield=e3,
|
|
120 |
%29 32 27 0 23 20
|
|
121 |
text = \small 29, markfield=Z2,
|
|
122 |
text = \small 32, markfield=a2,
|
|
123 |
text = \small 27, markfield=b2,
|
|
124 |
text = \small 0, markfield=c2,
|
|
125 |
text = \small 23, markfield=d2,
|
|
126 |
text = \small 20, markfield=e2,
|
|
127 |
%12 3 34 21 14 1
|
|
128 |
text = \small 12, markfield=Z1,
|
|
129 |
text = \small 3, markfield=a1,
|
|
130 |
text = \small 34, markfield=b1,
|
|
131 |
text = \small 21, markfield=c1,
|
|
132 |
text = \small 14, markfield=d1,
|
|
133 |
text = \small 1, markfield=e1,
|
|
134 |
%33 28 13 2 35 22
|
|
135 |
text = \small 33, markfield=Z0,
|
|
136 |
text = \small 28, markfield=a0,
|
|
137 |
text = \small 13, markfield=b0,
|
|
138 |
text = \small 2, markfield=c0,
|
|
139 |
text = \small 35, markfield=d0,
|
|
140 |
text = \small 22, markfield=e0,
|
|
141 |
vlabel=false,
|
|
142 |
hlabel=false
|
6
|
143 |
]
|
|
144 |
|
45
|
145 |
|
6
|
146 |
\noindent
|
45
|
147 |
where the 35th move can join up again with the 0th move.
|
|
148 |
|
48
|
149 |
If you cannot remember how a knight moves in chess, or never played
|
45
|
150 |
chess, below are all potential moves indicated for two knights, one on
|
48
|
151 |
field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
|
39
|
152 |
|
213
|
153 |
{\chessboard[maxfield=g7,
|
45
|
154 |
color=blue!50,
|
6
|
155 |
linewidth=0.2em,
|
|
156 |
shortenstart=0.5ex,
|
|
157 |
shortenend=0.5ex,
|
|
158 |
markstyle=cross,
|
45
|
159 |
markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
|
6
|
160 |
color=red!50,
|
45
|
161 |
markfields={f5, e6},
|
213
|
162 |
setpieces={Ng7, Nb2},
|
|
163 |
boardfontsize=12pt,labelfontsize=9pt]}
|
|
164 |
|
|
165 |
\subsection*{Reference Implementation}
|
|
166 |
|
378
|
167 |
\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from KEATS. The one
|
372
|
168 |
supplied with github does not contain the correct code. See Scala coursework
|
378
|
169 |
section on KEATS.}\medskip
|
372
|
170 |
|
|
171 |
\noindent
|
306
|
172 |
This Scala part comes with three reference implementations in form of
|
216
|
173 |
\texttt{jar}-files. This allows you to run any test cases on your own
|
213
|
174 |
computer. For example you can call Scala on the command line with the
|
|
175 |
option \texttt{-cp knight1.jar} and then query any function from the
|
216
|
176 |
\texttt{knight1.scala} template file. As usual you have to
|
347
|
177 |
prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}.
|
216
|
178 |
Since some of the calls are time sensitive, I included some timing
|
|
179 |
information. For example
|
213
|
180 |
|
|
181 |
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
|
|
182 |
$ scala -cp knight1.jar
|
347
|
183 |
scala> CW9a.enum_tours(5, List((0, 0))).length
|
213
|
184 |
Time needed: 1.722 secs.
|
|
185 |
res0: Int = 304
|
|
186 |
|
347
|
187 |
scala> CW9a.print_board(8, CW9a.first_tour(8, List((0, 0))).get)
|
213
|
188 |
Time needed: 15.411 secs.
|
|
189 |
|
|
190 |
51 46 55 44 53 4 21 12
|
|
191 |
56 43 52 3 22 13 24 5
|
|
192 |
47 50 45 54 25 20 11 14
|
|
193 |
42 57 2 49 40 23 6 19
|
|
194 |
35 48 41 26 61 10 15 28
|
|
195 |
58 1 36 39 32 27 18 7
|
|
196 |
37 34 31 60 9 62 29 16
|
|
197 |
0 59 38 33 30 17 8 63
|
|
198 |
\end{lstlisting}%$
|
|
199 |
|
|
200 |
|
|
201 |
\subsection*{Hints}
|
|
202 |
|
|
203 |
\noindent
|
307
|
204 |
\textbf{Preliminary Part} useful list functions: \texttt{.contains(..)} checks
|
213
|
205 |
whether an element is in a list, \texttt{.flatten} turns a list of
|
|
206 |
lists into just a list, \texttt{\_::\_} puts an element on the head of
|
|
207 |
the list, \texttt{.head} gives you the first element of a list (make
|
|
208 |
sure the list is not \texttt{Nil}); a useful option function:
|
|
209 |
\texttt{.isDefined} returns true, if an option is \texttt{Some(..)};
|
|
210 |
anonymous functions can be constructed using \texttt{(x:Int) => ...},
|
216
|
211 |
this function takes an \texttt{Int} as an argument.\medskip
|
45
|
212 |
|
212
|
213 |
|
|
214 |
\noindent
|
356
|
215 |
\textbf{Main Part} a useful list function: \texttt{.sortBy} sorts a list
|
212
|
216 |
according to a component given by the function; a function can be
|
216
|
217 |
tested to be tail-recursive by annotation \texttt{@tailrec}, which is
|
|
218 |
made available by importing \texttt{scala.annotation.tailrec}.\medskip
|
212
|
219 |
|
213
|
220 |
|
|
221 |
|
|
222 |
|
296
|
223 |
\subsection*{Preliminary Part (4 Marks)}
|
45
|
224 |
|
48
|
225 |
You are asked to implement the knight's tour problem such that the
|
|
226 |
dimension of the board can be changed. Therefore most functions will
|
50
|
227 |
take the dimension of the board as an argument. The fun with this
|
60
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
228 |
problem is that even for small chessboard dimensions it has already an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
incredibly large search space---finding a tour is like finding a
|
50
|
230 |
needle in a haystack. In the first task we want to see how far we get
|
|
231 |
with exhaustively exploring the complete search space for small
|
48
|
232 |
chessboards.\medskip
|
6
|
233 |
|
48
|
234 |
\noindent
|
|
235 |
Let us first fix the basic datastructures for the implementation. The
|
213
|
236 |
board dimension is an integer.
|
|
237 |
A \emph{position} (or field) on the chessboard is
|
48
|
238 |
a pair of integers, like $(0, 0)$. A \emph{path} is a list of
|
|
239 |
positions. The first (or 0th move) in a path is the last element in
|
|
240 |
this list; and the last move in the path is the first element. For
|
|
241 |
example the path for the $5\times 5$ chessboard above is represented
|
|
242 |
by
|
6
|
243 |
|
45
|
244 |
\[
|
|
245 |
\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
|
48
|
246 |
$\underbrace{\texttt{(2, 3)}}_{23}$, ...,
|
|
247 |
$\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}
|
45
|
248 |
\]
|
|
249 |
|
|
250 |
\noindent
|
|
251 |
Suppose the dimension of a chessboard is $n$, then a path is a
|
|
252 |
\emph{tour} if the length of the path is $n \times n$, each element
|
|
253 |
occurs only once in the path, and each move follows the rules of how a
|
|
254 |
knight moves (see above for the rules).
|
6
|
255 |
|
|
256 |
|
45
|
257 |
\subsubsection*{Tasks (file knight1.scala)}
|
|
258 |
|
378
|
259 |
|
|
260 |
|
45
|
261 |
\begin{itemize}
|
212
|
262 |
\item[(1)] Implement an \texttt{is\_legal} function that takes a
|
166
|
263 |
dimension, a path and a position as arguments and tests whether the
|
50
|
264 |
position is inside the board and not yet element in the
|
|
265 |
path. \hfill[1 Mark]
|
45
|
266 |
|
212
|
267 |
\item[(2)] Implement a \texttt{legal\_moves} function that calculates for a
|
48
|
268 |
position all legal onward moves. If the onward moves are
|
45
|
269 |
placed on a circle, you should produce them starting from
|
145
|
270 |
``12-o'clock'' following in clockwise order. For example on an
|
166
|
271 |
$8\times 8$ board for a knight at position $(2, 2)$ and otherwise
|
48
|
272 |
empty board, the legal-moves function should produce the onward
|
50
|
273 |
positions in this order:
|
6
|
274 |
|
45
|
275 |
\begin{center}
|
|
276 |
\texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
|
|
277 |
\end{center}
|
|
278 |
|
50
|
279 |
If the board is not empty, then maybe some of the moves need to be
|
|
280 |
filtered out from this list. For a knight on field $(7, 7)$ and an
|
|
281 |
empty board, the legal moves are
|
45
|
282 |
|
|
283 |
\begin{center}
|
|
284 |
\texttt{List((6,5), (5,6))}
|
48
|
285 |
\end{center}
|
|
286 |
\mbox{}\hfill[1 Mark]
|
45
|
287 |
|
212
|
288 |
\item[(3)] Implement two recursive functions (\texttt{count\_tours} and
|
166
|
289 |
\texttt{enum\_tours}). They each take a dimension and a path as
|
110
|
290 |
arguments. They exhaustively search for tours starting
|
|
291 |
from the given path. The first function counts all possible
|
50
|
292 |
tours (there can be none for certain board sizes) and the second
|
216
|
293 |
collects all tours in a list of paths. These functions will be
|
|
294 |
called with a path containing a single position---the starting field.
|
|
295 |
They are expected to extend this path so as to find all tours starting
|
|
296 |
from the given position.\\
|
|
297 |
\mbox{}\hfill[2 Marks]
|
45
|
298 |
\end{itemize}
|
6
|
299 |
|
212
|
300 |
\noindent \textbf{Test data:} For the marking, the functions in (3)
|
50
|
301 |
will be called with board sizes up to $5 \times 5$. If you search
|
110
|
302 |
for tours on a $5 \times 5$ board starting only from field $(0, 0)$,
|
50
|
303 |
there are 304 of tours. If you try out every field of a $5 \times
|
110
|
304 |
5$-board as a starting field and add up all tours, you obtain
|
48
|
305 |
1728. A $6\times 6$ board is already too large to be searched
|
110
|
306 |
exhaustively.\footnote{For your interest, the number of tours on
|
48
|
307 |
$6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
|
213
|
308 |
19591828170979904, respectively.}\smallskip
|
148
|
309 |
|
212
|
310 |
|
296
|
311 |
\subsection*{Core Part (6 Marks)}
|
45
|
312 |
|
296
|
313 |
|
|
314 |
\subsubsection*{Tasks (file knight1.scala cont.)}
|
45
|
315 |
|
378
|
316 |
\mbox{}\alert{}\textcolor{red}{You need to copy your \texttt{knight1.scala}
|
|
317 |
from the preliminary part to the main part and then solve Tasks 4 and 5
|
|
318 |
inside the copied file. Do not forget to ``git add'' the file for
|
|
319 |
pushing the results to the directory \texttt{main4}.}\medskip
|
|
320 |
|
|
321 |
|
45
|
322 |
\begin{itemize}
|
212
|
323 |
\item[(4)] Implement a \texttt{first}-function. This function takes a list of
|
166
|
324 |
positions and a function $f$ as arguments; $f$ is the name we give to
|
|
325 |
this argument). The function $f$ takes a position as argument and
|
|
326 |
produces an optional path. So $f$'s type is \texttt{Pos =>
|
|
327 |
Option[Path]}. The idea behind the \texttt{first}-function is as follows:
|
45
|
328 |
|
|
329 |
\[
|
|
330 |
\begin{array}{lcl}
|
48
|
331 |
\textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\
|
|
332 |
\textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
|
45
|
333 |
f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
|
48
|
334 |
\textit{first}(xs, f) & \textit{otherwise}\\
|
45
|
335 |
\end{cases}
|
|
336 |
\end{array}
|
|
337 |
\]
|
|
338 |
|
48
|
339 |
\noindent That is, we want to find the first position where the
|
166
|
340 |
result of $f$ is not \texttt{None}, if there is one. Note that
|
|
341 |
`inside' \texttt{first}, you do not (need to) know anything about
|
|
342 |
the argument $f$ except its type, namely \texttt{Pos =>
|
213
|
343 |
Option[Path]}. If you want to find out what the result of $f$ is
|
|
344 |
on a particular argument, say $x$, you can just write $f(x)$.
|
|
345 |
There is one additional point however you should
|
166
|
346 |
take into account when implementing \texttt{first}: you will need to
|
|
347 |
calculate what the result of $f(x)$ is; your code should do this
|
|
348 |
only \textbf{once} and for as \textbf{few} elements in the list as
|
|
349 |
possible! Do not calculate $f(x)$ for all elements and then see which
|
|
350 |
is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
|
48
|
351 |
|
212
|
352 |
\item[(5)] Implement a \texttt{first\_tour} function that uses the
|
213
|
353 |
\texttt{first}-function from (4), and searches recursively for single tour.
|
166
|
354 |
As there might not be such a tour at all, the \texttt{first\_tour} function
|
|
355 |
needs to return a value of type
|
212
|
356 |
\texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark]
|
48
|
357 |
\end{itemize}
|
|
358 |
|
|
359 |
\noindent
|
166
|
360 |
\textbf{Testing:} The \texttt{first\_tour} function will be called with board
|
148
|
361 |
sizes of up to $8 \times 8$.
|
|
362 |
\bigskip
|
6
|
363 |
|
296
|
364 |
%%\newpage
|
148
|
365 |
|
307
|
366 |
\noindent
|
296
|
367 |
As you should have seen in the earlier parts, a naive search for tours beyond
|
145
|
368 |
$8 \times 8$ boards and also searching for closed tours even on small
|
329
|
369 |
boards takes too much time. There is a heuristics, called \emph{Warnsdorf's
|
|
370 |
Rule} that can speed up finding a tour. This heuristics states that a
|
145
|
371 |
knight is moved so that it always proceeds to the field from which the
|
48
|
372 |
knight will have the \underline{fewest} onward moves. For example for
|
|
373 |
a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
|
|
374 |
onward moves, namely 2.
|
45
|
375 |
|
|
376 |
\chessboard[maxfield=g7,
|
|
377 |
pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
|
|
378 |
text = \small 3, markfield=Z5,
|
|
379 |
text = \small 7, markfield=b5,
|
|
380 |
text = \small 7, markfield=c4,
|
|
381 |
text = \small 7, markfield=c2,
|
|
382 |
text = \small 5, markfield=b1,
|
|
383 |
text = \small 2, markfield=Z1,
|
|
384 |
setpieces={Na3}]
|
|
385 |
|
|
386 |
\noindent
|
166
|
387 |
Warnsdorf's Rule states that the moves on the board above should be
|
50
|
388 |
tried in the order
|
45
|
389 |
|
|
390 |
\[
|
46
|
391 |
(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
|
45
|
392 |
\]
|
|
393 |
|
46
|
394 |
\noindent
|
60
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
395 |
Whenever there are ties, the corresponding onward moves can be in any
|
45
|
396 |
order. When calculating the number of onward moves for each field, we
|
|
397 |
do not count moves that revisit any field already visited.
|
|
398 |
|
213
|
399 |
\subsubsection*{Tasks (file knight2.scala)}
|
45
|
400 |
|
|
401 |
\begin{itemize}
|
212
|
402 |
\item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of
|
216
|
403 |
onward moves like in (2) but orders them according to
|
166
|
404 |
Warnsdorf’s Rule. That means moves with the fewest legal onward moves
|
86
|
405 |
should come first (in order to be tried out first). \hfill[1 Mark]
|
50
|
406 |
|
329
|
407 |
\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristics}
|
213
|
408 |
function that searches for a single
|
|
409 |
\textbf{closed} tour on a $6\times 6$ board. It should try out
|
|
410 |
onward moves according to
|
|
411 |
the \texttt{ordered\_moves} function from (6). It is more likely to find
|
50
|
412 |
a solution when started in the middle of the board (that is
|
86
|
413 |
position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
|
45
|
414 |
|
329
|
415 |
\item[(8)] Implement a \texttt{first\_tour\_heuristics} function
|
166
|
416 |
for boards up to
|
213
|
417 |
$30\times 30$. It is the same function as in (7) but searches for
|
|
418 |
tours (not just closed tours). It might be called with any field on the
|
216
|
419 |
board as starting field.\\
|
213
|
420 |
%You have to be careful to write a
|
329
|
421 |
%tail-recursive function of the \texttt{first\_tour\_heuristics} function
|
213
|
422 |
%otherwise you will get problems with stack-overflows.\\
|
|
423 |
\mbox{}\hfill[1 Mark]
|
|
424 |
\end{itemize}
|
|
425 |
|
|
426 |
\subsubsection*{Task (file knight3.scala)}
|
|
427 |
\begin{itemize}
|
|
428 |
\item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is
|
216
|
429 |
the same function as in (8), \textbf{but} should be able to
|
|
430 |
deal with boards up to
|
|
431 |
$70\times 70$ \textbf{within 30 seconds} (on my laptop). This will be tested
|
213
|
432 |
by starting from field $(0, 0)$. You have to be careful to
|
|
433 |
write a tail-recursive function otherwise you will get problems
|
|
434 |
with stack-overflows. Please observe the requirements about
|
|
435 |
the submissions: no tricks involving \textbf{.par}.\medskip
|
|
436 |
|
216
|
437 |
The timelimit of 30 seconds is with respect to the laptop on which the
|
|
438 |
marking will happen. You can roughly estimate how well your
|
213
|
439 |
implementation performs by running \texttt{knight3.jar} on your
|
216
|
440 |
computer. For example the reference implementation shows
|
|
441 |
on my laptop:
|
213
|
442 |
|
|
443 |
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
|
|
444 |
$ scala -cp knight3.jar
|
|
445 |
|
347
|
446 |
scala> CW9c.tour_on_mega_board(70, List((0, 0)))
|
213
|
447 |
Time needed: 9.484 secs.
|
|
448 |
...<<long_list>>...
|
|
449 |
\end{lstlisting}%$
|
|
450 |
|
145
|
451 |
\mbox{}\hfill[1 Mark]
|
45
|
452 |
\end{itemize}
|
148
|
453 |
\bigskip
|
|
454 |
|
|
455 |
|
|
456 |
|
6
|
457 |
|
|
458 |
\end{document}
|
|
459 |
|
|
460 |
%%% Local Variables:
|
|
461 |
%%% mode: latex
|
|
462 |
%%% TeX-master: t
|
|
463 |
%%% End:
|