161 \subsection*{Part 1 (7 Marks)} |
161 \subsection*{Part 1 (7 Marks)} |
162 |
162 |
163 You are asked to implement the knight's tour problem such that the |
163 You are asked to implement the knight's tour problem such that the |
164 dimension of the board can be changed. Therefore most functions will |
164 dimension of the board can be changed. Therefore most functions will |
165 take the dimension of the board as an argument. The fun with this |
165 take the dimension of the board as an argument. The fun with this |
166 problem is that even for small chessbord dimensions it has already an |
166 problem is that even for small chessboard dimensions it has already an |
167 incredably large search space---finding a tour is like finding a |
167 incredibly large search space---finding a tour is like finding a |
168 needle in a haystack. In the first task we want to see how far we get |
168 needle in a haystack. In the first task we want to see how far we get |
169 with exhaustively exploring the complete search space for small |
169 with exhaustively exploring the complete search space for small |
170 chessboards.\medskip |
170 chessboards.\medskip |
171 |
171 |
172 \noindent |
172 \noindent |
173 Let us first fix the basic datastructures for the implementation. The |
173 Let us first fix the basic datastructures for the implementation. The |
174 board dimension is an integer (we will never go boyond board sizes of |
174 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 |
175 $100 \times 100$). A \emph{position} (or field) on the chessboard is |
176 a pair of integers, like $(0, 0)$. A \emph{path} is a list of |
176 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 |
177 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 |
178 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 |
179 example the path for the $5\times 5$ chessboard above is represented |
292 text = \small 5, markfield=b1, |
292 text = \small 5, markfield=b1, |
293 text = \small 2, markfield=Z1, |
293 text = \small 2, markfield=Z1, |
294 setpieces={Na3}] |
294 setpieces={Na3}] |
295 |
295 |
296 \noindent |
296 \noindent |
297 Warnsdorf's rule states that the moves on the board above sould be |
297 Warnsdorf's rule states that the moves on the board above should be |
298 tried in the order |
298 tried in the order |
299 |
299 |
300 \[ |
300 \[ |
301 (0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2) |
301 (0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2) |
302 \] |
302 \] |
303 |
303 |
304 \noindent |
304 \noindent |
305 Whenever there are ties, the correspoding onward moves can be in any |
305 Whenever there are ties, the corresponding onward moves can be in any |
306 order. When calculating the number of onward moves for each field, we |
306 order. When calculating the number of onward moves for each field, we |
307 do not count moves that revisit any field already visited. |
307 do not count moves that revisit any field already visited. |
308 |
308 |
309 \subsubsection*{Tasks (file knight3.scala)} |
309 \subsubsection*{Tasks (file knight3.scala)} |
310 |
310 |
314 Warnsdorf’s rule. That means moves with the fewest legal onward moves |
314 Warnsdorf’s rule. That means moves with the fewest legal onward moves |
315 should come first (in order to be tried out first). |
315 should come first (in order to be tried out first). |
316 |
316 |
317 \item[(3b)] Implement a first-closed-tour-heuristic function that searches for a |
317 \item[(3b)] Implement a first-closed-tour-heuristic function that searches for a |
318 \textbf{closed} tour on a $6\times 6$ board. It should use the |
318 \textbf{closed} tour on a $6\times 6$ board. It should use the |
319 first-function from (2a) and tries out onwards moves according to |
319 first-function from (2a) and tries out onward moves according to |
320 the ordered-moves function from (3a). It is more likely to find |
320 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 |
321 a solution when started in the middle of the board (that is |
322 position $(dimension / 2, dimension / 2)$). |
322 position $(dimension / 2, dimension / 2)$). |
323 |
323 |
324 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. |
324 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$. |