equal
deleted
inserted
replaced
208 made available by importing \texttt{scala.annotation.tailrec}.\medskip |
208 made available by importing \texttt{scala.annotation.tailrec}.\medskip |
209 |
209 |
210 |
210 |
211 |
211 |
212 |
212 |
213 \subsection*{Part 1 (6 Marks)} |
213 \subsection*{Preliminary Part (4 Marks)} |
214 |
214 |
215 You are asked to implement the knight's tour problem such that the |
215 You are asked to implement the knight's tour problem such that the |
216 dimension of the board can be changed. Therefore most functions will |
216 dimension of the board can be changed. Therefore most functions will |
217 take the dimension of the board as an argument. The fun with this |
217 take the dimension of the board as an argument. The fun with this |
218 problem is that even for small chessboard dimensions it has already an |
218 problem is that even for small chessboard dimensions it has already an |
294 exhaustively.\footnote{For your interest, the number of tours on |
294 exhaustively.\footnote{For your interest, the number of tours on |
295 $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320, |
295 $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320, |
296 19591828170979904, respectively.}\smallskip |
296 19591828170979904, respectively.}\smallskip |
297 |
297 |
298 |
298 |
299 |
299 \subsection*{Core Part (6 Marks)} |
300 \subsubsection*{Tasks (cont.)} |
300 |
|
301 |
|
302 \subsubsection*{Tasks (file knight1.scala cont.)} |
301 |
303 |
302 \begin{itemize} |
304 \begin{itemize} |
303 \item[(4)] Implement a \texttt{first}-function. This function takes a list of |
305 \item[(4)] Implement a \texttt{first}-function. This function takes a list of |
304 positions and a function $f$ as arguments; $f$ is the name we give to |
306 positions and a function $f$ as arguments; $f$ is the name we give to |
305 this argument). The function $f$ takes a position as argument and |
307 this argument). The function $f$ takes a position as argument and |
339 \noindent |
341 \noindent |
340 \textbf{Testing:} The \texttt{first\_tour} function will be called with board |
342 \textbf{Testing:} The \texttt{first\_tour} function will be called with board |
341 sizes of up to $8 \times 8$. |
343 sizes of up to $8 \times 8$. |
342 \bigskip |
344 \bigskip |
343 |
345 |
344 |
|
345 |
|
346 %%\newpage |
346 %%\newpage |
347 \subsection*{Advanced Part 2 (4 Marks)} |
347 |
348 |
348 |
349 As you should have seen in Part 1, 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 |
354 knight will have the \underline{fewest} onward moves. For example for |
354 knight will have the \underline{fewest} onward moves. For example for |