diff -r 2c96963b2e5c -r c6fe374a5fca cws/cw02.tex --- a/cws/cw02.tex Fri Nov 11 16:44:19 2016 +0000 +++ b/cws/cw02.tex Sat Nov 12 15:20:56 2016 +0000 @@ -1,8 +1,7 @@ \documentclass{article} -\usepackage{../style} \usepackage{chessboard} \usepackage[LSBC4,T1]{fontenc} - +\usepackage{../style} \begin{document} @@ -16,12 +15,24 @@ \section*{Coursework 7 (Scala, Knight's Tour)} -This coursework is worth 10\% and is due on 21 November at 11pm. You -are asked to implement a Scala program that solves the \textit{knight's - tour problem} on an $n\times n$ chessboard. This problem is about -finding a tour such that the knight visits every field on the -chessboard once. One a $5\times 5$ chessboard, a knight's tour -is as follows: +This coursework is worth 10\%. The first part is due on 23 November +at 11pm; the second, more advanced part, is due on 30 November at +11pm. You are asked to implement Scala programs that solve various +versions of the \textit{Knight's Tour Problem} on a chessboard. + +\subsection*{Disclaimer} + +It should be understood that the work you submit represents +your own effort. You have not copied from anyone else. An +exception is the Scala code I showed during the lectures or +uploaded to KEATS, which you can freely use.\bigskip + +\subsection*{Background} + +The \textit{Knight's Tour Problem} is about finding a tour such that +the knight visits every field on a $n\times n$ chessboard once. For +example on a $5\times 5$ chessboard, a knight's tour is as follows: + \chessboard[maxfield=e5, pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text}, @@ -53,18 +64,23 @@ ] \noindent -The tour starts in the left-upper corner, then moves to field $(4,3)$, -then $(5,1)$ and so on. A knight's tour is called \emph{closed}, if +The tour starts in the right-upper corner, then moves to field $(4,3)$, +then $(5,1)$ and so on. There are no knight's tours on $2\times 2$, $3\times 3$ +and $4\times 4$ chessboards, but for every bigger board there is. + + +A knight's tour is called \emph{closed}, if the last step in the tour is within a knight's move to the beginning -of the tour. So the above knight's tour is not closed (that is it is +of the tour. So the above knight's tour is \underline{not} closed (it is open) because the last step on field $(1, 5)$ is not within the reach of the first step on $(5, 5)$. It turns out there is no closed -knight's tour on a $5\times 5$ board. But there is one on a $6\times -6$ board. +knight's tour on a $5\times 5$ board. But there are on a $6\times +6$ board.\bigskip -If you cannot remember how a knight moved in chess, below are all -potential moves indicated for two knights, one on field $(3, 3)$ and -another on $(8, 8)$: +\noindent +If you cannot remember how a knight moved in chess, or never played +chess, below are all potential moves indicated for two knights, one on +field $(3, 3)$ and another on $(8, 8)$: \chessboard[color=blue!50, @@ -78,12 +94,6 @@ setpieces={Nh8, Nc3}] -\subsubsection*{Disclaimer} - -It should be understood that the work you submit represents -your own effort. You have not copied from anyone else. An -exception is the Scala code I showed during the lectures or -uploaded to KEATS, which you can freely use.\bigskip \subsubsection*{Task}