equal
deleted
inserted
replaced
24 you submit can be processed by just calling \texttt{scala |
24 you submit can be processed by just calling \texttt{scala |
25 <<filename.scala>>}.\bigskip |
25 <<filename.scala>>}.\bigskip |
26 |
26 |
27 \noindent |
27 \noindent |
28 \textbf{Important:} Do not use any mutable data structures in your |
28 \textbf{Important:} Do not use any mutable data structures in your |
29 submissions! They are not needed. This excluded the use of |
29 submissions! They are not needed. This excludes the use of |
30 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
30 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
31 code! It has a different meaning in Scala, than in Java. |
31 code! It has a different meaning in Scala, than in Java. |
32 Do not use \texttt{var}! This declares a mutable variable. Feel free to |
32 Do not use \texttt{var}! This declares a mutable variable. Feel free to |
33 copy any code you need from files \texttt{knight1.scala}, |
33 copy any code you need from files \texttt{knight1.scala}, |
34 \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the |
34 \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the |
43 uploaded to KEATS, which you can freely use.\medskip |
43 uploaded to KEATS, which you can freely use.\medskip |
44 |
44 |
45 \subsection*{Background} |
45 \subsection*{Background} |
46 |
46 |
47 The \textit{Knight's Tour Problem} is about finding a tour such that |
47 The \textit{Knight's Tour Problem} is about finding a tour such that |
48 the knight visits every field on an $n\times n$ chessboard once. For |
48 the knight visits every field on an $n\times n$ chessboard once. Such |
49 example on a $5\times 5$ chessboard, a knight's tour is: |
49 a tour is called \emph{open} tour. For example on a $5\times 5$ |
|
50 chessboard, an open knight's tour is: |
50 |
51 |
51 |
52 |
52 \chessboard[maxfield=d4, |
53 \chessboard[maxfield=d4, |
53 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
54 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
54 text = \small 24, markfield=Z4, |
55 text = \small 24, markfield=Z4, |
80 |
81 |
81 \noindent |
82 \noindent |
82 The tour starts in the right-upper corner, then moves to field |
83 The tour starts in the right-upper corner, then moves to field |
83 $(3,2)$, then $(4,0)$ and so on. There are no knight's tours on |
84 $(3,2)$, then $(4,0)$ and so on. There are no knight's tours on |
84 $2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every |
85 $2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every |
85 bigger board there is. |
86 bigger board there is. |
86 |
87 |
87 A knight's tour is called \emph{closed}, if the last step in the tour |
88 A knight's tour is called \emph{closed}, if the last step in the tour |
88 is within a knight's move to the beginning of the tour. So the above |
89 is within a knight's move to the beginning of the tour. So the above |
89 knight's tour is \underline{not} closed (it is open) because the last |
90 knight's tour is \underline{not} closed (it is open) because the last |
90 step on field $(0, 4)$ is not within the reach of the first step on |
91 step on field $(0, 4)$ is not within the reach of the first step on |
170 chessboards.\medskip |
171 chessboards.\medskip |
171 |
172 |
172 \noindent |
173 \noindent |
173 Let us first fix the basic datastructures for the implementation. The |
174 Let us first fix the basic datastructures for the implementation. The |
174 board dimension is an integer (we will never go beyond board sizes of |
175 board dimension is an integer (we will never go beyond board sizes of |
175 $100 \times 100$). A \emph{position} (or field) on the chessboard is |
176 $50 \times 50$). A \emph{position} (or field) on the chessboard is |
176 a pair of integers, like $(0, 0)$. A \emph{path} is a list of |
177 a pair of integers, like $(0, 0)$. A \emph{path} is a list of |
177 positions. The first (or 0th move) in a path is the last element in |
178 positions. The first (or 0th move) in a path is the last element in |
178 this list; and the last move in the path is the first element. For |
179 this list; and the last move in the path is the first element. For |
179 example the path for the $5\times 5$ chessboard above is represented |
180 example the path for the $5\times 5$ chessboard above is represented |
180 by |
181 by |
242 \subsubsection*{Tasks (file knight2.scala)} |
243 \subsubsection*{Tasks (file knight2.scala)} |
243 |
244 |
244 \begin{itemize} |
245 \begin{itemize} |
245 \item[(2a)] Implement a first-function. This function takes a list of |
246 \item[(2a)] Implement a first-function. This function takes a list of |
246 positions and a function $f$ as arguments. The function $f$ takes a |
247 positions and a function $f$ as arguments. The function $f$ takes a |
247 position as argument and produces an optional path. So its type is |
248 position as argument and produces an optional path. So $f$'s type is |
248 \texttt{Pos => Option[Path]}. The idea behind the first-function is |
249 \texttt{Pos => Option[Path]}. The idea behind the first-function is |
249 as follows: |
250 as follows: |
250 |
251 |
251 \[ |
252 \[ |
252 \begin{array}{lcl} |
253 \begin{array}{lcl} |
320 the ordered-moves function from (3a). It is more likely to find |
321 the ordered-moves function from (3a). It is more likely to find |
321 a solution when started in the middle of the board (that is |
322 a solution when started in the middle of the board (that is |
322 position $(dimension / 2, dimension / 2)$). |
323 position $(dimension / 2, dimension / 2)$). |
323 |
324 |
324 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. |
325 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. |
325 It is the same function as in (3b) but searches for \textbf{open} tours. |
326 It is the same function as in (3b) but searches for \textbf{open} tours. You have |
|
327 to be careful to write a tail-recursive version of the first-tour-heuristic |
|
328 function otherwise you will get problems with stack-overflows. |
326 \end{itemize} |
329 \end{itemize} |
327 |
330 |
328 \end{document} |
331 \end{document} |
329 |
332 |
330 %%% Local Variables: |
333 %%% Local Variables: |