\documentclass{article}

\usepackage{chessboard}

\usepackage[LSBC4,T1]{fontenc}

\usepackage{../style}

\begin{document}

\setchessboard{smallboard,

               zero,

               showmover=false,

               boardfontencoding=LSBC4,

               hlabelformat=\arabic{ranklabel},

               vlabelformat=\arabic{filelabel}}

\mbox{}\\[-18mm]\mbox{}

\section*{Coursework 7 (Scala, Knight's Tour)}

This coursework is about searching and backtracking, and 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. Make sure the files

you submit can be processed by just calling \texttt{scala

  <<filename.scala>>}.

\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.\medskip

\subsection*{Background}

The \textit{Knight's Tour Problem} is about finding a tour such that

the knight visits every field on an $n\times n$ chessboard once. For

example on a $5\times 5$ chessboard, a knight's tour is:

\chessboard[maxfield=d4, 

            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},

            text = \small 24, markfield=Z4,

            text = \small 11, markfield=a4,

            text = \small  6, markfield=b4,

            text = \small 17, markfield=c4,

            text = \small  0, markfield=d4,

            text = \small 19, markfield=Z3,

            text = \small 16, markfield=a3,

            text = \small 23, markfield=b3,

            text = \small 12, markfield=c3,

            text = \small  7, markfield=d3,

            text = \small 10, markfield=Z2,

            text = \small  5, markfield=a2,

            text = \small 18, markfield=b2,

            text = \small  1, markfield=c2,

            text = \small 22, markfield=d2,

            text = \small 15, markfield=Z1,

            text = \small 20, markfield=a1,

            text = \small  3, markfield=b1,

            text = \small  8, markfield=c1,

            text = \small 13, markfield=d1,

            text = \small  4, markfield=Z0,

            text = \small  9, markfield=a0,

            text = \small 14, markfield=b0,

            text = \small 21, markfield=c0,

            text = \small  2, markfield=d0

           ]

\noindent

The tour starts in the right-upper corner, then moves to field

$(3,2)$, then $(4,0)$ 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 \underline{not} closed (it is open) because the last

step on field $(0, 4)$ is not within the reach of the first step on

$(4, 4)$. It turns out there is no closed knight's tour on a $5\times

\chessboard[maxfield=e5, 

            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},

            text = \small 10, markfield=Z5,

            text = \small  5, markfield=a5,

            text = \small 18, markfield=b5,

            text = \small 25, markfield=c5,

            text = \small 16, markfield=d5,

            text = \small  7, markfield=e5,

            text = \small 31, markfield=Z4,

            text = \small 26, markfield=a4,

            text = \small  9, markfield=b4,

            text = \small  6, markfield=c4,

            text = \small 19, markfield=d4,

            text = \small 24, markfield=e4,

            % 4  11  30  17   8  15 

            text = \small  4, markfield=Z3,

            text = \small 11, markfield=a3,

            text = \small 30, markfield=b3,

            text = \small 17, markfield=c3,

            text = \small  8, markfield=d3,

            text = \small 15, markfield=e3,

            %29  32  27   0  23  20 

            text = \small 29, markfield=Z2,

            text = \small 32, markfield=a2,

            text = \small 27, markfield=b2,

            text = \small  0, markfield=c2,

            text = \small 23, markfield=d2,

            text = \small 20, markfield=e2,

            %12   3  34  21  14   1 

            text = \small 12, markfield=Z1,

            text = \small  3, markfield=a1,

            text = \small 34, markfield=b1,

            text = \small 21, markfield=c1,

            text = \small 14, markfield=d1,

            text = \small  1, markfield=e1,

            %33  28  13   2  35  22 

            text = \small 33, markfield=Z0,

            text = \small 28, markfield=a0,

            text = \small 13, markfield=b0,

            text = \small  2, markfield=c0,

            text = \small 35, markfield=d0,

            text = \small 22, markfield=e0,

            vlabel=false,

            hlabel=false

           ]

\noindent

where the 35th move can join up again with the 0th move.

chess, below are all potential moves indicated for two knights, one on

\chessboard[maxfield=g7,

            color=blue!50,

            linewidth=0.2em,

            shortenstart=0.5ex,

            shortenend=0.5ex,

            markstyle=cross,

            markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},

            color=red!50,

            markfields={f5, e6},

            setpieces={Ng7, Nb2}]

\subsection*{Part 1 (6 Marks)}

\[

\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,

\]

\noindent

Suppose the dimension of a chessboard is $n$, then a path is a

\emph{tour} if the length of the path is $n \times n$, each element

occurs only once in the path, and each move follows the rules of how a

knight moves (see above for the rules).

\subsubsection*{Tasks (file knight1.scala)}

\begin{itemize}

\item[(1a)] Implement a is-legal-move function that takes a dimension, a path

and a position as argument and tests whether the position is inside

\item[(1b)] Implement a legal-moves function that calculates for a

  placed on a circle, you should produce them starting from

  ``12-oclock'' following in clockwise order.  For example on an

  $8\times 8$ board for a knight on position $(2, 2)$ and otherwise

  positions

  \begin{center}

  \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}

  \end{center}

  \begin{center}

  \texttt{List((6,5), (5,6))}

\item[(1c)] Implement two recursive functions (count-tours and

  enum-tours). They each take a dimension and a path as

  starting from the given path. The first function counts all possible

  open tours (there can be none for certain board sizes) and the second

\end{itemize}

\subsubsection*{Tasks (file knight2.scala)}

\begin{itemize}

\item[(2a)] Implement a first-function. This function takes a list of

  positions and a function $f$ as arguments. The function $f$ takes a

  position as argument and produces an optional path. The idea behind

  the first-function is as follows:

  \[

  \begin{array}{lcl}

    f(x) & \textit{if}\;f(x) \not=\texttt{None}\\

                              \end{cases}

  \end{array}

  \]

\item[(2b)] Implement a first-tour function. Using the first-function

\subsection*{Part 2 (4 Marks)}

\chessboard[maxfield=g7,

            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},

            text = \small 3, markfield=Z5,

            text = \small 7, markfield=b5,

            text = \small 7, markfield=c4,

            text = \small 7, markfield=c2,

            text = \small 5, markfield=b1,

            text = \small 2, markfield=Z1,

            setpieces={Na3}]

\noindent

\[

(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)

\]

\noindent

Whenever there are ties, the correspoding onward moves can be in any

order.  When calculating the number of onward moves for each field, we

do not count moves that revisit any field already visited.

\subsubsection*{Tasks (file knight3.scala)}

\begin{itemize}

\item[(3a)] orderered-moves

\item[(3b)] first-closed tour heuristics; up to $6\times 6$

\item[(3c)] first tour heuristics; up to $50\times 50$

\end{itemize}  

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: