1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{../style} |
|
3 \usepackage{chessboard} |
2 \usepackage{chessboard} |
4 \usepackage[LSBC4,T1]{fontenc} |
3 \usepackage[LSBC4,T1]{fontenc} |
5 |
4 \usepackage{../style} |
6 |
5 |
7 \begin{document} |
6 \begin{document} |
8 |
7 |
9 \setchessboard{smallboard, |
8 \setchessboard{smallboard, |
10 showmover=false, |
9 showmover=false, |
14 |
13 |
15 |
14 |
16 |
15 |
17 \section*{Coursework 7 (Scala, Knight's Tour)} |
16 \section*{Coursework 7 (Scala, Knight's Tour)} |
18 |
17 |
19 This coursework is worth 10\% and is due on 21 November at 11pm. You |
18 This coursework is worth 10\%. The first part is due on 23 November |
20 are asked to implement a Scala program that solves the \textit{knight's |
19 at 11pm; the second, more advanced part, is due on 30 November at |
21 tour problem} on an $n\times n$ chessboard. This problem is about |
20 11pm. You are asked to implement Scala programs that solve various |
22 finding a tour such that the knight visits every field on the |
21 versions of the \textit{Knight's Tour Problem} on a chessboard. |
23 chessboard once. One a $5\times 5$ chessboard, a knight's tour |
22 |
24 is as follows: |
23 \subsection*{Disclaimer} |
|
24 |
|
25 It should be understood that the work you submit represents |
|
26 your own effort. You have not copied from anyone else. An |
|
27 exception is the Scala code I showed during the lectures or |
|
28 uploaded to KEATS, which you can freely use.\bigskip |
|
29 |
|
30 \subsection*{Background} |
|
31 |
|
32 The \textit{Knight's Tour Problem} is about finding a tour such that |
|
33 the knight visits every field on a $n\times n$ chessboard once. For |
|
34 example on a $5\times 5$ chessboard, a knight's tour is as follows: |
|
35 |
25 |
36 |
26 \chessboard[maxfield=e5, |
37 \chessboard[maxfield=e5, |
27 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
38 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, |
28 text = \bf\small 24, markfield=a5, |
39 text = \bf\small 24, markfield=a5, |
29 text = \small 11, markfield=b5, |
40 text = \small 11, markfield=b5, |
51 text = \small 21, markfield=d1, |
62 text = \small 21, markfield=d1, |
52 text = \small 2, markfield=e1 |
63 text = \small 2, markfield=e1 |
53 ] |
64 ] |
54 |
65 |
55 \noindent |
66 \noindent |
56 The tour starts in the left-upper corner, then moves to field $(4,3)$, |
67 The tour starts in the right-upper corner, then moves to field $(4,3)$, |
57 then $(5,1)$ and so on. A knight's tour is called \emph{closed}, if |
68 then $(5,1)$ and so on. There are no knight's tours on $2\times 2$, $3\times 3$ |
|
69 and $4\times 4$ chessboards, but for every bigger board there is. |
|
70 |
|
71 |
|
72 A knight's tour is called \emph{closed}, if |
58 the last step in the tour is within a knight's move to the beginning |
73 the last step in the tour is within a knight's move to the beginning |
59 of the tour. So the above knight's tour is not closed (that is it is |
74 of the tour. So the above knight's tour is \underline{not} closed (it is |
60 open) because the last step on field $(1, 5)$ is not within the reach |
75 open) because the last step on field $(1, 5)$ is not within the reach |
61 of the first step on $(5, 5)$. It turns out there is no closed |
76 of the first step on $(5, 5)$. It turns out there is no closed |
62 knight's tour on a $5\times 5$ board. But there is one on a $6\times |
77 knight's tour on a $5\times 5$ board. But there are on a $6\times |
63 6$ board. |
78 6$ board.\bigskip |
64 |
79 |
65 If you cannot remember how a knight moved in chess, below are all |
80 \noindent |
66 potential moves indicated for two knights, one on field $(3, 3)$ and |
81 If you cannot remember how a knight moved in chess, or never played |
67 another on $(8, 8)$: |
82 chess, below are all potential moves indicated for two knights, one on |
|
83 field $(3, 3)$ and another on $(8, 8)$: |
68 |
84 |
69 |
85 |
70 \chessboard[color=blue!50, |
86 \chessboard[color=blue!50, |
71 linewidth=0.2em, |
87 linewidth=0.2em, |
72 shortenstart=0.5ex, |
88 shortenstart=0.5ex, |