1 % !TEX program = xelatex

     2 \documentclass{article}

     3 \usepackage{chessboard}

     4 \usepackage[LSBC4,T1]{fontenc}

     5 \let\clipbox\relax

     6 \usepackage{../styles/style}

     7 \usepackage{../styles/langs}

     8 \usepackage{disclaimer}

     9 \usepackage{ulem}

    10 

    11 \begin{document}

    12 

    13 \setchessboard{smallboard,

    14                zero,

    15                showmover=false,

    16                boardfontencoding=LSBC4,

    17                hlabelformat=\arabic{ranklabel},

    18                vlabelformat=\arabic{filelabel}}

    19 

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

    21 

    22 \section*{Main Part 4 (Scala, 11 Marks)}

    23 

    24 \mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\

    25 \mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\

    26 \mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\

    27 \mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\medskip\bigskip

    28 

    29 \noindent

    30 This part is about searching and backtracking. You are asked to

    31 implement Scala programs that solve various versions of the

    32 \textit{Knight's Tour Problem} on a chessboard.

    33 \medskip 

    34 

    35 % Note the core, more advanced, part might include material you have not

    36 %yet seen in the first three lectures. \bigskip

    37 

    38 \IMPORTANTNONE{}

    39 

    40 \noindent

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

    42 maximum of 30 seconds on my laptop: If you calculate a result once,

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

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

    45 \texttt{knight3.scala}.

    46 

    47 \DISCLAIMER{}

    48 

    49 \subsection*{Background}

    50 

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

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

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

    54 

    55 \chessboard[maxfield=d4, 

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

    57             text = \small 24, markfield=Z4,

    58             text = \small 11, markfield=a4,

    59             text = \small  6, markfield=b4,

    60             text = \small 17, markfield=c4,

    61             text = \small  0, markfield=d4,

    62             text = \small 19, markfield=Z3,

    63             text = \small 16, markfield=a3,

    64             text = \small 23, markfield=b3,

    65             text = \small 12, markfield=c3,

    66             text = \small  7, markfield=d3,

    67             text = \small 10, markfield=Z2,

    68             text = \small  5, markfield=a2,

    69             text = \small 18, markfield=b2,

    70             text = \small  1, markfield=c2,

    71             text = \small 22, markfield=d2,

    72             text = \small 15, markfield=Z1,

    73             text = \small 20, markfield=a1,

    74             text = \small  3, markfield=b1,

    75             text = \small  8, markfield=c1,

    76             text = \small 13, markfield=d1,

    77             text = \small  4, markfield=Z0,

    78             text = \small  9, markfield=a0,

    79             text = \small 14, markfield=b0,

    80             text = \small 21, markfield=c0,

    81             text = \small  2, markfield=d0

    82            ]

    83            

    84 \noindent

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

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

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

    88 bigger board there is. 

    89 

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

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

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

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

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

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

    96 example

    97 

    98 \chessboard[maxfield=e5, 

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

   100             text = \small 10, markfield=Z5,

   101             text = \small  5, markfield=a5,

   102             text = \small 18, markfield=b5,

   103             text = \small 25, markfield=c5,

   104             text = \small 16, markfield=d5,

   105             text = \small  7, markfield=e5,

   106             text = \small 31, markfield=Z4,

   107             text = \small 26, markfield=a4,

   108             text = \small  9, markfield=b4,

   109             text = \small  6, markfield=c4,

   110             text = \small 19, markfield=d4,

   111             text = \small 24, markfield=e4,

   112             % 4  11  30  17   8  15 

   113             text = \small  4, markfield=Z3,

   114             text = \small 11, markfield=a3,

   115             text = \small 30, markfield=b3,

   116             text = \small 17, markfield=c3,

   117             text = \small  8, markfield=d3,

   118             text = \small 15, markfield=e3,

   119             %29  32  27   0  23  20 

   120             text = \small 29, markfield=Z2,

   121             text = \small 32, markfield=a2,

   122             text = \small 27, markfield=b2,

   123             text = \small  0, markfield=c2,

   124             text = \small 23, markfield=d2,

   125             text = \small 20, markfield=e2,

   126             %12   3  34  21  14   1 

   127             text = \small 12, markfield=Z1,

   128             text = \small  3, markfield=a1,

   129             text = \small 34, markfield=b1,

   130             text = \small 21, markfield=c1,

   131             text = \small 14, markfield=d1,

   132             text = \small  1, markfield=e1,

   133             %33  28  13   2  35  22 

   134             text = \small 33, markfield=Z0,

   135             text = \small 28, markfield=a0,

   136             text = \small 13, markfield=b0,

   137             text = \small  2, markfield=c0,

   138             text = \small 35, markfield=d0,

   139             text = \small 22, markfield=e0,

   140             vlabel=false,

   141             hlabel=false

   142            ]

   143 

   144 

   145 \noindent

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

   147 

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

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

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

   151 

   152 {\chessboard[maxfield=g7,

   153             color=blue!50,

   154             linewidth=0.2em,

   155             shortenstart=0.5ex,

   156             shortenend=0.5ex,

   157             markstyle=cross,

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

   159             color=red!50,

   160             markfields={f5, e6},

   161             setpieces={Ng7, Nb2},

   162             boardfontsize=12pt,labelfontsize=9pt]}

   163 

   164 \subsection*{Reference Implementation}

   165 

   166 %\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from K%EATS. The one

   167 %supplied with github does not contain the correct code. See Scala coursework

   168 %section on KEATS.}\medskip

   169 

   170 \noindent

   171 This Scala part comes with three reference implementations in form of

   172 \texttt{jar}-files. This allows you to run any test cases on your own

   173 computer. For example you can call Scala on the command line with the

   174 option \texttt{-cp knight1.jar} and then query any function from the

   175 \texttt{knight1.scala} template file. As usual you have to

   176 prefix the calls with \texttt{M4a}, \texttt{M4b}, \texttt{M4c} and \texttt{M4d}.

   177 Since some of the calls are time sensitive, I included some timing

   178 information. For example

   179 

   180 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

   181 $ scala -cp knight1.jar

   182 scala> M4a.enum_tours(5, List((0, 0))).length

   183 Time needed: 1.722 secs.

   184 res0: Int = 304

   185 

   186 scala> M4a.print_board(8, M4a.first_tour(8, List((0, 0))).get)

   187 Time needed: 15.411 secs.

   188 

   189  51  46  55  44  53   4  21  12 

   190  56  43  52   3  22  13  24   5 

   191  47  50  45  54  25  20  11  14 

   192  42  57   2  49  40  23   6  19 

   193  35  48  41  26  61  10  15  28 

   194  58   1  36  39  32  27  18   7 

   195  37  34  31  60   9  62  29  16 

   196   0  59  38  33  30  17   8  63 

   197 \end{lstlisting}%$

   198 

   199 

   200 \subsection*{Hints}

   201 

   202 \noindent

   203 Useful list functions: \texttt{.contains(..)} checks

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

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

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

   207 sure the list is not \texttt{Nil}); a useful option function:

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

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

   210 this function takes an \texttt{Int} as an argument; 

   211 a useful list function: \texttt{.sortBy} sorts a list

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

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

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

   215 

   216 

   217 %%\newpage

   218 

   219 \subsection*{Tasks}

   220 

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

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

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

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

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

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

   227 with exhaustively exploring the complete search space for small

   228 chessboards.\medskip

   229 

   230 \noindent

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

   232 board dimension is an integer.

   233 A \emph{position} (or field) on the chessboard is

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

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

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

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

   238 by

   239 

   240 \[

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

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

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

   244 \]

   245 

   246 \noindent

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

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

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

   250 knight moves (see above for the rules).

   251 

   252 

   253 \subsubsection*{Task 1 (file knight1.scala)}

   254 

   255 

   256 

   257 \begin{itemize}

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

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

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

   261   path. \hfill[1 Mark]

   262 

   263 \item[(2)] Implement a \texttt{legal\_moves} function that calculates for a

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

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

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

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

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

   269   positions in this order:

   270 

   271   \begin{center}

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

   273   \end{center}

   274 

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

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

   277   empty board, the legal moves are

   278 

   279   \begin{center}

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

   281   \end{center}

   282   \mbox{}\hfill[1 Mark]

   283 

   284 \item[(3)] Implement two recursive functions (\texttt{count\_tours} and

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

   286   arguments. They exhaustively search for tours starting

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

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

   289   collects all tours in a list of paths. These functions will be

   290   called with a path containing a single position---the starting field.

   291   They are expected to extend this path so as to find all tours starting

   292   from the given position.\\

   293   \mbox{}\hfill[1 Mark]

   294 \end{itemize}

   295   

   296 \noindent \textbf{Test data:} For the marking, the functions in (3)

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

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

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

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

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

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

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

   304   19591828170979904, respectively.}\smallskip

   305 

   306 \begin{itemize}

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

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

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

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

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

   312 

   313   \[

   314   \begin{array}{lcl}

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

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

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

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

   319                               \end{cases}

   320   \end{array}

   321   \]

   322 

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

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

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

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

   327     Option[Path]}. If you want to find out what the result of $f$ is

   328   on a particular argument, say $x$, you can just write $f(x)$. 

   329   There is one additional point however you should

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

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

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

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

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

   335   

   336 \item[(5)] Implement a \texttt{first\_tour} function that uses the

   337   \texttt{first}-function from (4), and searches recursively for single tour.

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

   339   needs to return a value of type

   340   \texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark]  

   341 \end{itemize}

   342 

   343 \noindent

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

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

   346 \bigskip

   347 

   348 %%\newpage

   349 \subsubsection*{Task 2 (file knight2.scala)}

   350 

   351 \noindent

   352 As you should have seen in the earlier parts, a naive search for tours beyond

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

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

   355 Rule} that can speed up finding a tour. This heuristics states that a

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

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

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

   359 onward moves, namely 2.

   360 

   361 \chessboard[maxfield=g7,

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

   363             text = \small 3, markfield=Z5,

   364             text = \small 7, markfield=b5,

   365             text = \small 7, markfield=c4,

   366             text = \small 7, markfield=c2,

   367             text = \small 5, markfield=b1,

   368             text = \small 2, markfield=Z1,

   369             setpieces={Na3}]

   370 

   371 \noindent

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

   373 tried in the order

   374 

   375 \[

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

   377 \]

   378 

   379 \noindent

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

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

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

   383 

   384 \begin{itemize}

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

   386   onward moves like in (2) but orders them according to 

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

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

   389   

   390 \item[(7)] Implement a \texttt{first\_closed\_tour\_heuristics}

   391   function that searches for a single

   392   \textbf{closed} tour on a $6\times 6$ board. It should try out

   393   onward moves according to

   394   the \texttt{ordered\_moves} function from (6). It is more likely to find

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

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

   397 

   398 \item[(8)] Implement a \texttt{first\_tour\_heuristics} function

   399   for boards up to

   400   $30\times 30$.  It is the same function as in (7) but searches for

   401   tours (not just closed tours). It might be called with any field on the

   402   board as starting field.\\

   403   %You have to be careful to write a

   404   %tail-recursive function of the \texttt{first\_tour\_heuristics} function

   405   %otherwise you will get problems with stack-overflows.\\

   406   \mbox{}\hfill[1 Mark]

   407 \end{itemize}    

   408 

   409 \subsubsection*{Task 3 (file knight3.scala)}

   410 \begin{itemize}

   411 \item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is

   412   the same function as in (8), \textbf{but} should be able to

   413   deal with boards up to

   414   $70\times 70$ \textbf{within 30 seconds} (on my laptop). This will be tested

   415   by starting from field $(0, 0)$. You have to be careful to

   416   write a tail-recursive function otherwise you will get problems

   417   with stack-overflows. Please observe the requirements about

   418   the submissions: no tricks involving \textbf{.par}.\medskip

   419 

   420   The timelimit of 30 seconds is with respect to the laptop on which the

   421   marking will happen. You can roughly estimate how well your

   422   implementation performs by running \texttt{knight3.jar} on your

   423   computer. For example the reference implementation shows

   424   on my laptop:

   425   

   426   \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

   427 $ scala -cp knight3.jar

   428   

   429 scala> M4c.tour_on_mega_board(70, List((0, 0)))

   430 Time needed: 9.484 secs.

   431 ...<<long_list>>...

   432 \end{lstlisting}%$

   433 

   434   \mbox{}\hfill[1 Mark]

   435 \end{itemize}

   436 

   437 \subsubsection*{Task 4 (file knight4.scala)}

   438 \begin{itemize}

   439 \item[(10)] In this task we want to solve the problem of finding a single

   440   tour (if there exists one) on what is sometimes called ``mutilated''

   441   chessboards, for example rectangular chessbords or chessboards where

   442   fields are missing. For this implement a search function

   443 

   444   \begin{center}

   445     \begin{tabular}{@{}l@{}}

   446     \texttt{def one\_tour\_pred(dim: Int, path: Path,}\\

   447       \texttt{\phantom{def one\_tour\_pred(}n: Int, f: Pos => Boolean): Option[Path]}

   448       \end{tabular}

   449   \end{center}

   450 

   451   which has, like before, the dimension and current path as arguments,

   452   and in addtion it takes an integer, which specifies the length of

   453   the longest path (or length of the path after which the search

   454   should backtrack), and a function from positions to Booleans. This

   455   function acts as a predicate in order to restrict which onward legal

   456   moves should be considered in the search. The function

   457   \texttt{one\_tour\_pred} should return a single tour

   458   (\texttt{Some}-case), if one or more tours exist, and \texttt{None}, if no

   459   tour exists. For example when called with 

   460 

   461   \begin{center}

   462   \texttt{one\_tour\_pred(7, List((0, 0)), 35, x => x.\_1 < 5)}

   463   \end{center}  

   464 

   465   we are looking for a tour starting from position \texttt{(0,0)} on a

   466   7 $\times$ 5 board, where the maximum length of the path is 35. The

   467   predicate \texttt{x => x.\_1 < 5} ensures that no position with an

   468   x-coordinate bigger than 4 is considered. One possible solution is

   469 

   470   \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

   471    0   13   22   33   28   11   20 

   472   23   32    1   12   21   34   27 

   473   14    7   16   29    2   19   10 

   474   31   24    5    8   17   26    3 

   475    6   15   30   25    4    9   18 

   476   -1   -1   -1   -1   -1   -1   -1 

   477   -1   -1   -1   -1   -1   -1   -1

   478 \end{lstlisting}%$

   479 

   480 where \texttt{print\_board} prints a \texttt{-1} for all fields that

   481 have not been visited.

   482 

   483   \mbox{}\hfill[2 Marks]

   484 \end{itemize}

   485 

   486 

   487 

   488 \end{document}

   489 

   490 %%% Local Variables: 

   491 %%% mode: latex

   492 %%% TeX-master: t

   493 %%% End: