equal
deleted
inserted
replaced
18 |
18 |
19 This coursework is worth 10\%. It is about searching and |
19 This coursework is worth 10\%. It is about searching and |
20 backtracking. The first part is due on 23 November at 11pm; the |
20 backtracking. The first part is due on 23 November at 11pm; the |
21 second, more advanced part, is due on 30 November at 11pm. You are |
21 second, more advanced part, is due on 30 November at 11pm. You are |
22 asked to implement Scala programs that solve various versions of the |
22 asked to implement Scala programs that solve various versions of the |
23 \textit{Knight's Tour Problem} on a chessboard. Make sure the files |
23 \textit{Knight's Tour Problem} on a chessboard. Note the second part |
24 you submit can be processed by just calling \texttt{scala |
24 might include material you have not yet seen in the first two |
25 <<filename.scala>>}.\bigskip |
25 lectures. Make sure the files you submit can be processed by just |
|
26 calling \texttt{scala <<filename.scala>>}.\bigskip |
26 |
27 |
27 \noindent |
28 \noindent |
28 \textbf{Important:} Do not use any mutable data structures in your |
29 \textbf{Important:} Do not use any mutable data structures in your |
29 submissions! They are not needed. This excludes the use of |
30 submissions! They are not needed. This excludes the use of |
30 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
31 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
258 \end{cases} |
259 \end{cases} |
259 \end{array} |
260 \end{array} |
260 \] |
261 \] |
261 |
262 |
262 \noindent That is, we want to find the first position where the |
263 \noindent That is, we want to find the first position where the |
263 result of $f$ is not \texttt{None}, if there is one.\mbox{}\hfill[1 Mark] |
264 result of $f$ is not \texttt{None}, if there is one. Note that you |
|
265 do not (need to) know anything about the function $f$ except its |
|
266 type, namely \texttt{Pos => Option[Path]}. There is one additional |
|
267 point however you should take into account when implementing |
|
268 \textit{first}: you will need to calculate what the result of $f(x)$ |
|
269 is; your code should do this only \textbf{once}!\\\mbox{}\hfill[1 Mark] |
264 |
270 |
265 \item[(2b)] Implement a first-tour function that uses the |
271 \item[(2b)] Implement a first-tour function that uses the |
266 first-function from (2a), and searches recursively for an open tour. |
272 first-function from (2a), and searches recursively for an open tour. |
267 As there might not be such a tour at all, the first-tour function |
273 As there might not be such a tour at all, the first-tour function |
268 needs to return an \texttt{Option[Path]}.\hfill[2 Marks] |
274 needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks] |
269 \end{itemize} |
275 \end{itemize} |
270 |
276 |
271 \noindent |
277 \noindent |
272 \textbf{Testing} The first tour function will be called with board |
278 \textbf{Testing} The first tour function will be called with board |
273 sizes of up to $8 \times 8$. |
279 sizes of up to $8 \times 8$. |