1 % !TEX program = xelatex

     2 \documentclass{article}

     3 \usepackage{chessboard}

     4 \usepackage[LSBC4,T1]{fontenc}

     5 \let\clipbox\relax

     6 \usepackage{../style}

     7 \usepackage{../langs}

     8 \usepackage{disclaimer}

     9 

    10 \begin{document}

    11 

    12 \setchessboard{smallboard,

    13                zero,

    14                showmover=false,

    15                boardfontencoding=LSBC4,

    16                hlabelformat=\arabic{ranklabel},

    17                vlabelformat=\arabic{filelabel}}

    18 

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

    20 

    21 \section*{Preliminary and Core Part 9 (Scala, 4 + 6 Marks)}

    22 

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

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

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

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

    27 

    28 \noindent

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

    30 implement Scala programs that solve various versions of the

    31 \textit{Knight's Tour Problem} on a chessboard. The preliminary part (4\%) is

    32 due on  \cwNINE{} at 5pm; the core part (6\%) is due on \cwNINEa{} at 5pm.\bigskip

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

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

    35 

    36 \IMPORTANTNONE{}

    37 

    38 \noindent

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

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

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

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

    43 \texttt{knight3.scala}.

    44 

    45 \DISCLAIMER{}

    46 

    47 \subsection*{Background}

    48 

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

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

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

    52 

    53 \chessboard[maxfield=d4, 

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

    55             text = \small 24, markfield=Z4,

    56             text = \small 11, markfield=a4,

    57             text = \small  6, markfield=b4,

    58             text = \small 17, markfield=c4,

    59             text = \small  0, markfield=d4,

    60             text = \small 19, markfield=Z3,

    61             text = \small 16, markfield=a3,

    62             text = \small 23, markfield=b3,

    63             text = \small 12, markfield=c3,

    64             text = \small  7, markfield=d3,

    65             text = \small 10, markfield=Z2,

    66             text = \small  5, markfield=a2,

    67             text = \small 18, markfield=b2,

    68             text = \small  1, markfield=c2,

    69             text = \small 22, markfield=d2,

    70             text = \small 15, markfield=Z1,

    71             text = \small 20, markfield=a1,

    72             text = \small  3, markfield=b1,

    73             text = \small  8, markfield=c1,

    74             text = \small 13, markfield=d1,

    75             text = \small  4, markfield=Z0,

    76             text = \small  9, markfield=a0,

    77             text = \small 14, markfield=b0,

    78             text = \small 21, markfield=c0,

    79             text = \small  2, markfield=d0

    80            ]

    81            

    82 \noindent

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

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

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

    86 bigger board there is. 

    87 

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

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

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

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

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

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

    94 example

    95 

    96 \chessboard[maxfield=e5, 

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

    98             text = \small 10, markfield=Z5,

    99             text = \small  5, markfield=a5,

   100             text = \small 18, markfield=b5,

   101             text = \small 25, markfield=c5,

   102             text = \small 16, markfield=d5,

   103             text = \small  7, markfield=e5,

   104             text = \small 31, markfield=Z4,

   105             text = \small 26, markfield=a4,

   106             text = \small  9, markfield=b4,

   107             text = \small  6, markfield=c4,

   108             text = \small 19, markfield=d4,

   109             text = \small 24, markfield=e4,

   110             % 4  11  30  17   8  15 

   111             text = \small  4, markfield=Z3,

   112             text = \small 11, markfield=a3,

   113             text = \small 30, markfield=b3,

   114             text = \small 17, markfield=c3,

   115             text = \small  8, markfield=d3,

   116             text = \small 15, markfield=e3,

   117             %29  32  27   0  23  20 

   118             text = \small 29, markfield=Z2,

   119             text = \small 32, markfield=a2,

   120             text = \small 27, markfield=b2,

   121             text = \small  0, markfield=c2,

   122             text = \small 23, markfield=d2,

   123             text = \small 20, markfield=e2,

   124             %12   3  34  21  14   1 

   125             text = \small 12, markfield=Z1,

   126             text = \small  3, markfield=a1,

   127             text = \small 34, markfield=b1,

   128             text = \small 21, markfield=c1,

   129             text = \small 14, markfield=d1,

   130             text = \small  1, markfield=e1,

   131             %33  28  13   2  35  22 

   132             text = \small 33, markfield=Z0,

   133             text = \small 28, markfield=a0,

   134             text = \small 13, markfield=b0,

   135             text = \small  2, markfield=c0,

   136             text = \small 35, markfield=d0,

   137             text = \small 22, markfield=e0,

   138             vlabel=false,

   139             hlabel=false

   140            ]

   141 

   142 

   143 \noindent

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

   145 

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

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

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

   149 

   150 {\chessboard[maxfield=g7,

   151             color=blue!50,

   152             linewidth=0.2em,

   153             shortenstart=0.5ex,

   154             shortenend=0.5ex,

   155             markstyle=cross,

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

   157             color=red!50,

   158             markfields={f5, e6},

   159             setpieces={Ng7, Nb2},

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

   161 

   162 \subsection*{Reference Implementation}

   163 

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

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

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

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

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

   169 prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}.

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

   171 information. For example

   172 

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

   174 $ scala -cp knight1.jar

   175 scala> CW9a.enum_tours(5, List((0, 0))).length

   176 Time needed: 1.722 secs.

   177 res0: Int = 304

   178 

   179 scala> CW9a.print_board(8, CW9a.first_tour(8, List((0, 0))).get)

   180 Time needed: 15.411 secs.

   181 

   182  51  46  55  44  53   4  21  12 

   183  56  43  52   3  22  13  24   5 

   184  47  50  45  54  25  20  11  14 

   185  42  57   2  49  40  23   6  19 

   186  35  48  41  26  61  10  15  28 

   187  58   1  36  39  32  27  18   7 

   188  37  34  31  60   9  62  29  16 

   189   0  59  38  33  30  17   8  63 

   190 \end{lstlisting}%$

   191 

   192 

   193 \subsection*{Hints}

   194 

   195 \noindent

   196 \textbf{Preliminary Part} useful list functions: \texttt{.contains(..)} checks

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

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

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

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

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

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

   203 this function takes an \texttt{Int} as an argument.\medskip

   204 

   205 

   206 \noindent

   207 \textbf{Core Part} a useful list function: \texttt{.sortBy} sorts a list

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

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

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

   211 

   212 

   213 

   214 

   215 \subsection*{Preliminary Part (4 Marks)}

   216 

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

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

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

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

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

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

   223 with exhaustively exploring the complete search space for small

   224 chessboards.\medskip

   225 

   226 \noindent

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

   228 board dimension is an integer.

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

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

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

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

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

   234 by

   235 

   236 \[

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

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

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

   240 \]

   241 

   242 \noindent

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

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

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

   246 knight moves (see above for the rules).

   247 

   248 

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

   250 

   251 \begin{itemize}

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

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

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

   255   path. \hfill[1 Mark]

   256 

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

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

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

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

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

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

   263   positions in this order:

   264 

   265   \begin{center}

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

   267   \end{center}

   268 

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

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

   271   empty board, the legal moves are

   272 

   273   \begin{center}

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

   275   \end{center}

   276   \mbox{}\hfill[1 Mark]

   277 

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

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

   280   arguments. They exhaustively search for tours starting

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

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

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

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

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

   286   from the given position.\\

   287   \mbox{}\hfill[2 Marks]

   288 \end{itemize}

   289 

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

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

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

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

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

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

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

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

   298   19591828170979904, respectively.}\smallskip

   299 

   300 

   301 \subsection*{Core Part (6 Marks)}

   302 

   303 

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

   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 

   350 \noindent

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

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

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

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

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

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

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

   358 onward moves, namely 2.

   359 

   360 \chessboard[maxfield=g7,

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

   362             text = \small 3, markfield=Z5,

   363             text = \small 7, markfield=b5,

   364             text = \small 7, markfield=c4,

   365             text = \small 7, markfield=c2,

   366             text = \small 5, markfield=b1,

   367             text = \small 2, markfield=Z1,

   368             setpieces={Na3}]

   369 

   370 \noindent

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

   372 tried in the order

   373 

   374 \[

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

   376 \]

   377 

   378 \noindent

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

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

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

   382 

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

   384 

   385 \begin{itemize}

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

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

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

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

   390   

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

   392   function that searches for a single

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

   394   onward moves according to

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

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

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

   398 

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

   400   for boards up to

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

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

   403   board as starting field.\\

   404   %You have to be careful to write a

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

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

   407   \mbox{}\hfill[1 Mark]

   408 \end{itemize}    

   409 

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

   411 \begin{itemize}

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

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

   414   deal with boards up to

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

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

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

   418   with stack-overflows. Please observe the requirements about

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

   420 

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

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

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

   424   computer. For example the reference implementation shows

   425   on my laptop:

   426   

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

   428 $ scala -cp knight3.jar

   429   

   430 scala> CW9c.tour_on_mega_board(70, List((0, 0)))

   431 Time needed: 9.484 secs.

   432 ...<<long_list>>...

   433 \end{lstlisting}%$

   434 

   435   \mbox{}\hfill[1 Mark]

   436 \end{itemize}  

   437 \bigskip

   438 

   439 

   440 

   441 

   442 \end{document}

   443 

   444 %%% Local Variables: 

   445 %%% mode: latex

   446 %%% TeX-master: t

   447 %%% End: