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

    51 \section*{Main Part 4:\\ Implementing the Shogun Board Game (7 Marks)}

    29 \noindent

    58 

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

    59 \noindent

    31 implement Scala programs that solve various versions of the

    60 You are asked to implement a Scala program for playing the Shogun

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

    61 board game.\medskip

    33 \medskip 

    62 

    34 

    63 %The deadline for your submission is on 26th July at

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

    64 %16:00. There will be no automated tests for the resit, but there are

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

    65 %many testcases in the template and the task description.  Make sure

    66 %you use Scala \textbf{2.13.XX} for the resit---the same version as

    67 %during the lectures.  \medskip

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

    72 Also note that the running time of each task will be restricted to a

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

    74 try to avoid to calculate the result again. 

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

    45 \texttt{knight3.scala}.

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

    80 Shogun

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

    81 (\faVolumeUp\,[shōgoon]) is a game played by two players on a chess board and is somewhat

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

    82 similar to chess and checkers. A real Shogun board looks

    54 

    83 like in the pictures on the left.

    55 \chessboard[maxfield=d4, 

    84 

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

    85 

    57             text = \small 24, markfield=Z4,

    86 \begin{center}

    58             text = \small 11, markfield=a4,

    87 \begin{tabular}{@{}ccc@{}}

    59             text = \small  6, markfield=b4,

    88 \raisebox{2mm}{\includegraphics[scale=0.1]{shogun2.jpeg}}

    60             text = \small 17, markfield=c4,

    89 &     

    61             text = \small  0, markfield=d4,

    90 \raisebox{2mm}{\includegraphics[scale=0.14]{shogun.jpeg}}

    62             text = \small 19, markfield=Z3,

    91 &  

    63             text = \small 16, markfield=a3,

    92 \begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    

    64             text = \small 23, markfield=b3,

    93 % chessboard

    65             text = \small 12, markfield=c3,

    94 \draw[very thick,gray] (0,0) rectangle (8,8);

    66             text = \small  7, markfield=d3,

    95 \foreach\x in {0,...,7}\foreach\y in {7,...,0}

    67             text = \small 10, markfield=Z2,

    96 {

    68             text = \small  5, markfield=a2,

    97   \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 

    69             text = \small 18, markfield=b2,

    98   \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

    70             text = \small  1, markfield=c2,

    99 }

    71             text = \small 22, markfield=d2,

   100 % black pieces

    72             text = \small 15, markfield=Z1,

   101 \foreach\x/\y/\e in {1/1/1,2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,8/1/2}

    73             text = \small 20, markfield=a1,

   102   \pic[fill=white] at (\x,\y) {piece={\e}};

    74             text = \small  3, markfield=b1,

   103 % white pieces

    75             text = \small  8, markfield=c1,

   104 \foreach\x/\y/\e in {1/8/4,2/8/2,3/8/4,5/8/4,6/8/2,7/8/3,8/8/1}

    76             text = \small 13, markfield=d1,

   105   \pic[fill=red] at (\x,\y)     {piece={\e}};

    77             text = \small  4, markfield=Z0,

   106 \pic[fill=white] at (5.0,1.0) {king={1}};

    78             text = \small  9, markfield=a0,

   107 \pic[fill=red]   at (4.0,8.0) {king={2}};

    79             text = \small 14, markfield=b0,

   108 % numbers

    80             text = \small 21, markfield=c0,

   109 \foreach\x in {1,...,8}

    81             text = \small  2, markfield=d0

   110 {\draw (\x - 0.5, -0.4) node {\x};

    82            ]

   111 }

    83            

   112 \foreach\y in {1,...,8}

    84 \noindent

   113 {\draw (-0.4, \y - 0.6, -0.4) node {\y};

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

   114 }

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

   115 \end{tikzpicture}

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

   116 \end{tabular}

    88 bigger board there is. 

   117 \end{center}

    89 

   118 

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

   119 

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

   120 \noindent

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

   121 In what follows we shall use board illustrations as shown on the right.  As

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

   122 can be seen there are two colours in Shogun for the pieces, red and white. Each

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

   123 player has 8 pieces, one of which is a king (the piece with the crown)

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

   124 and seven are pawns. At the beginning the pieces are lined up as shown

    96 example

   125 above.  What sets Shogun apart from chess and checkers is that each

    97 

   126 piece has, what I call, a kind of \textit{energy}---which for pawns is

    98 \chessboard[maxfield=e5, 

   127 a number between 1 and 4, and for kings between 1 and 2. The energy

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

   128 determines how far a piece has to move. In the physical version of

   100             text = \small 10, markfield=Z5,

   129 Shogun, the pieces and the board have magnets that can change the

   101             text = \small  5, markfield=a5,

   130 energy of a piece from move to move---so a piece on one field can have

   102             text = \small 18, markfield=b5,

   131 energy 2 and on a different field the same piece might have energy

   103             text = \small 25, markfield=c5,

   132 3. There are some further constraints on legal moves, which are

   104             text = \small 16, markfield=d5,

   133 explained below.  The point of this part is to implement functions

   105             text = \small  7, markfield=e5,

   134 about moving pieces on the Shogun board.\medskip\medskip

   106             text = \small 31, markfield=Z4,

   135 

   107             text = \small 26, markfield=a4,

   136 %and testing for when a

   108             text = \small  9, markfield=b4,

   137 %checkmate occurs---i.e.~the king is attacked and cannot move

   109             text = \small  6, markfield=c4,

   138 %anymore to an ``unattacked'' field (to simplify matters for

   110             text = \small 19, markfield=d4,

   139 %the resit we leave out the case where the checkmate can be averted by capturing

   111             text = \small 24, markfield=e4,

   140 %the attacking piece).\medskip

   112             % 4  11  30  17   8  15 

   141 

   113             text = \small  4, markfield=Z3,

   142 \noindent

   114             text = \small 11, markfield=a3,

   143 Like in chess, in Shogun the players take turns of moving and

   115             text = \small 30, markfield=b3,

   144 possibly capturing opposing pieces.

   116             text = \small 17, markfield=c3,

   145 There are the following rules on how pieces can move:

   117             text = \small  8, markfield=d3,

   146 

   118             text = \small 15, markfield=e3,

   147 \begin{itemize}

   119             %29  32  27   0  23  20 

   148 \item The energy of a piece determines how far, that is how many

   120             text = \small 29, markfield=Z2,

   149   fields, a piece has to move (remember pawns have an energy between 1 --

   121             text = \small 32, markfield=a2,

   150   4, kings have an energy of only 1 -- 2). The energy of a piece might

   122             text = \small 27, markfield=b2,

   151   change when the piece moves to new field.

   123             text = \small  0, markfield=c2,

   152 \item Pieces can move in straight lines (up, down, left, right), or in

   124             text = \small 23, markfield=d2,

   153   L-shape moves, meaning a move can make a single

   125             text = \small 20, markfield=e2,

   154   90$^{\circ}$-turn. S-shape moves with more than one turn are not

   126             %12   3  34  21  14   1 

   155   allowed. Also in a single move a piece cannot go forward and then

   127             text = \small 12, markfield=Z1,

   156   go backward---for example with energy 3 you cannot move 2 fields up and

   128             text = \small  3, markfield=a1,

   157   then 1 field down. A piece can never move diagonally.

   129             text = \small 34, markfield=b1,

   158 \item A piece cannot jump over another piece and cannot stack up on top of your own pieces.

   130             text = \small 21, markfield=c1,

   159   But you can capture an opponent's piece if you move to an occupied field. A captured

   131             text = \small 14, markfield=d1,

   160   piece is removed from the board.

   132             text = \small  1, markfield=e1,

   161 \end{itemize}  

   133             %33  28  13   2  35  22 

   162 

   134             text = \small 33, markfield=Z0,

   163 \noindent

   135             text = \small 28, markfield=a0,

   164 Like in chess, checkmate is determined when the king of a player cannot

   136             text = \small 13, markfield=b0,

   165 move anymore to a field that is not attacked, or a player cannot

   137             text = \small  2, markfield=c0,

   166 capture or block the attacking piece, or the king is the only

   138             text = \small 35, markfield=d0,

   167 piece left for a player. A board that is checkmate is the following:

   139             text = \small 22, markfield=e0,

   168 

   140             vlabel=false,

   169 \begin{center}

   141             hlabel=false

   170 \begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]    

   142            ]

   171 % chessboard

   143 

   172 \draw[very thick,gray] (0,0) rectangle (8,8);

   144 

   173 \foreach\x in {0,...,7}\foreach\y in {7,...,0}

   145 \noindent

   174 {

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

   175   \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 

   147 

   176   \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

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

   177 }

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

   178 % redpieces

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

   179 \pic[fill=red]   at (4,2) {king={2}};

   151 

   180 \pic[fill=red]   at (6,1) {piece={3}};

   152 {\chessboard[maxfield=g7,

   181 \pic[fill=red]   at (4,4) {piece={4}};

   153             color=blue!50,

   182 \pic[fill=red]   at (5,3) {piece={4}};

   154             linewidth=0.2em,

   183 % white pieces

   155             shortenstart=0.5ex,

   184 \pic[fill=white] at (7,1) {king={2}};

   156             shortenend=0.5ex,

   185 \pic[fill=white] at (8,5) {piece={2}};

   157             markstyle=cross,

   186 \pic[fill=white] at (4,1) {piece={2}};

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

   187 % numbers

   159             color=red!50,

   188 \foreach\x in {1,...,8}

   160             markfields={f5, e6},

   189 {\draw (\x - 0.5, -0.4) node {\x};

   161             setpieces={Ng7, Nb2},

   190 }

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

   191 \foreach\y in {1,...,8}

   163 

   192 {\draw (-0.4, \y - 0.6, -0.4) node {\y};

   164 \subsection*{Reference Implementation}

   193 }

   165 

   194 \end{tikzpicture}

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

   195 \end{center}

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

   196 

   168 %section on KEATS.}\medskip

   197 \noindent

   169 

   198 The reason for the checkmate is that the white king on field (7, 1) is

   170 \noindent

   199 attacked by the red pawn on \mbox{(5, 3)}. There is nowhere for the

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

   200 white king to go, and no white pawn can be moved into the way of this

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

   201 red pawn and white can also not capture it. When determining a possible

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

   202 move, you need to be careful with pieces that might be in the

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

   203 way. Consider the following position:

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

   204 

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

   205 \begin{equation}\label{moves}

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

   206 \begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]    

   178 information. For example

   207 % chessboard

   179 

   208 \draw[very thick,gray] (0,0) rectangle (8,8);

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

   209 \foreach\x in {0,...,7}\foreach\y in {7,...,0}

   181 $ scala -cp knight1.jar

   210 {

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

   211   \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 

   183 Time needed: 1.722 secs.

   212   \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

   184 res0: Int = 304

   213 }

   185 

   214 % redpieces

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

   215 \fill[blue!50] (0,2) rectangle ++ (1,1);

   187 Time needed: 15.411 secs.

   216 \fill[blue!50] (1,1) rectangle ++ (1,1);

   188 

   217 \fill[blue!50] (0,4) rectangle ++ (1,1);

   189  51  46  55  44  53   4  21  12 

   218 \fill[blue!50] (1,5) rectangle ++ (1,1);

   190  56  43  52   3  22  13  24   5 

   219 \fill[blue!50] (2,6) rectangle ++ (1,1);

   191  47  50  45  54  25  20  11  14 

   220 %%\fill[blue!50] (3,7) rectangle ++ (1,1);

   192  42  57   2  49  40  23   6  19 

   221 \fill[blue!50] (4,6) rectangle ++ (1,1);

   193  35  48  41  26  61  10  15  28 

   222 \fill[blue!50] (5,5) rectangle ++ (1,1);

   194  58   1  36  39  32  27  18   7 

   223 \fill[blue!50] (6,4) rectangle ++ (1,1);

   195  37  34  31  60   9  62  29  16 

   224 \fill[blue!50] (6,2) rectangle ++ (1,1);

   196   0  59  38  33  30  17   8  63 

   225 \fill[blue!50] (7,3) rectangle ++ (1,1);

   197 \end{lstlisting}%$

   226 \fill[blue!50] (4,0) rectangle ++ (1,1);

   227 \fill[blue!50] (2,0) rectangle ++ (1,1);

   228 \pic[fill=red]   at (4,4) {piece={4}};

   229 \pic[fill=red]   at (4,8) {piece={4}};

   230 \pic[fill=white] at (2,5) {piece={3}};

   231 \pic[fill=white] at (4,3) {piece={2}};

   232 \pic[fill=white] at (6,3) {piece={1}};

   233 \pic[fill=white] at (8,4) {piece={1}};

   234 % numbers

   235 \foreach\x in {1,...,8}

   236 {\draw (\x - 0.5, -0.4) node {\x};

   237 }

   238 \foreach\y in {1,...,8}

   239 {\draw (-0.4, \y - 0.6, -0.4) node {\y};

   240 }

   241 \end{tikzpicture}

   242 \end{equation}

   243 

   244 \noindent

   245 The red piece in the centre on field (4, 4) can move to all the blue fields.

   246 In particular it can move to (2, 6), because it can move 2 fields up

   247 and 2 fields to the left---it cannot reach this field by moving two

   248 fields to the left and then two up, because jumping over the white

   249 piece at (2, 5) is not allowed. Similarly, the field at (6, 2) is

   250 unreachable for the red piece because of the two white pieces at (4,

   251 3) and (6, 3) are in the way and no S-shape move is allowed in

   252 Shogun. The red piece on (4, 4) cannot move to the field (4, 8) at the

   253 top, because a red piece is already there; but it can move to (8, 4)

   254 and capture the white piece there. The moral is we always have to

   255 explore all possible ways in order to determine whether a piece can be

   256 moved to a field or not: in general there might be several ways and some of

   257 them might be blocked.

   202 \noindent

   262 Useful functions about pieces and boards are defined at the beginning

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

   263 of the template file. The function \texttt{.map} applies a function to

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

   264 each element of a list or set; \texttt{.flatMap} works like

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

   265 \texttt{map} followed by a \texttt{.flatten}---this is useful if a

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

   266 function returns a set of sets, which need to be ``unioned up''.  Sets

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

   267 can be partitioned according to a predicate with the function

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

   268 \texttt{.partition}.  For example

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

   269 

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

   270 \begin{lstlisting}

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

   271 val (even, odd) = Set(1,2,3,4,5).partition(_ % 2 == 0)

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

   272 // --> even = Set(2,4)

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

   273 //     odd  = Set(1,3,5)

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

   274 \end{lstlisting}

   215 

   275 

   216 

   276 \noindent

   217 %%\newpage

   277 The function \texttt{.toList} transforms a set into a list. The function

   278 \texttt{.count} counts elements according to a predicate. For example

   279 

   280 \begin{lstlisting}

   281 Set(1,2,3,4,5).count(_ % 2 == 0)

   282 // --> 2  

   283 \end{lstlisting}

   284 

   285 %% \newpage

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

   289 You are asked to implement how pieces can move on a Shogun board.  Let

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

   290 us first fix the basic datastructures for the implementation.  A

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

   291 \emph{position} (or field) is a pair of integers, like $(3, 2)$. The

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

   292 board's dimension is always 8 $\times$ 8.  A \emph{colour} is either

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

   293 red (\texttt{Red}) or white (\texttt{Wht}).  A \emph{piece} is either

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

   294 a pawn or a king, and has a position, a colour and an energy (an

   227 with exhaustively exploring the complete search space for small

   295 integer).  In the template file there are functions \texttt{incx},

   228 chessboards.\medskip

   296 \texttt{decx}, \texttt{incy} and \texttt{decy} for incrementing and

   229 

   297 decrementing the x- and y-coordinates of positions of pieces.

   230 \noindent

   298 

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

   299 A \emph{board} consists of a set of pieces. We always assume that we

   232 board dimension is an integer.

   300 start with a consistent board and every move generates another

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

   301 consistent board. In this way we do not need to check, for example,

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

   302 whether pieces are stacked on top of each other or located outside the

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

   303 board, or have an energy outside the permitted range. There are

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

   304 functions \texttt{-} and \texttt{+} for removing, respectively adding,

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

   305 single pieces to a board.  The function \texttt{occupied} takes a

   238 by

   306 position and a board as arguments, and returns an \texttt{Option} of a

   239 

   307 piece when this position is occupied, otherwise \texttt{None}. The

   240 \[

   308 function \texttt{occupied\_by} returns the colour of a potential piece

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

   309 on that position. The function \texttt{is\_occupied} returns a boolean

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

   310 for whether a position is occupied or not; \texttt{print\_board} is a

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

   311 rough function that prints out a board on the console. This function

   244 \]

   312 is meant for testing purposes.

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

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

   317 \item[(1)] You need to calculate all possible moves for a piece on a Shogun board. In order to

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

   318   make sure no piece moves forwards and backwards at the same time,

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

   319   and also exclude all S-shape moves, the data-structure \texttt{Move}

   261   path. \hfill[1 Mark]

   320   is introduced. A \texttt{Move} encodes all simple moves (up, down, left,

   262 

   321   right) and L-shape moves (first right, then up and so on). This is defined

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

   322   as follows:

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

   323 

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

   324 {\small\begin{lstlisting}

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

   325 abstract class Move

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

   326 case object U extends Move    // up

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

   327 case object D extends Move    // down

   269   positions in this order:

   328 case object R extends Move    // right

   329 case object L extends Move    // left

   330 case object RU extends Move   // ...

   331 case object LU extends Move

   332 case object RD extends Move

   333 case object LD extends Move

   334 case object UR extends Move

   335 case object UL extends Move

   336 case object DR extends Move

   337 case object DL extends Move

   338 \end{lstlisting}}

   339 

   340 You need to implement an \texttt{eval} function that takes a piece

   341 \texttt{pc}, a move \texttt{m}, an energy \texttt{en} and a board

   342 \texttt{b} as arguments. The idea is to recursively calculate all

   343 fields that can be reached by the move \texttt{m} (there might be more than

   344 one). The energy acts as a counter and decreases in each recursive

   345 call until 0 is reached (the final field). The function \texttt{eval} for a piece \texttt{pc}

   346 should behave as follows:

   347 

   348 \begin{itemize}

   349 \item If the position of a piece is outside the board, then no field can be reached (represented by

   350   the empty set \texttt{Set()}).

   351 \item If the energy is 0 and the position of the piece is \textit{not} occupied, then the field can be reached

   352   and the set \texttt{Set(pc)} is returned whereby \texttt{pc} is the piece given as argument.

   353 \item If the energy is 0 and the position of the piece \textit{is} occupied, but occupied by a piece

   354   of the opposite colour, then also the set \texttt{Set(pc)} is returned.

   355 \item In case the energy is > 0 and the position of the piece

   356   \texttt{pc} is occupied, then this move is blocked and the set

   357   \texttt{Set()} is returned.  

   358 \item In all other cases we have to analyse the move

   359   \texttt{m}. First, the simple moves (that is \texttt{U}, \texttt{D},

   360   \texttt{L} and \texttt{R}) we only have to increment / decrement the

   361   x- or y-position of the piece, decrease the energy and call eval

   362   recursively with the updated arguments. For example for \texttt{U}

   363   you need to increase the y-coordinate:

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

   366   \texttt{U} $\quad\Rightarrow\quad$ new arguments: \texttt{incy(pc)}, \texttt{U}, energy - 1, same board  

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

   369   The move \texttt{U} here acts like a ``mode'', meaning if you move

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

   370   up, you can only move up; the mode never changes. Similarly for the other simple moves: if

   277   empty board, the legal moves are

   371   you move right, you can only move right and so on. In this way it is

   372   prevented to go first to the right, and then change direction in order to go

   373   left (same with up and down).

   374   

   375   For the L-shape moves (\texttt{RU}, \texttt{LU}, \texttt{RD} and so on) you need to calculate two

   376   sets of reachable fields. Say we analyse \texttt{RU}, then we first have to calculate all fields

   377   reachable by moving to the right; then we have to calculate all moves by changing the mode to \texttt{U}.

   378   That means there are two recursive calls to \texttt{eval}:

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

   381   \begin{tabular}{@{}lll@{}}  

   382   \texttt{RU} & $\Rightarrow$ & new args for call 1: \texttt{incx(pc)}, \texttt{RU}, energy - 1, same board\\  

   383               &               & new args for call 2: \texttt{pc}, \texttt{U}, same energy, same board

   384   \end{tabular}  

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

   475 \item[(3)] Implement a function \texttt{attacked} that takes a colour and a board

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

   476   and calculates all pieces of the opposite side that are attacked. For example

   286   arguments. They exhaustively search for tours starting

   477   below on the left are all the attacked pieces by red, and on the right for white:

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

   478 

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

   479 \begin{center}

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

   480 \begin{tabular}{cc}      

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

   481 \begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    

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

   482 % chessboard

   292   from the given position.\\

   483 \draw[very thick,gray] (0,0) rectangle (8,8);

   484 \foreach\x in {0,...,7}\foreach\y in {7,...,0}

   485 {

   486   \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 

   487   \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

   488 }

   489 \fill[blue!50] (7,3) rectangle ++ (1,1);

   490 \fill[blue!50] (6,0) rectangle ++ (1,1);

   491 

   492 

   493 % black pieces

   494 \foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}

   495   \pic[fill=red] at (\x,\y) {piece={\e}};

   496 % white pieces

   497 \foreach\x/\y/\e in {8/4/2,4/1/2,8/7/3}

   498   \pic[fill=white] at (\x,\y)     {piece={\e}};

   499 

   500 \pic[fill=red] at (4,2) {king={2}};

   501 \pic[fill=white] at (7,1) {king={2}};

   502 

   503 % numbers

   504 \foreach\x in {1,...,8}

   505 {\draw (\x - 0.5, -0.4) node {\x};

   506 }

   507 \foreach\y in {1,...,8}

   508 {\draw (-0.4, \y - 0.6, -0.4) node {\y};

   509 }

   510 \end{tikzpicture}

   511 &

   512 \begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    

   513 % chessboard

   514 \draw[very thick,gray] (0,0) rectangle (8,8);

   515 \foreach\x in {0,...,7}\foreach\y in {7,...,0}

   516 {

   517   \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 

   518   \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

   519 }

   520 \fill[blue!50] (5,0) rectangle ++ (1,1);

   521 

   522 

   523 % black pieces

   524 \foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}

   525   \pic[fill=red] at (\x,\y) {piece={\e}};

   526 % white pieces

   527 \foreach\x/\y/\e in {8/4/2,4/1/2,8/7/3}

   528   \pic[fill=white] at (\x,\y)     {piece={\e}};

   529 

   530 \pic[fill=red] at (4,2) {king={2}};

   531 \pic[fill=white] at (7,1) {king={2}};

   532 

   533 % numbers

   534 \foreach\x in {1,...,8}

   535 {\draw (\x - 0.5, -0.4) node {\x};

   536 }

   537 \foreach\y in {1,...,8}

   538 {\draw (-0.4, \y - 0.6, -0.4) node {\y};

   539 }

   540 \end{tikzpicture}

   541 \\[-5mm]                       

   542 \end{tabular}

   543 \end{center}\mbox{}\hfill[1 Mark]

   544 

   545 \item[(4)] Implement a function \texttt{attackedN} that takes a piece and a board

   546   and calculates the number of times this pieces is attacked by pieces of the opposite colour.

   547   For example the piece on field (8, 4) above is attacked by 3 red pieces, and

   548   the piece on (6, 1) by 1 white piece.

   549   \\

   550   \mbox{}\hfill[1 Mark]

   551 

   552 \item[(5)] Implement a function \texttt{protectedN} that takes a piece and a board

   553   and calculates the number of times this pieces is protected by pieces of the same colour.

   554   For example the piece on field (8, 4) above is protected by 1 white pieces (the one on (8, 7)),

   555   and the piece on (5, 3) is protected by three red pieces ((6, 1), (4, 2), and (6, 5)).

   556   \\