186 chessboards.\medskip |
186 chessboards.\medskip |
187 |
187 |
188 \noindent |
188 \noindent |
189 Let us first fix the basic datastructures for the implementation. The |
189 Let us first fix the basic datastructures for the implementation. The |
190 board dimension is an integer (we will never go beyond board sizes of |
190 board dimension is an integer (we will never go beyond board sizes of |
191 $50 \times 50$). A \emph{position} (or field) on the chessboard is |
191 $40 \times 40$). A \emph{position} (or field) on the chessboard is |
192 a pair of integers, like $(0, 0)$. A \emph{path} is a list of |
192 a pair of integers, like $(0, 0)$. A \emph{path} is a list of |
193 positions. The first (or 0th move) in a path is the last element in |
193 positions. The first (or 0th move) in a path is the last element in |
194 this list; and the last move in the path is the first element. For |
194 this list; and the last move in the path is the first element. For |
195 example the path for the $5\times 5$ chessboard above is represented |
195 example the path for the $5\times 5$ chessboard above is represented |
196 by |
196 by |
217 path. \hfill[1 Mark] |
217 path. \hfill[1 Mark] |
218 |
218 |
219 \item[(1b)] Implement a \texttt{legal-moves} function that calculates for a |
219 \item[(1b)] Implement a \texttt{legal-moves} function that calculates for a |
220 position all legal onward moves. If the onward moves are |
220 position all legal onward moves. If the onward moves are |
221 placed on a circle, you should produce them starting from |
221 placed on a circle, you should produce them starting from |
222 ``12-oclock'' following in clockwise order. For example on an |
222 ``12-o'clock'' following in clockwise order. For example on an |
223 $8\times 8$ board for a knight on position $(2, 2)$ and otherwise |
223 $8\times 8$ board for a knight on position $(2, 2)$ and otherwise |
224 empty board, the legal-moves function should produce the onward |
224 empty board, the legal-moves function should produce the onward |
225 positions in this order: |
225 positions in this order: |
226 |
226 |
227 \begin{center} |
227 \begin{center} |
290 |
290 |
291 \noindent |
291 \noindent |
292 \textbf{Testing} The first tour function will be called with board |
292 \textbf{Testing} The first tour function will be called with board |
293 sizes of up to $8 \times 8$. |
293 sizes of up to $8 \times 8$. |
294 |
294 |
295 |
295 %%\newpage |
296 \subsection*{Part 2 (3 Marks)} |
296 \subsection*{Part 2 (3 Marks)} |
297 |
297 |
298 As you should have seen in Part 1, a naive search for tours |
298 As you should have seen in Part 1, a naive search for tours beyond |
299 beyond $8 \times 8$ boards and also searching for closed tours |
299 $8 \times 8$ boards and also searching for closed tours even on small |
300 takes too much time. There is a heuristic, called Warnsdorf's rule |
300 boards takes too much time. There is a heuristic, called Warnsdorf's |
301 that can speed up finding a tour. This heuristic states that a knight |
301 rule that can speed up finding a tour. This heuristic states that a |
302 is moved so that it always proceeds to the field from which the |
302 knight is moved so that it always proceeds to the field from which the |
303 knight will have the \underline{fewest} onward moves. For example for |
303 knight will have the \underline{fewest} onward moves. For example for |
304 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible |
304 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible |
305 onward moves, namely 2. |
305 onward moves, namely 2. |
306 |
306 |
307 \chessboard[maxfield=g7, |
307 \chessboard[maxfield=g7, |
340 first-function from (2a) and tries out onward moves according to |
340 first-function from (2a) and tries out onward moves according to |
341 the ordered-moves function from (3a). It is more likely to find |
341 the ordered-moves function from (3a). It is more likely to find |
342 a solution when started in the middle of the board (that is |
342 a solution when started in the middle of the board (that is |
343 position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] |
343 position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] |
344 |
344 |
345 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. |
345 \item[(3c)] Implement a first-tour-heuristic function for boards up to |
346 It is the same function as in (3b) but searches for tours. You have |
346 $40\times 40$. It is the same function as in (3b) but searches for |
347 to be careful to write a tail-recursive version of the first-tour-heuristic |
347 tours (not just closed tours). You have to be careful to write a |
348 function otherwise you will get problems with stack-overflows. \hfill[1 Mark] |
348 tail-recursive version of the first-tour-heuristic function |
|
349 otherwise you will get problems with stack-overflows.\\ |
|
350 \mbox{}\hfill[1 Mark] |
349 \end{itemize} |
351 \end{itemize} |
350 |
352 |
351 \end{document} |
353 \end{document} |
352 |
354 |
353 %%% Local Variables: |
355 %%% Local Variables: |