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*{Part 8 (Scala)}

    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  \cwEIGHT{} at 4pm; the core part is due on \cwEIGHTa{} at 4pm.

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

    34 yet seen in the first three lectures. \bigskip

    35 

    36 \IMPORTANT{}

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

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

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

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

    41 \texttt{knight3.scala}.

    42 

    43 \DISCLAIMER{}

    44 

    45 \subsection*{Background}

    46 

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

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

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

    50 

    51 \chessboard[maxfield=d4, 

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

    53             text = \small 24, markfield=Z4,

    54             text = \small 11, markfield=a4,

    55             text = \small  6, markfield=b4,

    56             text = \small 17, markfield=c4,

    57             text = \small  0, markfield=d4,

    58             text = \small 19, markfield=Z3,

    59             text = \small 16, markfield=a3,

    60             text = \small 23, markfield=b3,

    61             text = \small 12, markfield=c3,

    62             text = \small  7, markfield=d3,

    63             text = \small 10, markfield=Z2,

    64             text = \small  5, markfield=a2,

    65             text = \small 18, markfield=b2,

    66             text = \small  1, markfield=c2,

    67             text = \small 22, markfield=d2,

    68             text = \small 15, markfield=Z1,

    69             text = \small 20, markfield=a1,

    70             text = \small  3, markfield=b1,

    71             text = \small  8, markfield=c1,

    72             text = \small 13, markfield=d1,

    73             text = \small  4, markfield=Z0,

    74             text = \small  9, markfield=a0,

    75             text = \small 14, markfield=b0,

    76             text = \small 21, markfield=c0,

    77             text = \small  2, markfield=d0

    78            ]

    79            

    80 \noindent

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

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

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

    84 bigger board there is. 

    85 

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

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

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

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

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

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

    92 example

    93 

    94 \chessboard[maxfield=e5, 

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

    96             text = \small 10, markfield=Z5,

    97             text = \small  5, markfield=a5,

    98             text = \small 18, markfield=b5,

    99             text = \small 25, markfield=c5,

   100             text = \small 16, markfield=d5,

   101             text = \small  7, markfield=e5,

   102             text = \small 31, markfield=Z4,

   103             text = \small 26, markfield=a4,

   104             text = \small  9, markfield=b4,

   105             text = \small  6, markfield=c4,

   106             text = \small 19, markfield=d4,

   107             text = \small 24, markfield=e4,

   108             % 4  11  30  17   8  15 

   109             text = \small  4, markfield=Z3,

   110             text = \small 11, markfield=a3,

   111             text = \small 30, markfield=b3,

   112             text = \small 17, markfield=c3,

   113             text = \small  8, markfield=d3,

   114             text = \small 15, markfield=e3,

   115             %29  32  27   0  23  20 

   116             text = \small 29, markfield=Z2,

   117             text = \small 32, markfield=a2,

   118             text = \small 27, markfield=b2,

   119             text = \small  0, markfield=c2,

   120             text = \small 23, markfield=d2,

   121             text = \small 20, markfield=e2,

   122             %12   3  34  21  14   1 

   123             text = \small 12, markfield=Z1,

   124             text = \small  3, markfield=a1,

   125             text = \small 34, markfield=b1,

   126             text = \small 21, markfield=c1,

   127             text = \small 14, markfield=d1,

   128             text = \small  1, markfield=e1,

   129             %33  28  13   2  35  22 

   130             text = \small 33, markfield=Z0,

   131             text = \small 28, markfield=a0,

   132             text = \small 13, markfield=b0,

   133             text = \small  2, markfield=c0,

   134             text = \small 35, markfield=d0,

   135             text = \small 22, markfield=e0,

   136             vlabel=false,

   137             hlabel=false

   138            ]

   139 

   140 

   141 \noindent

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

   143 

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

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

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

   147 

   148 {\chessboard[maxfield=g7,

   149             color=blue!50,

   150             linewidth=0.2em,

   151             shortenstart=0.5ex,

   152             shortenend=0.5ex,

   153             markstyle=cross,

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

   155             color=red!50,

   156             markfields={f5, e6},

   157             setpieces={Ng7, Nb2},

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

   159 

   160 \subsection*{Reference Implementation}

   161 

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

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

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

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

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

   167 prefix the calls with \texttt{CW8a}, \texttt{CW8b} and \texttt{CW8c}.

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

   169 information. For example

   170 

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

   172 $ scala -cp knight1.jar

   173 scala> CW8a.enum_tours(5, List((0, 0))).length

   174 Time needed: 1.722 secs.

   175 res0: Int = 304

   176 

   177 scala> CW8a.print_board(8, CW8a.first_tour(8, List((0, 0))).get)

   178 Time needed: 15.411 secs.

   179 

   180  51  46  55  44  53   4  21  12 

   181  56  43  52   3  22  13  24   5 

   182  47  50  45  54  25  20  11  14 

   183  42  57   2  49  40  23   6  19 

   184  35  48  41  26  61  10  15  28 

   185  58   1  36  39  32  27  18   7 

   186  37  34  31  60   9  62  29  16 

   187   0  59  38  33  30  17   8  63 

   188 \end{lstlisting}%$

   189 

   190 

   191 \subsection*{Hints}

   192 

   193 \noindent

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

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

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

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

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

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

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

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

   202 

   203 

   204 \noindent

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

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

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

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

   209 

   210 

   211 

   212 

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

   214 

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

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

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

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

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

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

   221 with exhaustively exploring the complete search space for small

   222 chessboards.\medskip

   223 

   224 \noindent

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

   226 board dimension is an integer.

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

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

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

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

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

   232 by

   233 

   234 \[

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

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

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

   238 \]

   239 

   240 \noindent

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

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

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

   244 knight moves (see above for the rules).

   245 

   246 

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

   248 

   249 \begin{itemize}

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

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

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

   253   path. \hfill[1 Mark]

   254 

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

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

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

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

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

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

   261   positions in this order:

   262 

   263   \begin{center}

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

   265   \end{center}

   266 

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

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

   269   empty board, the legal moves are

   270 

   271   \begin{center}

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

   273   \end{center}

   274   \mbox{}\hfill[1 Mark]

   275 

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

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

   278   arguments. They exhaustively search for tours starting

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

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

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

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

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

   284   from the given position.\\

   285   \mbox{}\hfill[2 Marks]

   286 \end{itemize}

   287 

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

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

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

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

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

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

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

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

   296   19591828170979904, respectively.}\smallskip

   297 

   298 

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

   300 

   301 

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

   303 

   304 \begin{itemize}

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

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

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

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

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

   310 

   311   \[

   312   \begin{array}{lcl}

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

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

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

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

   317                               \end{cases}

   318   \end{array}

   319   \]

   320 

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

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

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

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

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

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

   327   There is one additional point however you should

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

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

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

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

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

   333   

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

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

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

   337   needs to return a value of type

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

   339 \end{itemize}

   340 

   341 \noindent

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

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

   344 \bigskip

   345 

   346 %%\newpage

   347 

   348 \noindent

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

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

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

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

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

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

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

   356 onward moves, namely 2.

   357 

   358 \chessboard[maxfield=g7,

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

   360             text = \small 3, markfield=Z5,

   361             text = \small 7, markfield=b5,

   362             text = \small 7, markfield=c4,

   363             text = \small 7, markfield=c2,

   364             text = \small 5, markfield=b1,

   365             text = \small 2, markfield=Z1,

   366             setpieces={Na3}]

   367 

   368 \noindent

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

   370 tried in the order

   371 

   372 \[

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

   374 \]

   375 

   376 \noindent

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

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

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

   380 

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

   382 

   383 \begin{itemize}

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

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

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

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

   388   

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

   390   function that searches for a single

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

   392   onward moves according to

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

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

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

   396 

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

   398   for boards up to

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

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

   401   board as starting field.\\

   402   %You have to be careful to write a

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

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

   405   \mbox{}\hfill[1 Mark]

   406 \end{itemize}    

   407 

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

   409 \begin{itemize}

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

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

   412   deal with boards up to

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

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

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

   416   with stack-overflows. Please observe the requirements about

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

   418 

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

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

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

   422   computer. For example the reference implementation shows

   423   on my laptop:

   424   

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

   426 $ scala -cp knight3.jar

   427   

   428 scala> CW8c.tour_on_mega_board(70, List((0, 0)))

   429 Time needed: 9.484 secs.

   430 ...<<long_list>>...

   431 \end{lstlisting}%$

   432 

   433   \mbox{}\hfill[1 Mark]

   434 \end{itemize}  

   435 \bigskip

   436 

   437 

   438 

   439 

   440 \end{document}

   441 

   442 %%% Local Variables: 

   443 %%% mode: latex

   444 %%% TeX-master: t

   445 %%% End: