1 \documentclass{article}

     2 \usepackage{chessboard}

     3 \usepackage[LSBC4,T1]{fontenc}

     4 \let\clipbox\relax

     5 \usepackage{../style}

     6 \usepackage{disclaimer}

     7 

     8 \begin{document}

     9 

    10 \setchessboard{smallboard,

    11                zero,

    12                showmover=false,

    13                boardfontencoding=LSBC4,

    14                hlabelformat=\arabic{ranklabel},

    15                vlabelformat=\arabic{filelabel}}

    16 

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

    18 

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

    20 

    21 This coursework is worth 10\%. It is about searching and

    22 backtracking. The first part is due on 23 November at 11pm; the

    23 second, more advanced part, is due on 21 December at 11pm. You are

    24 asked to implement Scala programs that solve various versions of the

    25 \textit{Knight's Tour Problem} on a chessboard. Note the second part

    26 might include material you have not yet seen in the first two

    27 lectures. \bigskip

    28 

    29 \IMPORTANT{}

    30 Also note that the running time of each part will be restricted to a

    31 maximum of 360 seconds on my laptop: If you calculate a result once,

    32 try to avoid to calculate the result again. Feel free to copy any code

    33 you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and

    34 \texttt{knight3.scala}.

    35 

    36 \DISCLAIMER{}

    37 

    38 \subsection*{Background}

    39 

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

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

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

    43 

    44 \chessboard[maxfield=d4, 

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

    46             text = \small 24, markfield=Z4,

    47             text = \small 11, markfield=a4,

    48             text = \small  6, markfield=b4,

    49             text = \small 17, markfield=c4,

    50             text = \small  0, markfield=d4,

    51             text = \small 19, markfield=Z3,

    52             text = \small 16, markfield=a3,

    53             text = \small 23, markfield=b3,

    54             text = \small 12, markfield=c3,

    55             text = \small  7, markfield=d3,

    56             text = \small 10, markfield=Z2,

    57             text = \small  5, markfield=a2,

    58             text = \small 18, markfield=b2,

    59             text = \small  1, markfield=c2,

    60             text = \small 22, markfield=d2,

    61             text = \small 15, markfield=Z1,

    62             text = \small 20, markfield=a1,

    63             text = \small  3, markfield=b1,

    64             text = \small  8, markfield=c1,

    65             text = \small 13, markfield=d1,

    66             text = \small  4, markfield=Z0,

    67             text = \small  9, markfield=a0,

    68             text = \small 14, markfield=b0,

    69             text = \small 21, markfield=c0,

    70             text = \small  2, markfield=d0

    71            ]

    72            

    73 \noindent

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

    75 $(3,2)$, then $(4,0)$ and so on. There are no knight's tours on

    76 $2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every

    77 bigger board there is. 

    78 

    79 A knight's tour is called \emph{closed}, if the last step in the tour

    80 is within a knight's move to the beginning of the tour. So the above

    81 knight's tour is \underline{not} closed because the last

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

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

    84 5$ board. But there are on a $6\times 6$ board and on bigger ones, for

    85 example

    86 

    87 \chessboard[maxfield=e5, 

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

    89             text = \small 10, markfield=Z5,

    90             text = \small  5, markfield=a5,

    91             text = \small 18, markfield=b5,

    92             text = \small 25, markfield=c5,

    93             text = \small 16, markfield=d5,

    94             text = \small  7, markfield=e5,

    95             text = \small 31, markfield=Z4,

    96             text = \small 26, markfield=a4,

    97             text = \small  9, markfield=b4,

    98             text = \small  6, markfield=c4,

    99             text = \small 19, markfield=d4,

   100             text = \small 24, markfield=e4,

   101             % 4  11  30  17   8  15 

   102             text = \small  4, markfield=Z3,

   103             text = \small 11, markfield=a3,

   104             text = \small 30, markfield=b3,

   105             text = \small 17, markfield=c3,

   106             text = \small  8, markfield=d3,

   107             text = \small 15, markfield=e3,

   108             %29  32  27   0  23  20 

   109             text = \small 29, markfield=Z2,

   110             text = \small 32, markfield=a2,

   111             text = \small 27, markfield=b2,

   112             text = \small  0, markfield=c2,

   113             text = \small 23, markfield=d2,

   114             text = \small 20, markfield=e2,

   115             %12   3  34  21  14   1 

   116             text = \small 12, markfield=Z1,

   117             text = \small  3, markfield=a1,

   118             text = \small 34, markfield=b1,

   119             text = \small 21, markfield=c1,

   120             text = \small 14, markfield=d1,

   121             text = \small  1, markfield=e1,

   122             %33  28  13   2  35  22 

   123             text = \small 33, markfield=Z0,

   124             text = \small 28, markfield=a0,

   125             text = \small 13, markfield=b0,

   126             text = \small  2, markfield=c0,

   127             text = \small 35, markfield=d0,

   128             text = \small 22, markfield=e0,

   129             vlabel=false,

   130             hlabel=false

   131            ]

   132 

   133 

   134 \noindent

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

   136 

   137 If you cannot remember how a knight moves in chess, or never played

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

   139 field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):

   140 

   141 

   142 \chessboard[maxfield=g7,

   143             color=blue!50,

   144             linewidth=0.2em,

   145             shortenstart=0.5ex,

   146             shortenend=0.5ex,

   147             markstyle=cross,

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

   149             color=red!50,

   150             markfields={f5, e6},

   151             setpieces={Ng7, Nb2}]

   152 

   153 \subsection*{Part 1 (7 Marks)}

   154 

   155 You are asked to implement the knight's tour problem such that the

   156 dimension of the board can be changed.  Therefore most functions will

   157 take the dimension of the board as an argument.  The fun with this

   158 problem is that even for small chessboard dimensions it has already an

   159 incredibly large search space---finding a tour is like finding a

   160 needle in a haystack. In the first task we want to see how far we get

   161 with exhaustively exploring the complete search space for small

   162 chessboards.\medskip

   163 

   164 \noindent

   165 Let us first fix the basic datastructures for the implementation.  The

   166 board dimension is an integer (we will never go beyond board sizes of

   167 $40 \times 40$).  A \emph{position} (or field) on the chessboard is

   168 a pair of integers, like $(0, 0)$. A \emph{path} is a list of

   169 positions. The first (or 0th move) in a path is the last element in

   170 this list; and the last move in the path is the first element. For

   171 example the path for the $5\times 5$ chessboard above is represented

   172 by

   173 

   174 \[

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

   176   $\underbrace{\texttt{(2, 3)}}_{23}$, ...,

   177   $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}

   178 \]

   179 

   180 \noindent

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

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

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

   184 knight moves (see above for the rules).

   185 

   186 

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

   188 

   189 \begin{itemize}

   190 \item[(1a)] Implement an \texttt{is\_legal\_move} function that takes a

   191   dimension, a path and a position as arguments and tests whether the

   192   position is inside the board and not yet element in the

   193   path. \hfill[1 Mark]

   194 

   195 \item[(1b)] Implement a \texttt{legal\_moves} function that calculates for a

   196   position all legal onward moves. If the onward moves are

   197   placed on a circle, you should produce them starting from

   198   ``12-o'clock'' following in clockwise order.  For example on an

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

   200   empty board, the legal-moves function should produce the onward

   201   positions in this order:

   202 

   203   \begin{center}

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

   205   \end{center}

   206 

   207   If the board is not empty, then maybe some of the moves need to be

   208   filtered out from this list.  For a knight on field $(7, 7)$ and an

   209   empty board, the legal moves are

   210 

   211   \begin{center}

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

   213   \end{center}

   214   \mbox{}\hfill[1 Mark]

   215 

   216 \item[(1c)] Implement two recursive functions (\texttt{count\_tours} and

   217   \texttt{enum\_tours}). They each take a dimension and a path as

   218   arguments. They exhaustively search for tours starting

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

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

   221   collects all tours in a list of paths.\hfill[2 Marks]

   222 \end{itemize}

   223 

   224 \noindent \textbf{Test data:} For the marking, the functions in (1c)

   225 will be called with board sizes up to $5 \times 5$. If you search

   226 for tours on a $5 \times 5$ board starting only from field $(0, 0)$,

   227 there are 304 of tours. If you try out every field of a $5 \times

   228 5$-board as a starting field and add up all tours, you obtain

   229 1728. A $6\times 6$ board is already too large to be searched

   230 exhaustively.\footnote{For your interest, the number of tours on

   231   $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,

   232   19591828170979904, respectively.}\bigskip

   233 

   234 \noindent

   235 \textbf{Hints:} useful list functions: \texttt{.contains(..)} checks

   236 whether an element is in a list, \texttt{.flatten} turns a list of

   237 lists into just a list, \texttt{\_::\_} puts an element on the head of

   238 the list, \texttt{.head} gives you the first element of a list (make

   239 sure the list is not \texttt{Nil}).

   240 

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

   242 

   243 \begin{itemize}

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

   245   positions and a function $f$ as arguments; $f$ is the name we give to

   246   this argument). The function $f$ takes a position as argument and

   247   produces an optional path. So $f$'s type is \texttt{Pos =>

   248     Option[Path]}. The idea behind the \texttt{first}-function is as follows:

   249 

   250   \[

   251   \begin{array}{lcl}

   252   \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\  

   253   \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}

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

   255     \textit{first}(xs, f) & \textit{otherwise}\\

   256                               \end{cases}

   257   \end{array}

   258   \]

   259 

   260   \noindent That is, we want to find the first position where the

   261   result of $f$ is not \texttt{None}, if there is one. Note that

   262   `inside' \texttt{first}, you do not (need to) know anything about

   263   the argument $f$ except its type, namely \texttt{Pos =>

   264     Option[Path]}. There is one additional point however you should

   265   take into account when implementing \texttt{first}: you will need to

   266   calculate what the result of $f(x)$ is; your code should do this

   267   only \textbf{once} and for as \textbf{few} elements in the list as

   268   possible! Do not calculate $f(x)$ for all elements and then see which 

   269   is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]

   270   

   271 \item[(2b)] Implement a \texttt{first\_tour} function that uses the

   272   \texttt{first}-function from (2a), and searches recursively for a tour.

   273   As there might not be such a tour at all, the \texttt{first\_tour} function

   274   needs to return a value of type

   275   \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]

   276 \end{itemize}

   277 

   278 \noindent

   279 \textbf{Testing:} The \texttt{first\_tour} function will be called with board

   280 sizes of up to $8 \times 8$.

   281 \bigskip

   282 

   283 \noindent

   284 \textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a

   285 list according to a boolean function; a useful option function:

   286 \texttt{.isDefined} returns true, if an option is \texttt{Some(..)};

   287 anonymous functions can be constructed using \texttt{(x:Int) => ...},

   288 this functions takes an \texttt{Int} as an argument.

   289 

   290 

   291 %%\newpage

   292 \subsection*{Part 2 (3 Marks)}

   293 

   294 As you should have seen in Part 1, a naive search for tours beyond

   295 $8 \times 8$ boards and also searching for closed tours even on small

   296 boards takes too much time. There is a heuristic, called \emph{Warnsdorf's

   297 Rule} that can speed up finding a tour. This heuristic states that a

   298 knight is moved so that it always proceeds to the field from which the

   299 knight will have the \underline{fewest} onward moves.  For example for

   300 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible

   301 onward moves, namely 2.

   302 

   303 \chessboard[maxfield=g7,

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

   305             text = \small 3, markfield=Z5,

   306             text = \small 7, markfield=b5,

   307             text = \small 7, markfield=c4,

   308             text = \small 7, markfield=c2,

   309             text = \small 5, markfield=b1,

   310             text = \small 2, markfield=Z1,

   311             setpieces={Na3}]

   312 

   313 \noindent

   314 Warnsdorf's Rule states that the moves on the board above should be

   315 tried in the order

   316 

   317 \[

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

   319 \]

   320 

   321 \noindent

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

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

   324 do not count moves that revisit any field already visited.

   325 

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

   327 

   328 \begin{itemize}

   329 \item[(3a)] Write a function \texttt{ordered\_moves} that calculates a list of

   330   onward moves like in (1b) but orders them according to the

   331   Warnsdorf’s Rule. That means moves with the fewest legal onward moves

   332   should come first (in order to be tried out first). \hfill[1 Mark]

   333   

   334 \item[(3b)] Implement a \texttt{first\_closed-tour\_heuristic}

   335   function that searches for a

   336   \textbf{closed} tour on a $6\times 6$ board. It should use the

   337   \texttt{first}-function from (2a) and tries out onward moves according to

   338   the \texttt{ordered\_moves} function from (3a). It is more likely to find

   339   a solution when started in the middle of the board (that is

   340   position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]

   341 

   342 \item[(3c)] Implement a \texttt{first\_tour\_heuristic} function

   343   for boards up to

   344   $40\times 40$.  It is the same function as in (3b) but searches for

   345   tours (not just closed tours). You have to be careful to write a

   346   tail-recursive function of the \texttt{first\_tour\_heuristic} function

   347   otherwise you will get problems with stack-overflows.\\

   348   \mbox{}\hfill[1 Mark]

   349 \end{itemize}  

   350 \bigskip

   351 

   352 \noindent

   353 \textbf{Hints:} a useful list function: \texttt{.sortBy} sorts a list

   354 according to a component given by the function; a function can be

   355 tested to be tail recursive by annotation \texttt{@tailrec}, which is

   356 made available by importing \texttt{scala.annotation.tailrec}.

   357 

   358 

   359 

   360 \end{document}

   361 

   362 %%% Local Variables: 

   363 %%% mode: latex

   364 %%% TeX-master: t

   365 %%% End: