\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
5$ board. But there are on a $6\times 6$ board, for example

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

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 $(2, 2)$ (blue) and another on $(7, 7)$ (red):


\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)}

We will implement the knight's tour problem such that we can change
quickly the dimension of the chessboard. The fun with this problem is
that even for small chessbord dimensions it has already an incredably
large search space---finding a tour is like finding a needle in a
haystack. In the first part we want to see far we get with
exhaustively exploring the complete search space for small dimensions.

Let us first fix the basic datastructures for the implementation.  A
\emph{position} (or field) on the chessboard is a pair of integers. A
\emph{path} is a list of positions. The first (or 0th move) in a path
should be the last element in this list; and the last move is the
first element. For example the path for the $5\times 5$ chessboard
above is represented by

\[
\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
  $\underbrace{\texttt{(2, 3)}}_{23}$, ..., (3, 2), $\underbrace{\texttt{(4, 4)}}_0$)}
\]

\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
the board and not yet element in the path.

\item[(1b)] Implement a legal-moves function that calculates for a
  position all legal follow-on moves. If the follow-on moves are
  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
  empty board, the legal-moves function should produce the follow-on
  positions

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

  If the board is not empty, then maybe some of the moves need to be filtered out from this list.
  For a knight on field $(7, 7)$ and an empty board, the legal moves
  are

  \begin{center}
  \texttt{List((6,5), (5,6))}
  \end{center}  

\item[(1c)] Implement two recursive functions (count-tours and
  enum-tours). They each take a dimension and a path as
  arguments. They exhaustively search for \underline{open} tours
  starting from the given path. The first function counts all possible
  open tours (there can be none for certain board sizes) and the second
  collects all open tours in a list of paths.
\end{itemize}

\noindent \textbf{Test data:} For the marking, these functions will be
called with board sizes up to $5 \times 5$. If you only search for
open tours starting from field $(0, 0)$, there are 304 of them. If you
try out every field of a $5 \times 5$-board as a starting field and
add up all open tours, you obtain 1728. A $6\times 6$ board is already
too large to search exhaustively: the number of open tours on
$6\times 6$, $7\times 7$ and $8\times 8$ are

\begin{center}
\begin{tabular}{ll}  
  $6\times 6$ & 6637920\\
  $7\times 7$ & 165575218320\\
  $8\times 8$ & 19591828170979904
\end{tabular}
\end{center}

\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}
  first(\texttt{Nil}, f) & \dn & \texttt{None}\\  
  first(x\!::\!xs, f) & \dn & \begin{cases}
    f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
    first(xs, f) & \textit{otherwise}\\
                              \end{cases}
  \end{array}
  \]

\item[(2b)] Implement a first-tour function. Using the first-function
  from (2a), search recursively for an open tour. Only use the field
  $(0, 0)$ as a starting field of the tour. As there might not be such
  a tour at all, the first-tour function needs to return an
  \texttt{Option[Path]}. For the marking, this function will be called
  with board sizes up to $8 \times 8$.
\end{itemize}  


\subsection*{Part 2 (4 Marks)}

For open tours beyond $8 \times 8$ boards and also for searching for
closed tours, an heuristic (called Warnsdorf's rule) needs to be
implemented. This rule states that a knight is moved so that it
always proceeds to the square from which the knight will have the
fewest onward moves.  For example for a knight on field $(1, 3)$,
the field $(0, 1)$ has the fewest possible onward moves.

\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
Warnsdorf's rule states that the moves sould be tried out in the
order

\[
(0, 1), (0, 5), (2, 5), (3, 4), (3, 2)
\]

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: