255 there are 304 of tours. If you try out every field of a $5 \times |
255 there are 304 of tours. If you try out every field of a $5 \times |
256 5$-board as a starting field and add up all tours, you obtain |
256 5$-board as a starting field and add up all tours, you obtain |
257 1728. A $6\times 6$ board is already too large to be searched |
257 1728. A $6\times 6$ board is already too large to be searched |
258 exhaustively.\footnote{For your interest, the number of tours on |
258 exhaustively.\footnote{For your interest, the number of tours on |
259 $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320, |
259 $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320, |
260 19591828170979904, respectively.} |
260 19591828170979904, respectively.}\bigskip |
|
261 |
|
262 \noindent |
|
263 \textbf{Hints:} useful list functions: \texttt{.contains(..)} checks whether an |
|
264 element is in a list, \texttt{.flatten} turns a list of lists into just a list, |
|
265 \texttt{\_::\_} puts an element on the head of the list, \texttt{.head} gives you the |
|
266 first element of a list (make sure the list is not \texttt{Nil}) |
261 |
267 |
262 \subsubsection*{Tasks (file knight2.scala)} |
268 \subsubsection*{Tasks (file knight2.scala)} |
263 |
269 |
264 \begin{itemize} |
270 \begin{itemize} |
265 \item[(2a)] Implement a first-function. This function takes a list of |
271 \item[(2a)] Implement a first-function. This function takes a list of |
292 needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks] |
298 needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks] |
293 \end{itemize} |
299 \end{itemize} |
294 |
300 |
295 \noindent |
301 \noindent |
296 \textbf{Testing} The first tour function will be called with board |
302 \textbf{Testing} The first tour function will be called with board |
297 sizes of up to $8 \times 8$. |
303 sizes of up to $8 \times 8$. |
298 |
304 \bigskip |
299 %%\newpage |
305 |
|
306 \noindent |
|
307 \textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a list according |
|
308 to a boolean function; a useful option function: \texttt{.isDefined} returns true, |
|
309 if an option is \texttt{Some(..)}; anonymous functions can be constructed using |
|
310 \texttt{(x:Int) => ...}, this functions takes an \texttt{Int} as argument |
|
311 |
|
312 |
|
313 \newpage |
300 \subsection*{Part 2 (3 Marks)} |
314 \subsection*{Part 2 (3 Marks)} |
301 |
315 |
302 As you should have seen in Part 1, a naive search for tours beyond |
316 As you should have seen in Part 1, a naive search for tours beyond |
303 $8 \times 8$ boards and also searching for closed tours even on small |
317 $8 \times 8$ boards and also searching for closed tours even on small |
304 boards takes too much time. There is a heuristic, called Warnsdorf's |
318 boards takes too much time. There is a heuristic, called Warnsdorf's |
351 tours (not just closed tours). You have to be careful to write a |
365 tours (not just closed tours). You have to be careful to write a |
352 tail-recursive version of the first-tour-heuristic function |
366 tail-recursive version of the first-tour-heuristic function |
353 otherwise you will get problems with stack-overflows.\\ |
367 otherwise you will get problems with stack-overflows.\\ |
354 \mbox{}\hfill[1 Mark] |
368 \mbox{}\hfill[1 Mark] |
355 \end{itemize} |
369 \end{itemize} |
|
370 \bigskip |
|
371 |
|
372 \noindent |
|
373 \textbf{Hints:} a useful list function: \texttt{.sortBy} sorts a list according |
|
374 to a component given by the function; a function can be tested to be tail |
|
375 recursive by annotation \texttt{@tailrec}, which is made available by |
|
376 importing \texttt{scala.annotation.tailrec} |
|
377 |
|
378 |
356 |
379 |
357 \end{document} |
380 \end{document} |
358 |
381 |
359 %%% Local Variables: |
382 %%% Local Variables: |
360 %%% mode: latex |
383 %%% mode: latex |