16 |
16 |
17 \section*{Coursework 7 (Scala, Knight's Tour)} |
17 \section*{Coursework 7 (Scala, Knight's Tour)} |
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 21 December 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. Note the second part |
23 \textit{Knight's Tour Problem} on a chessboard. Note the second part |
24 might include material you have not yet seen in the first two |
24 might include material you have not yet seen in the first two |
25 lectures. Make sure the files you submit can be processed by just |
25 lectures. \bigskip |
26 calling \texttt{scala <<filename.scala>>}.\bigskip |
26 |
27 |
27 \noindent |
28 \noindent |
28 \textbf{Important:} |
29 \textbf{Important:} Do not use any mutable data structures in your |
29 |
30 submissions! They are not needed. This means you cannot use |
30 \begin{itemize} |
31 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
31 \item Make sure the files you submit can be processed by just calling\\ |
32 code! It has a different meaning in Scala, than in Java. |
32 \mbox{\texttt{scala <<filename.scala>>}} on the commandline. |
33 Do not use \texttt{var}! This declares a mutable variable. Feel free to |
33 |
34 copy any code you need from files \texttt{knight1.scala}, |
34 \item Do not use any mutable data structures in your |
35 \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the |
35 submissions! They are not needed. This means you cannot use |
36 functions you submit are defined on the ``top-level'' of Scala, not |
36 \texttt{ListBuffer}s, for example. |
37 inside a class or object. Also note that the running time of |
37 |
38 each part will be restricted to a maximum of 360 seconds on my |
38 \item Do not use \texttt{return} in your code! It has a different |
39 laptop. |
39 meaning in Scala, than in Java. |
40 |
40 |
|
41 \item Do not use \texttt{var}! This declares a mutable variable. Only |
|
42 use \texttt{val}! |
|
43 |
|
44 \item Do not use any parallel collections! No \texttt{.par} therefore! |
|
45 Our testing and marking infrastructure is not set up for it. |
|
46 \end{itemize} |
|
47 |
|
48 \noindent |
|
49 Also note that the running time of each part will be restricted to a |
|
50 maximum of 360 seconds on my laptop: If you calculate a result once, |
|
51 try to avoid to calculate the result again. Feel free to copy any code |
|
52 you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and |
|
53 \texttt{knight3.scala}. |
41 |
54 |
42 \subsection*{Disclaimer} |
55 \subsection*{Disclaimer} |
43 |
56 |
44 It should be understood that the work you submit represents |
57 It should be understood that the work you submit represents |
45 your own effort. You have not copied from anyone else. An |
58 your own effort. You have not copied from anyone else. An |
46 exception is the Scala code I showed during the lectures or |
59 exception is the Scala code I showed during the lectures or |
47 uploaded to KEATS, which you can freely use.\medskip |
60 uploaded to KEATS, which you can freely use. |
48 |
61 |
49 \subsection*{Background} |
62 \subsection*{Background} |
50 |
63 |
51 The \textit{Knight's Tour Problem} is about finding a tour such that |
64 The \textit{Knight's Tour Problem} is about finding a tour such that |
52 the knight visits every field on an $n\times n$ chessboard once. For |
65 the knight visits every field on an $n\times n$ chessboard once. For |
53 example on a $5\times 5$ chessboard, a knight's tour is: |
66 example on a $5\times 5$ chessboard, a knight's tour is: |
54 |
|
55 |
67 |
56 \chessboard[maxfield=d4, |
68 \chessboard[maxfield=d4, |
57 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
69 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
58 text = \small 24, markfield=Z4, |
70 text = \small 24, markfield=Z4, |
59 text = \small 11, markfield=a4, |
71 text = \small 11, markfield=a4, |
79 text = \small 9, markfield=a0, |
91 text = \small 9, markfield=a0, |
80 text = \small 14, markfield=b0, |
92 text = \small 14, markfield=b0, |
81 text = \small 21, markfield=c0, |
93 text = \small 21, markfield=c0, |
82 text = \small 2, markfield=d0 |
94 text = \small 2, markfield=d0 |
83 ] |
95 ] |
84 |
96 |
85 \noindent |
97 \noindent |
86 The tour starts in the right-upper corner, then moves to field |
98 The tour starts in the right-upper corner, then moves to field |
87 $(3,2)$, then $(4,0)$ and so on. There are no knight's tours on |
99 $(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 |
100 $2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every |
89 bigger board there is. |
101 bigger board there is. |