346 %%\newpage |
346 %%\newpage |
347 |
347 |
348 \noindent |
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 heuristics, 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 heuristics 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 |
355 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible |
355 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible |
356 onward moves, namely 2. |
356 onward moves, namely 2. |
357 |
357 |
384 \item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of |
384 \item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of |
385 onward moves like in (2) but orders them according to |
385 onward moves like in (2) but orders them according to |
386 Warnsdorf’s Rule. That means moves with the fewest legal onward moves |
386 Warnsdorf’s Rule. That means moves with the fewest legal onward moves |
387 should come first (in order to be tried out first). \hfill[1 Mark] |
387 should come first (in order to be tried out first). \hfill[1 Mark] |
388 |
388 |
389 \item[(7)] Implement a \texttt{first\_closed\_tour\_heuristic} |
389 \item[(7)] Implement a \texttt{first\_closed\_tour\_heuristics} |
390 function that searches for a single |
390 function that searches for a single |
391 \textbf{closed} tour on a $6\times 6$ board. It should try out |
391 \textbf{closed} tour on a $6\times 6$ board. It should try out |
392 onward moves according to |
392 onward moves according to |
393 the \texttt{ordered\_moves} function from (6). It is more likely to find |
393 the \texttt{ordered\_moves} function from (6). It is more likely to find |
394 a solution when started in the middle of the board (that is |
394 a solution when started in the middle of the board (that is |
395 position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] |
395 position $(dimension / 2, dimension / 2)$). \hfill[1 Mark] |
396 |
396 |
397 \item[(8)] Implement a \texttt{first\_tour\_heuristic} function |
397 \item[(8)] Implement a \texttt{first\_tour\_heuristics} function |
398 for boards up to |
398 for boards up to |
399 $30\times 30$. It is the same function as in (7) but searches for |
399 $30\times 30$. It is the same function as in (7) but searches for |
400 tours (not just closed tours). It might be called with any field on the |
400 tours (not just closed tours). It might be called with any field on the |
401 board as starting field.\\ |
401 board as starting field.\\ |
402 %You have to be careful to write a |
402 %You have to be careful to write a |
403 %tail-recursive function of the \texttt{first\_tour\_heuristic} function |
403 %tail-recursive function of the \texttt{first\_tour\_heuristics} function |
404 %otherwise you will get problems with stack-overflows.\\ |
404 %otherwise you will get problems with stack-overflows.\\ |
405 \mbox{}\hfill[1 Mark] |
405 \mbox{}\hfill[1 Mark] |
406 \end{itemize} |
406 \end{itemize} |
407 |
407 |
408 \subsubsection*{Task (file knight3.scala)} |
408 \subsubsection*{Task (file knight3.scala)} |