32 code! It has a different meaning in Scala, than in Java. |
32 code! It has a different meaning in Scala, than in Java. |
33 Do not use \texttt{var}! This declares a mutable variable. Feel free to |
33 Do not use \texttt{var}! This declares a mutable variable. Feel free to |
34 copy any code you need from files \texttt{knight1.scala}, |
34 copy any code you need from files \texttt{knight1.scala}, |
35 \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the |
35 \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the |
36 functions you submit are defined on the ``top-level'' of Scala, not |
36 functions you submit are defined on the ``top-level'' of Scala, not |
37 inside a class or object. |
37 inside a class or object. Also note that the running time of |
|
38 each part will be restricted to a maximum of 360 seconds. |
|
39 |
38 |
40 |
39 \subsection*{Disclaimer} |
41 \subsection*{Disclaimer} |
40 |
42 |
41 It should be understood that the work you submit represents |
43 It should be understood that the work you submit represents |
42 your own effort. You have not copied from anyone else. An |
44 your own effort. You have not copied from anyone else. An |
317 |
319 |
318 \begin{itemize} |
320 \begin{itemize} |
319 \item[(3a)] Write a function ordered-moves that calculates a list of |
321 \item[(3a)] Write a function ordered-moves that calculates a list of |
320 onward moves like in (1b) but orders them according to the |
322 onward moves like in (1b) but orders them according to the |
321 Warnsdorf’s rule. That means moves with the fewest legal onward moves |
323 Warnsdorf’s rule. That means moves with the fewest legal onward moves |
322 should come first (in order to be tried out first). |
324 should come first (in order to be tried out first). \hfill[1 Mark] |
323 |
325 |
324 \item[(3b)] Implement a first-closed-tour-heuristic function that searches for a |
326 \item[(3b)] Implement a first-closed-tour-heuristic function that searches for a |
325 \textbf{closed} tour on a $6\times 6$ board. It should use the |
327 \textbf{closed} tour on a $6\times 6$ board. It should use the |
326 first-function from (2a) and tries out onward moves according to |
328 first-function from (2a) and tries out onward moves according to |
327 the ordered-moves function from (3a). It is more likely to find |
329 the ordered-moves function from (3a). It is more likely to find |
328 a solution when started in the middle of the board (that is |
330 a solution when started in the middle of the board (that is |
329 position $(dimension / 2, dimension / 2)$). |
331 position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] |
330 |
332 |
331 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. |
333 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. |
332 It is the same function as in (3b) but searches for \textbf{open} tours. You have |
334 It is the same function as in (3b) but searches for \textbf{open} tours. You have |
333 to be careful to write a tail-recursive version of the first-tour-heuristic |
335 to be careful to write a tail-recursive version of the first-tour-heuristic |
334 function otherwise you will get problems with stack-overflows. |
336 function otherwise you will get problems with stack-overflows. \hfill[1 Mark] |
335 \end{itemize} |
337 \end{itemize} |
336 |
338 |
337 \end{document} |
339 \end{document} |
338 |
340 |
339 %%% Local Variables: |
341 %%% Local Variables: |