189 |
189 |
190 |
190 |
191 \subsection*{Hints} |
191 \subsection*{Hints} |
192 |
192 |
193 \noindent |
193 \noindent |
194 \textbf{Part 1} useful list functions: \texttt{.contains(..)} checks |
194 \textbf{Preliminary Part} useful list functions: \texttt{.contains(..)} checks |
195 whether an element is in a list, \texttt{.flatten} turns a list of |
195 whether an element is in a list, \texttt{.flatten} turns a list of |
196 lists into just a list, \texttt{\_::\_} puts an element on the head of |
196 lists into just a list, \texttt{\_::\_} puts an element on the head of |
197 the list, \texttt{.head} gives you the first element of a list (make |
197 the list, \texttt{.head} gives you the first element of a list (make |
198 sure the list is not \texttt{Nil}); a useful option function: |
198 sure the list is not \texttt{Nil}); a useful option function: |
199 \texttt{.isDefined} returns true, if an option is \texttt{Some(..)}; |
199 \texttt{.isDefined} returns true, if an option is \texttt{Some(..)}; |
200 anonymous functions can be constructed using \texttt{(x:Int) => ...}, |
200 anonymous functions can be constructed using \texttt{(x:Int) => ...}, |
201 this function takes an \texttt{Int} as an argument.\medskip |
201 this function takes an \texttt{Int} as an argument.\medskip |
202 |
202 |
203 |
203 |
204 \noindent |
204 \noindent |
205 \textbf{Part 2} a useful list function: \texttt{.sortBy} sorts a list |
205 \textbf{Core Part} a useful list function: \texttt{.sortBy} sorts a list |
206 according to a component given by the function; a function can be |
206 according to a component given by the function; a function can be |
207 tested to be tail-recursive by annotation \texttt{@tailrec}, which is |
207 tested to be tail-recursive by annotation \texttt{@tailrec}, which is |
208 made available by importing \texttt{scala.annotation.tailrec}.\medskip |
208 made available by importing \texttt{scala.annotation.tailrec}.\medskip |
209 |
209 |
210 |
210 |
343 sizes of up to $8 \times 8$. |
343 sizes of up to $8 \times 8$. |
344 \bigskip |
344 \bigskip |
345 |
345 |
346 %%\newpage |
346 %%\newpage |
347 |
347 |
348 |
348 \noindent |
349 As you should have seen in the earlier parts, a naive search for tours beyond |
349 As you should have seen in the earlier parts, a naive search for tours beyond |
350 $8 \times 8$ boards and also searching for closed tours even on small |
350 $8 \times 8$ boards and also searching for closed tours even on small |
351 boards takes too much time. There is a heuristic, called \emph{Warnsdorf's |
351 boards takes too much time. There is a heuristic, called \emph{Warnsdorf's |
352 Rule} that can speed up finding a tour. This heuristic states that a |
352 Rule} that can speed up finding a tour. This heuristic states that a |
353 knight is moved so that it always proceeds to the field from which the |
353 knight is moved so that it always proceeds to the field from which the |