26 \subsection*{Disclaimer} |
27 \subsection*{Disclaimer} |
27 |
28 |
28 It should be understood that the work you submit represents |
29 It should be understood that the work you submit represents |
29 your own effort. You have not copied from anyone else. An |
30 your own effort. You have not copied from anyone else. An |
30 exception is the Scala code I showed during the lectures or |
31 exception is the Scala code I showed during the lectures or |
31 uploaded to KEATS, which you can freely use.\bigskip |
32 uploaded to KEATS, which you can freely use.\medskip |
32 |
33 |
33 \subsection*{Background} |
34 \subsection*{Background} |
34 |
35 |
35 The \textit{Knight's Tour Problem} is about finding a tour such that |
36 The \textit{Knight's Tour Problem} is about finding a tour such that |
36 the knight visits every field on a $n\times n$ chessboard once and |
37 the knight visits every field on an $n\times n$ chessboard once. For |
37 only once. For example on a $5\times 5$ chessboard, a knight's tour is |
38 example on a $5\times 5$ chessboard, a knight's tour is: |
38 as follows: |
39 |
39 |
40 |
|
41 \chessboard[maxfield=d4, |
|
42 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
|
43 text = \small 24, markfield=Z4, |
|
44 text = \small 11, markfield=a4, |
|
45 text = \small 6, markfield=b4, |
|
46 text = \small 17, markfield=c4, |
|
47 text = \small 0, markfield=d4, |
|
48 text = \small 19, markfield=Z3, |
|
49 text = \small 16, markfield=a3, |
|
50 text = \small 23, markfield=b3, |
|
51 text = \small 12, markfield=c3, |
|
52 text = \small 7, markfield=d3, |
|
53 text = \small 10, markfield=Z2, |
|
54 text = \small 5, markfield=a2, |
|
55 text = \small 18, markfield=b2, |
|
56 text = \small 1, markfield=c2, |
|
57 text = \small 22, markfield=d2, |
|
58 text = \small 15, markfield=Z1, |
|
59 text = \small 20, markfield=a1, |
|
60 text = \small 3, markfield=b1, |
|
61 text = \small 8, markfield=c1, |
|
62 text = \small 13, markfield=d1, |
|
63 text = \small 4, markfield=Z0, |
|
64 text = \small 9, markfield=a0, |
|
65 text = \small 14, markfield=b0, |
|
66 text = \small 21, markfield=c0, |
|
67 text = \small 2, markfield=d0 |
|
68 ] |
|
69 |
|
70 \noindent |
|
71 The tour starts in the right-upper corner, then moves to field |
|
72 $(3,2)$, then $(4,0)$ and so on. There are no knight's tours on |
|
73 $2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every |
|
74 bigger board there is. |
|
75 |
|
76 A knight's tour is called \emph{closed}, if the last step in the tour |
|
77 is within a knight's move to the beginning of the tour. So the above |
|
78 knight's tour is \underline{not} closed (it is open) because the last |
|
79 step on field $(0, 4)$ is not within the reach of the first step on |
|
80 $(4, 4)$. It turns out there is no closed knight's tour on a $5\times |
|
81 5$ board. But there are on a $6\times 6$ board, for example |
40 |
82 |
41 \chessboard[maxfield=e5, |
83 \chessboard[maxfield=e5, |
42 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
84 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
43 text = \bf\small 24, markfield=a5, |
85 text = \small 10, markfield=Z5, |
44 text = \small 11, markfield=b5, |
86 text = \small 5, markfield=a5, |
45 text = \small 6, markfield=c5, |
87 text = \small 18, markfield=b5, |
46 text = \small 17, markfield=d5, |
88 text = \small 25, markfield=c5, |
47 text = \small 0, markfield=e5, |
89 text = \small 16, markfield=d5, |
48 text = \small 19, markfield=a4, |
90 text = \small 7, markfield=e5, |
49 text = \small 16, markfield=b4, |
91 text = \small 31, markfield=Z4, |
50 text = \small 23, markfield=c4, |
92 text = \small 26, markfield=a4, |
51 text = \small 12, markfield=d4, |
93 text = \small 9, markfield=b4, |
52 text = \small 7, markfield=e4, |
94 text = \small 6, markfield=c4, |
53 text = \small 10, markfield=a3, |
95 text = \small 19, markfield=d4, |
54 text = \small 5, markfield=b3, |
96 text = \small 24, markfield=e4, |
55 text = \small 18, markfield=c3, |
97 % 4 11 30 17 8 15 |
56 text = \small 1, markfield=d3, |
98 text = \small 4, markfield=Z3, |
57 text = \small 22, markfield=e3, |
99 text = \small 11, markfield=a3, |
58 text = \small 15, markfield=a2, |
100 text = \small 30, markfield=b3, |
59 text = \small 20, markfield=b2, |
101 text = \small 17, markfield=c3, |
60 text = \small 3, markfield=c2, |
102 text = \small 8, markfield=d3, |
61 text = \small 8, markfield=d2, |
103 text = \small 15, markfield=e3, |
62 text = \small 13, markfield=e2, |
104 %29 32 27 0 23 20 |
63 text = \small 4, markfield=a1, |
105 text = \small 29, markfield=Z2, |
64 text = \small 9, markfield=b1, |
106 text = \small 32, markfield=a2, |
65 text = \small 14, markfield=c1, |
107 text = \small 27, markfield=b2, |
66 text = \small 21, markfield=d1, |
108 text = \small 0, markfield=c2, |
67 text = \small 2, markfield=e1 |
109 text = \small 23, markfield=d2, |
|
110 text = \small 20, markfield=e2, |
|
111 %12 3 34 21 14 1 |
|
112 text = \small 12, markfield=Z1, |
|
113 text = \small 3, markfield=a1, |
|
114 text = \small 34, markfield=b1, |
|
115 text = \small 21, markfield=c1, |
|
116 text = \small 14, markfield=d1, |
|
117 text = \small 1, markfield=e1, |
|
118 %33 28 13 2 35 22 |
|
119 text = \small 33, markfield=Z0, |
|
120 text = \small 28, markfield=a0, |
|
121 text = \small 13, markfield=b0, |
|
122 text = \small 2, markfield=c0, |
|
123 text = \small 35, markfield=d0, |
|
124 text = \small 22, markfield=e0, |
|
125 vlabel=false, |
|
126 hlabel=false |
68 ] |
127 ] |
69 |
128 |
|
129 |
70 \noindent |
130 \noindent |
71 The tour starts in the right-upper corner, then moves to field $(4,3)$, |
131 where the 35th move can join up again with the 0th move. |
72 then $(5,1)$ and so on. There are no knight's tours on $2\times 2$, $3\times 3$ |
132 |
73 and $4\times 4$ chessboards, but for every bigger board there is. |
|
74 |
|
75 |
|
76 A knight's tour is called \emph{closed}, if |
|
77 the last step in the tour is within a knight's move to the beginning |
|
78 of the tour. So the above knight's tour is \underline{not} closed (it is |
|
79 open) because the last step on field $(1, 5)$ is not within the reach |
|
80 of the first step on $(5, 5)$. It turns out there is no closed |
|
81 knight's tour on a $5\times 5$ board. But there are on a $6\times |
|
82 6$ board.\bigskip |
|
83 |
|
84 \noindent |
|
85 If you cannot remember how a knight moved in chess, or never played |
133 If you cannot remember how a knight moved in chess, or never played |
86 chess, below are all potential moves indicated for two knights, one on |
134 chess, below are all potential moves indicated for two knights, one on |
87 field $(3, 3)$ and another on $(8, 8)$: |
135 field $(2, 2)$ (blue) and another on $(7, 7)$ (red): |
88 |
136 |
89 |
137 |
90 \chessboard[color=blue!50, |
138 \chessboard[maxfield=g7, |
|
139 color=blue!50, |
91 linewidth=0.2em, |
140 linewidth=0.2em, |
92 shortenstart=0.5ex, |
141 shortenstart=0.5ex, |
93 shortenend=0.5ex, |
142 shortenend=0.5ex, |
94 markstyle=cross, |
143 markstyle=cross, |
95 markfields={b5, d5, a4, e4, a2, e2, b1, d1}, |
144 markfields={a4, c4, Z3, d3, Z1, d1, a0, c0}, |
96 color=red!50, |
145 color=red!50, |
97 markfields={g6, f7}, |
146 markfields={f5, e6}, |
98 setpieces={Nh8, Nc3}] |
147 setpieces={Ng7, Nb2}] |
99 |
148 |
100 |
149 \subsection*{Part 1 (6 Marks)} |
101 |
150 |
102 |
151 We will implement the knight's tour problem such that we can change |
103 \subsubsection*{Task} |
152 quickly the dimension of the chessboard. The fun with this problem is |
104 |
153 that even for small chessbord dimensions it has already an incredably |
105 The task is to implement a regular expression matcher based on |
154 large search space---finding a tour is like finding a needle in a |
106 derivatives of regular expressions. The implementation should |
155 haystack. In the first part we want to see far we get with |
107 be able to deal with the usual (basic) regular expressions |
156 exhaustively exploring the complete search space for small dimensions. |
108 |
157 |
109 \noindent {\bf Important!} Your implementation should have |
158 Let us first fix the basic datastructures for the implementation. A |
110 explicit cases for the basic regular expressions, but also |
159 \emph{position} (or field) on the chessboard is a pair of integers. A |
111 explicit cases for the extended regular expressions. That |
160 \emph{path} is a list of positions. The first (or 0th move) in a path |
112 means do not treat the extended regular expressions by just |
161 should be the last element in this list; and the last move is the |
113 translating them into the basic ones. See also Question 2, |
162 first element. For example the path for the $5\times 5$ chessboard |
114 where you are asked to explicitly give the rules for |
163 above is represented by |
115 \textit{nullable} and \textit{der} for the extended regular |
164 |
116 expressions. |
165 \[ |
117 |
166 \texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$, |
118 |
167 $\underbrace{\texttt{(2, 3)}}_{23}$, ..., (3, 2), $\underbrace{\texttt{(4, 4)}}_0$)} |
|
168 \] |
|
169 |
|
170 \noindent |
|
171 Suppose the dimension of a chessboard is $n$, then a path is a |
|
172 \emph{tour} if the length of the path is $n \times n$, each element |
|
173 occurs only once in the path, and each move follows the rules of how a |
|
174 knight moves (see above for the rules). |
|
175 |
|
176 |
|
177 \subsubsection*{Tasks (file knight1.scala)} |
|
178 |
|
179 \begin{itemize} |
|
180 \item[(1a)] Implement a is-legal-move function that takes a dimension, a path |
|
181 and a position as argument and tests whether the position is inside |
|
182 the board and not yet element in the path. |
|
183 |
|
184 \item[(1b)] Implement a legal-moves function that calculates for a |
|
185 position all legal follow-on moves. If the follow-on moves are |
|
186 placed on a circle, you should produce them starting from |
|
187 ``12-oclock'' following in clockwise order. For example on an |
|
188 $8\times 8$ board for a knight on position $(2, 2)$ and otherwise |
|
189 empty board, the legal-moves function should produce the follow-on |
|
190 positions |
|
191 |
|
192 \begin{center} |
|
193 \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))} |
|
194 \end{center} |
|
195 |
|
196 If the board is not empty, then maybe some of the moves need to be filtered out from this list. |
|
197 For a knight on field $(7, 7)$ and an empty board, the legal moves |
|
198 are |
|
199 |
|
200 \begin{center} |
|
201 \texttt{List((6,5), (5,6))} |
|
202 \end{center} |
|
203 |
|
204 \item[(1c)] Implement two recursive functions (count-tours and |
|
205 enum-tours). They each take a dimension and a path as |
|
206 arguments. They exhaustively search for \underline{open} tours |
|
207 starting from the given path. The first function counts all possible |
|
208 open tours (there can be none for certain board sizes) and the second |
|
209 collects all open tours in a list of paths. |
|
210 \end{itemize} |
|
211 |
|
212 \noindent \textbf{Test data:} For the marking, these functions will be |
|
213 called with board sizes up to $5 \times 5$. If you only search for |
|
214 open tours starting from field $(0, 0)$, there are 304 of them. If you |
|
215 try out every field of a $5 \times 5$-board as a starting field and |
|
216 add up all open tours, you obtain 1728. A $6\times 6$ board is already |
|
217 too large to search exhaustively: the number of open tours on |
|
218 $6\times 6$, $7\times 7$ and $8\times 8$ are |
|
219 |
|
220 \begin{center} |
|
221 \begin{tabular}{ll} |
|
222 $6\times 6$ & 6637920\\ |
|
223 $7\times 7$ & 165575218320\\ |
|
224 $8\times 8$ & 19591828170979904 |
|
225 \end{tabular} |
|
226 \end{center} |
|
227 |
|
228 \subsubsection*{Tasks (file knight2.scala)} |
|
229 |
|
230 \begin{itemize} |
|
231 \item[(2a)] Implement a first-function. This function takes a list of |
|
232 positions and a function $f$ as arguments. The function $f$ takes a |
|
233 position as argument and produces an optional path. The idea behind |
|
234 the first-function is as follows: |
|
235 |
|
236 \[ |
|
237 \begin{array}{lcl} |
|
238 first(\texttt{Nil}, f) & \dn & \texttt{None}\\ |
|
239 first(x\!::\!xs, f) & \dn & \begin{cases} |
|
240 f(x) & \textit{if}\;f(x) \not=\texttt{None}\\ |
|
241 first(xs, f) & \textit{otherwise}\\ |
|
242 \end{cases} |
|
243 \end{array} |
|
244 \] |
|
245 |
|
246 \item[(2b)] Implement a first-tour function. Using the first-function |
|
247 from (2a), search recursively for an open tour. Only use the field |
|
248 $(0, 0)$ as a starting field of the tour. As there might not be such |
|
249 a tour at all, the first-tour function needs to return an |
|
250 \texttt{Option[Path]}. For the marking, this function will be called |
|
251 with board sizes up to $8 \times 8$. |
|
252 \end{itemize} |
|
253 |
|
254 |
|
255 \subsection*{Part 2 (4 Marks)} |
|
256 |
|
257 For open tours beyond $8 \times 8$ boards and also for searching for |
|
258 closed tours, an heuristic (called Warnsdorf's rule) needs to be |
|
259 implemented. This rule states that a knight is moved so that it |
|
260 always proceeds to the square from which the knight will have the |
|
261 fewest onward moves. For example for a knight on field $(1, 3)$, |
|
262 the field $(0, 1)$ has the fewest possible onward moves. |
|
263 |
|
264 \chessboard[maxfield=g7, |
|
265 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
|
266 text = \small 3, markfield=Z5, |
|
267 text = \small 7, markfield=b5, |
|
268 text = \small 7, markfield=c4, |
|
269 text = \small 7, markfield=c2, |
|
270 text = \small 5, markfield=b1, |
|
271 text = \small 2, markfield=Z1, |
|
272 setpieces={Na3}] |
|
273 |
|
274 \noindent |
|
275 Warnsdorf's rule states that the moves sould be tried out in the |
|
276 order |
|
277 |
|
278 \[ |
|
279 (0, 1), (0, 5), (2, 5), (3, 4), (3, 2) |
|
280 \] |
|
281 |
|
282 Whenever there are ties, the correspoding onward moves can be in any |
|
283 order. When calculating the number of onward moves for each field, we |
|
284 do not count moves that revisit any field already visited. |
|
285 |
|
286 \subsubsection*{Tasks (file knight3.scala)} |
|
287 |
|
288 \begin{itemize} |
|
289 \item[(3a)] orderered-moves |
|
290 |
|
291 \item[(3b)] first-closed tour heuristics; up to $6\times 6$ |
|
292 |
|
293 \item[(3c)] first tour heuristics; up to $50\times 50$ |
|
294 \end{itemize} |
119 |
295 |
120 \end{document} |
296 \end{document} |
121 |
297 |
122 %%% Local Variables: |
298 %%% Local Variables: |
123 %%% mode: latex |
299 %%% mode: latex |