
diff -r fbff6f601370 -r be818c5a67d4 cws/main_cw04.tex
--- a/cws/main_cw04.tex	Thu Nov 02 23:34:53 2023 +0000
+++ b/cws/main_cw04.tex	Sat Nov 04 18:53:37 2023 +0000
@@ -7,6 +7,35 @@
 \usepackage{../styles/langs}
 \usepackage{disclaimer}
 \usepackage{ulem}
+%\usepackage{tipauni}
+
+
+
+\tikzset 
+{%
+  pics/piece/.style n args={1}{ 
+    code={%
+      \fill[rounded corners]                  (-0.1,-0.1) rectangle (-0.9, -0.9);
+      \fill[left color=white,rounded corners,
+            right color=gray,
+            opacity=0.7]      (-0.1,-0.1) rectangle (-0.9, -0.9);
+      \draw[line width=0.4mm,rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);
+      \draw[line width=0.2mm,rounded corners] (-0.2,-0.2) rectangle (-0.8, -0.8);
+      \draw[anchor=mid] (-0.5,-0.6) node {#1};
+    }},
+  pics/king/.style n args={1}{ 
+    code={%
+      \fill[rounded corners]                  (-0.1,-0.1) rectangle (-0.9, -0.9);
+      \fill[left color=white,rounded corners,
+            right color=gray,
+            opacity=0.7]      (-0.1,-0.1) rectangle (-0.9, -0.9);
+      \draw[line width=0.4mm,rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);
+      \draw[line width=0.2mm,rounded corners] (-0.2,-0.2) rectangle (-0.8, -0.8);
+      \draw[anchor=mid] (-0.5,-0.6) node {#1};
+      \draw[anchor=center] (-0.5,-0.25) node {\includegraphics[scale=0.015]{crown.png}};
+    }}
+}
+
 
 \begin{document}
 
@@ -19,472 +48,515 @@
 
 \mbox{}\\[-18mm]\mbox{}
 
-\section*{Main Part 4 (Scala, 11 Marks)}
+\section*{Main Part 4:\\ Implementing the Shogun Board Game (7 Marks)}
 
 \mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\
 \mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\
 \mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\
 \mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\medskip\bigskip
 
+
 \noindent
-This part is about searching and backtracking. You are asked to
-implement Scala programs that solve various versions of the
-\textit{Knight's Tour Problem} on a chessboard.
-\medskip 
+You are asked to implement a Scala program for playing the Shogun
+board game.\medskip
 
-% Note the core, more advanced, part might include material you have not
-%yet seen in the first three lectures. \bigskip
+%The deadline for your submission is on 26th July at
+%16:00. There will be no automated tests for the resit, but there are
+%many testcases in the template and the task description.  Make sure
+%you use Scala \textbf{2.13.XX} for the resit---the same version as
+%during the lectures.  \medskip
 
 \IMPORTANTNONE{}
 
 \noindent
-Also note that the running time of each part will be restricted to a
+Also note that the running time of each task will be restricted to a
 maximum of 30 seconds on my laptop: If you calculate a result once,
-try to avoid to calculate the result again. Feel free to copy any code
-you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
-\texttt{knight3.scala}.
+try to avoid to calculate the result again. 
 
 \DISCLAIMER{}
 
 \subsection*{Background}
 
-The \textit{Knight's Tour Problem} is about finding a tour such that
-the knight visits every field on an $n\times n$ chessboard once. For
-example on a $5\times 5$ chessboard, a knight's tour is:
+Shogun
+(\faVolumeUp\,[shōgoon]) is a game played by two players on a chess board and is somewhat
+similar to chess and checkers. A real Shogun board looks
+like in the pictures on the left.
 
-\chessboard[maxfield=d4, 
-            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
-            text = \small 24, markfield=Z4,
-            text = \small 11, markfield=a4,
-            text = \small  6, markfield=b4,
-            text = \small 17, markfield=c4,
-            text = \small  0, markfield=d4,
-            text = \small 19, markfield=Z3,
-            text = \small 16, markfield=a3,
-            text = \small 23, markfield=b3,
-            text = \small 12, markfield=c3,
-            text = \small  7, markfield=d3,
-            text = \small 10, markfield=Z2,
-            text = \small  5, markfield=a2,
-            text = \small 18, markfield=b2,
-            text = \small  1, markfield=c2,
-            text = \small 22, markfield=d2,
-            text = \small 15, markfield=Z1,
-            text = \small 20, markfield=a1,
-            text = \small  3, markfield=b1,
-            text = \small  8, markfield=c1,
-            text = \small 13, markfield=d1,
-            text = \small  4, markfield=Z0,
-            text = \small  9, markfield=a0,
-            text = \small 14, markfield=b0,
-            text = \small 21, markfield=c0,
-            text = \small  2, markfield=d0
-           ]
-           
-\noindent
-This tour starts in the right-upper corner, then moves to field
-$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
-$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
-bigger board there is. 
 
-A knight's tour is called \emph{closed}, if the last step in the tour
-is within a knight's move to the beginning of the tour. So the above
-knight's tour is \underline{not} closed because the last
-step on field $(0, 4)$ is not within the reach of the first step on
-$(4, 4)$. It turns out there is no closed knight's tour on a $5\times
-5$ board. But there are on a $6\times 6$ board and on bigger ones, for
-example
-
-\chessboard[maxfield=e5, 
-            pgfstyle={[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
-            text = \small 10, markfield=Z5,
-            text = \small  5, markfield=a5,
-            text = \small 18, markfield=b5,
-            text = \small 25, markfield=c5,
-            text = \small 16, markfield=d5,
-            text = \small  7, markfield=e5,
-            text = \small 31, markfield=Z4,
-            text = \small 26, markfield=a4,
-            text = \small  9, markfield=b4,
-            text = \small  6, markfield=c4,
-            text = \small 19, markfield=d4,
-            text = \small 24, markfield=e4,
-            % 4  11  30  17   8  15 
-            text = \small  4, markfield=Z3,
-            text = \small 11, markfield=a3,
-            text = \small 30, markfield=b3,
-            text = \small 17, markfield=c3,
-            text = \small  8, markfield=d3,
-            text = \small 15, markfield=e3,
-            %29  32  27   0  23  20 
-            text = \small 29, markfield=Z2,
-            text = \small 32, markfield=a2,
-            text = \small 27, markfield=b2,
-            text = \small  0, markfield=c2,
-            text = \small 23, markfield=d2,
-            text = \small 20, markfield=e2,
-            %12   3  34  21  14   1 
-            text = \small 12, markfield=Z1,
-            text = \small  3, markfield=a1,
-            text = \small 34, markfield=b1,
-            text = \small 21, markfield=c1,
-            text = \small 14, markfield=d1,
-            text = \small  1, markfield=e1,
-            %33  28  13   2  35  22 
-            text = \small 33, markfield=Z0,
-            text = \small 28, markfield=a0,
-            text = \small 13, markfield=b0,
-            text = \small  2, markfield=c0,
-            text = \small 35, markfield=d0,
-            text = \small 22, markfield=e0,
-            vlabel=false,
-            hlabel=false
-           ]
+\begin{center}
+\begin{tabular}{@{}ccc@{}}
+\raisebox{2mm}{\includegraphics[scale=0.1]{shogun2.jpeg}}
+&     
+\raisebox{2mm}{\includegraphics[scale=0.14]{shogun.jpeg}}
+&  
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 
+  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+% black pieces
+\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}
+  \pic[fill=white] at (\x,\y) {piece={\e}};
+% white pieces
+\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}
+  \pic[fill=red] at (\x,\y)     {piece={\e}};
+\pic[fill=white] at (5.0,1.0) {king={1}};
+\pic[fill=red]   at (4.0,8.0) {king={2}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\end{tabular}
+\end{center}
 
 
 \noindent
-where the 35th move can join up again with the 0th move.
+In what follows we shall use board illustrations as shown on the right.  As
+can be seen there are two colours in Shogun for the pieces, red and white. Each
+player has 8 pieces, one of which is a king (the piece with the crown)
+and seven are pawns. At the beginning the pieces are lined up as shown
+above.  What sets Shogun apart from chess and checkers is that each
+piece has, what I call, a kind of \textit{energy}---which for pawns is
+a number between 1 and 4, and for kings between 1 and 2. The energy
+determines how far a piece has to move. In the physical version of
+Shogun, the pieces and the board have magnets that can change the
+energy of a piece from move to move---so a piece on one field can have
+energy 2 and on a different field the same piece might have energy
+3. There are some further constraints on legal moves, which are
+explained below.  The point of this part is to implement functions
+about moving pieces on the Shogun board.\medskip\medskip
 
-If you cannot remember how a knight moves in chess, or never played
-chess, below are all potential moves indicated for two knights, one on
-field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
+%and testing for when a
+%checkmate occurs---i.e.~the king is attacked and cannot move
+%anymore to an ``unattacked'' field (to simplify matters for
+%the resit we leave out the case where the checkmate can be averted by capturing
+%the attacking piece).\medskip
 
-{\chessboard[maxfield=g7,
-            color=blue!50,
-            linewidth=0.2em,
-            shortenstart=0.5ex,
-            shortenend=0.5ex,
-            markstyle=cross,
-            markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
-            color=red!50,
-            markfields={f5, e6},
-            setpieces={Ng7, Nb2},
-            boardfontsize=12pt,labelfontsize=9pt]}
+\noindent
+Like in chess, in Shogun the players take turns of moving and
+possibly capturing opposing pieces.
+There are the following rules on how pieces can move:
 
-\subsection*{Reference Implementation}
-
-%\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from K%EATS. The one
-%supplied with github does not contain the correct code. See Scala coursework
-%section on KEATS.}\medskip
+\begin{itemize}
+\item The energy of a piece determines how far, that is how many
+  fields, a piece has to move (remember pawns have an energy between 1 --
+  4, kings have an energy of only 1 -- 2). The energy of a piece might
+  change when the piece moves to new field.
+\item Pieces can move in straight lines (up, down, left, right), or in
+  L-shape moves, meaning a move can make a single
+  90$^{\circ}$-turn. S-shape moves with more than one turn are not
+  allowed. Also in a single move a piece cannot go forward and then
+  go backward---for example with energy 3 you cannot move 2 fields up and
+  then 1 field down. A piece can never move diagonally.
+\item A piece cannot jump over another piece and cannot stack up on top of your own pieces.
+  But you can capture an opponent's piece if you move to an occupied field. A captured
+  piece is removed from the board.
+\end{itemize}  
 
 \noindent
-This Scala part comes with three reference implementations in form of
-\texttt{jar}-files. This allows you to run any test cases on your own
-computer. For example you can call Scala on the command line with the
-option \texttt{-cp knight1.jar} and then query any function from the
-\texttt{knight1.scala} template file. As usual you have to
-prefix the calls with \texttt{M4a}, \texttt{M4b}, \texttt{M4c} and \texttt{M4d}.
-Since some of the calls are time sensitive, I included some timing
-information. For example
+Like in chess, checkmate is determined when the king of a player cannot
+move anymore to a field that is not attacked, or a player cannot
+capture or block the attacking piece, or the king is the only
+piece left for a player. A board that is checkmate is the following:
+
+\begin{center}
+\begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]    
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 
+  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+% redpieces
+\pic[fill=red]   at (4,2) {king={2}};
+\pic[fill=red]   at (6,1) {piece={3}};
+\pic[fill=red]   at (4,4) {piece={4}};
+\pic[fill=red]   at (5,3) {piece={4}};
+% white pieces
+\pic[fill=white] at (7,1) {king={2}};
+\pic[fill=white] at (8,5) {piece={2}};
+\pic[fill=white] at (4,1) {piece={2}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\end{center}
+
+\noindent
+The reason for the checkmate is that the white king on field (7, 1) is
+attacked by the red pawn on \mbox{(5, 3)}. There is nowhere for the
+white king to go, and no white pawn can be moved into the way of this
+red pawn and white can also not capture it. When determining a possible
+move, you need to be careful with pieces that might be in the
+way. Consider the following position:
 
-\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp knight1.jar
-scala> M4a.enum_tours(5, List((0, 0))).length
-Time needed: 1.722 secs.
-res0: Int = 304
-
-scala> M4a.print_board(8, M4a.first_tour(8, List((0, 0))).get)
-Time needed: 15.411 secs.
+\begin{equation}\label{moves}
+\begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]    
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 
+  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+% redpieces
+\fill[blue!50] (0,2) rectangle ++ (1,1);
+\fill[blue!50] (1,1) rectangle ++ (1,1);
+\fill[blue!50] (0,4) rectangle ++ (1,1);
+\fill[blue!50] (1,5) rectangle ++ (1,1);
+\fill[blue!50] (2,6) rectangle ++ (1,1);
+%%\fill[blue!50] (3,7) rectangle ++ (1,1);
+\fill[blue!50] (4,6) rectangle ++ (1,1);
+\fill[blue!50] (5,5) rectangle ++ (1,1);
+\fill[blue!50] (6,4) rectangle ++ (1,1);
+\fill[blue!50] (6,2) rectangle ++ (1,1);
+\fill[blue!50] (7,3) rectangle ++ (1,1);
+\fill[blue!50] (4,0) rectangle ++ (1,1);
+\fill[blue!50] (2,0) rectangle ++ (1,1);
+\pic[fill=red]   at (4,4) {piece={4}};
+\pic[fill=red]   at (4,8) {piece={4}};
+\pic[fill=white] at (2,5) {piece={3}};
+\pic[fill=white] at (4,3) {piece={2}};
+\pic[fill=white] at (6,3) {piece={1}};
+\pic[fill=white] at (8,4) {piece={1}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\end{equation}
 
- 51  46  55  44  53   4  21  12 
- 56  43  52   3  22  13  24   5 
- 47  50  45  54  25  20  11  14 
- 42  57   2  49  40  23   6  19 
- 35  48  41  26  61  10  15  28 
- 58   1  36  39  32  27  18   7 
- 37  34  31  60   9  62  29  16 
-  0  59  38  33  30  17   8  63 
-\end{lstlisting}%$
+\noindent
+The red piece in the centre on field (4, 4) can move to all the blue fields.
+In particular it can move to (2, 6), because it can move 2 fields up
+and 2 fields to the left---it cannot reach this field by moving two
+fields to the left and then two up, because jumping over the white
+piece at (2, 5) is not allowed. Similarly, the field at (6, 2) is
+unreachable for the red piece because of the two white pieces at (4,
+3) and (6, 3) are in the way and no S-shape move is allowed in
+Shogun. The red piece on (4, 4) cannot move to the field (4, 8) at the
+top, because a red piece is already there; but it can move to (8, 4)
+and capture the white piece there. The moral is we always have to
+explore all possible ways in order to determine whether a piece can be
+moved to a field or not: in general there might be several ways and some of
+them might be blocked.
 
 
 \subsection*{Hints}
 
+Useful functions about pieces and boards are defined at the beginning
+of the template file. The function \texttt{.map} applies a function to
+each element of a list or set; \texttt{.flatMap} works like
+\texttt{map} followed by a \texttt{.flatten}---this is useful if a
+function returns a set of sets, which need to be ``unioned up''.  Sets
+can be partitioned according to a predicate with the function
+\texttt{.partition}.  For example
+
+\begin{lstlisting}
+val (even, odd) = Set(1,2,3,4,5).partition(_ % 2 == 0)
+// --> even = Set(2,4)
+//     odd  = Set(1,3,5)
+\end{lstlisting}
+
 \noindent
-Useful list functions: \texttt{.contains(..)} checks
-whether an element is in a list, \texttt{.flatten} turns a list of
-lists into just a list, \texttt{\_::\_} puts an element on the head of
-the list, \texttt{.head} gives you the first element of a list (make
-sure the list is not \texttt{Nil}); a useful option function:
-\texttt{.isDefined} returns true, if an option is \texttt{Some(..)};
-anonymous functions can be constructed using \texttt{(x:Int) => ...},
-this function takes an \texttt{Int} as an argument; 
-a useful list function: \texttt{.sortBy} sorts a list
-according to a component given by the function; a function can be
-tested to be tail-recursive by annotation \texttt{@tailrec}, which is
-made available by importing \texttt{scala.annotation.tailrec}.\medskip
+The function \texttt{.toList} transforms a set into a list. The function
+\texttt{.count} counts elements according to a predicate. For example
 
+\begin{lstlisting}
+Set(1,2,3,4,5).count(_ % 2 == 0)
+// --> 2  
+\end{lstlisting}
 
-%%\newpage
+%% \newpage
 
 \subsection*{Tasks}
 
-You are asked to implement the knight's tour problem such that the
-dimension of the board can be changed.  Therefore most functions will
-take the dimension of the board as an argument.  The fun with this
-problem is that even for small chessboard dimensions it has already an
-incredibly large search space---finding a tour is like finding a
-needle in a haystack. In the first task we want to see how far we get
-with exhaustively exploring the complete search space for small
-chessboards.\medskip
+You are asked to implement how pieces can move on a Shogun board.  Let
+us first fix the basic datastructures for the implementation.  A
+\emph{position} (or field) is a pair of integers, like $(3, 2)$. The
+board's dimension is always 8 $\times$ 8.  A \emph{colour} is either
+red (\texttt{Red}) or white (\texttt{Wht}).  A \emph{piece} is either
+a pawn or a king, and has a position, a colour and an energy (an
+integer).  In the template file there are functions \texttt{incx},
+\texttt{decx}, \texttt{incy} and \texttt{decy} for incrementing and
+decrementing the x- and y-coordinates of positions of pieces.
 
-\noindent
-Let us first fix the basic datastructures for the implementation.  The
-board dimension is an integer.
-A \emph{position} (or field) on the chessboard is
-a pair of integers, like $(0, 0)$. A \emph{path} is a list of
-positions. The first (or 0th move) in a path is the last element in
-this list; and the last move in the path is the first element. For
-example the path for the $5\times 5$ chessboard above is represented
-by
-
-\[
-\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
-  $\underbrace{\texttt{(2, 3)}}_{23}$, ...,
-  $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}
-\]
-
-\noindent
-Suppose the dimension of a chessboard is $n$, then a path is a
-\emph{tour} if the length of the path is $n \times n$, each element
-occurs only once in the path, and each move follows the rules of how a
-knight moves (see above for the rules).
-
-
-\subsubsection*{Task 1 (file knight1.scala)}
+A \emph{board} consists of a set of pieces. We always assume that we
+start with a consistent board and every move generates another
+consistent board. In this way we do not need to check, for example,
+whether pieces are stacked on top of each other or located outside the
+board, or have an energy outside the permitted range. There are
+functions \texttt{-} and \texttt{+} for removing, respectively adding,
+single pieces to a board.  The function \texttt{occupied} takes a
+position and a board as arguments, and returns an \texttt{Option} of a
+piece when this position is occupied, otherwise \texttt{None}. The
+function \texttt{occupied\_by} returns the colour of a potential piece
+on that position. The function \texttt{is\_occupied} returns a boolean
+for whether a position is occupied or not; \texttt{print\_board} is a
+rough function that prints out a board on the console. This function
+is meant for testing purposes.
 
 
 
 \begin{itemize}
-\item[(1)] Implement an \texttt{is\_legal} function that takes a
-  dimension, a path and a position as arguments and tests whether the
-  position is inside the board and not yet element in the
-  path. \hfill[1 Mark]
+\item[(1)] You need to calculate all possible moves for a piece on a Shogun board. In order to
+  make sure no piece moves forwards and backwards at the same time,
+  and also exclude all S-shape moves, the data-structure \texttt{Move}
+  is introduced. A \texttt{Move} encodes all simple moves (up, down, left,
+  right) and L-shape moves (first right, then up and so on). This is defined
+  as follows:
+
+{\small\begin{lstlisting}
+abstract class Move
+case object U extends Move    // up
+case object D extends Move    // down
+case object R extends Move    // right
+case object L extends Move    // left
+case object RU extends Move   // ...
+case object LU extends Move
+case object RD extends Move
+case object LD extends Move
+case object UR extends Move
+case object UL extends Move
+case object DR extends Move
+case object DL extends Move
+\end{lstlisting}}
 
-\item[(2)] Implement a \texttt{legal\_moves} function that calculates for a
-  position all legal onward moves. If the onward moves are
-  placed on a circle, you should produce them starting from
-  ``12-o'clock'' following in clockwise order.  For example on an
-  $8\times 8$ board for a knight at position $(2, 2)$ and otherwise
-  empty board, the legal-moves function should produce the onward
-  positions in this order:
+You need to implement an \texttt{eval} function that takes a piece
+\texttt{pc}, a move \texttt{m}, an energy \texttt{en} and a board
+\texttt{b} as arguments. The idea is to recursively calculate all
+fields that can be reached by the move \texttt{m} (there might be more than
+one). The energy acts as a counter and decreases in each recursive
+call until 0 is reached (the final field). The function \texttt{eval} for a piece \texttt{pc}
+should behave as follows:
 
-  \begin{center}
-  \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
-  \end{center}
-
-  If the board is not empty, then maybe some of the moves need to be
-  filtered out from this list.  For a knight on field $(7, 7)$ and an
-  empty board, the legal moves are
+\begin{itemize}
+\item If the position of a piece is outside the board, then no field can be reached (represented by
+  the empty set \texttt{Set()}).
+\item If the energy is 0 and the position of the piece is \textit{not} occupied, then the field can be reached
+  and the set \texttt{Set(pc)} is returned whereby \texttt{pc} is the piece given as argument.
+\item If the energy is 0 and the position of the piece \textit{is} occupied, but occupied by a piece
+  of the opposite colour, then also the set \texttt{Set(pc)} is returned.
+\item In case the energy is > 0 and the position of the piece
+  \texttt{pc} is occupied, then this move is blocked and the set
+  \texttt{Set()} is returned.  
+\item In all other cases we have to analyse the move
+  \texttt{m}. First, the simple moves (that is \texttt{U}, \texttt{D},
+  \texttt{L} and \texttt{R}) we only have to increment / decrement the
+  x- or y-position of the piece, decrease the energy and call eval
+  recursively with the updated arguments. For example for \texttt{U}
+  you need to increase the y-coordinate:
 
   \begin{center}
-  \texttt{List((6,5), (5,6))}
+  \texttt{U} $\quad\Rightarrow\quad$ new arguments: \texttt{incy(pc)}, \texttt{U}, energy - 1, same board  
   \end{center}
-  \mbox{}\hfill[1 Mark]
-
-\item[(3)] Implement two recursive functions (\texttt{count\_tours} and
-  \texttt{enum\_tours}). They each take a dimension and a path as
-  arguments. They exhaustively search for tours starting
-  from the given path. The first function counts all possible 
-  tours (there can be none for certain board sizes) and the second
-  collects all tours in a list of paths. These functions will be
-  called with a path containing a single position---the starting field.
-  They are expected to extend this path so as to find all tours starting
-  from the given position.\\
-  \mbox{}\hfill[1 Mark]
-\end{itemize}
-  
-\noindent \textbf{Test data:} For the marking, the functions in (3)
-will be called with board sizes up to $5 \times 5$. If you search
-for tours on a $5 \times 5$ board starting only from field $(0, 0)$,
-there are 304 of tours. If you try out every field of a $5 \times
-5$-board as a starting field and add up all tours, you obtain
-1728. A $6\times 6$ board is already too large to be searched
-exhaustively.\footnote{For your interest, the number of tours on
-  $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
-  19591828170979904, respectively.}\smallskip
 
-\begin{itemize}
-\item[(4)] Implement a \texttt{first}-function. This function takes a list of
-  positions and a function $f$ as arguments; $f$ is the name we give to
-  this argument). The function $f$ takes a position as argument and
-  produces an optional path. So $f$'s type is \texttt{Pos =>
-    Option[Path]}. The idea behind the \texttt{first}-function is as follows:
-
-  \[
-  \begin{array}{lcl}
-  \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\  
-  \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
-    f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
-    \textit{first}(xs, f) & \textit{otherwise}\\
-                              \end{cases}
-  \end{array}
-  \]
+  The move \texttt{U} here acts like a ``mode'', meaning if you move
+  up, you can only move up; the mode never changes. Similarly for the other simple moves: if
+  you move right, you can only move right and so on. In this way it is
+  prevented to go first to the right, and then change direction in order to go
+  left (same with up and down).
+  
+  For the L-shape moves (\texttt{RU}, \texttt{LU}, \texttt{RD} and so on) you need to calculate two
+  sets of reachable fields. Say we analyse \texttt{RU}, then we first have to calculate all fields
+  reachable by moving to the right; then we have to calculate all moves by changing the mode to \texttt{U}.
+  That means there are two recursive calls to \texttt{eval}:
 
-  \noindent That is, we want to find the first position where the
-  result of $f$ is not \texttt{None}, if there is one. Note that
-  `inside' \texttt{first}, you do not (need to) know anything about
-  the argument $f$ except its type, namely \texttt{Pos =>
-    Option[Path]}. If you want to find out what the result of $f$ is
-  on a particular argument, say $x$, you can just write $f(x)$. 
-  There is one additional point however you should
-  take into account when implementing \texttt{first}: you will need to
-  calculate what the result of $f(x)$ is; your code should do this
-  only \textbf{once} and for as \textbf{few} elements in the list as
-  possible! Do not calculate $f(x)$ for all elements and then see which 
-  is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
-  
-\item[(5)] Implement a \texttt{first\_tour} function that uses the
-  \texttt{first}-function from (4), and searches recursively for single tour.
-  As there might not be such a tour at all, the \texttt{first\_tour} function
-  needs to return a value of type
-  \texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark]  
+  \begin{center}
+  \begin{tabular}{@{}lll@{}}  
+  \texttt{RU} & $\Rightarrow$ & new args for call 1: \texttt{incx(pc)}, \texttt{RU}, energy - 1, same board\\  
+              &               & new args for call 2: \texttt{pc}, \texttt{U}, same energy, same board
+  \end{tabular}  
+  \end{center}
+
+  In each case we receive some new piece(s) on reachable fields and therefore we return the set
+  containing all these fields. Similarly in the other cases.
 \end{itemize}
 
-\noindent
-\textbf{Testing:} The \texttt{first\_tour} function will be called with board
-sizes of up to $8 \times 8$.
-\bigskip
-
-%%\newpage
-\subsubsection*{Task 2 (file knight2.scala)}
+For example on the left board below, \texttt{eval} is called with the white
+piece in the centre and the move \texttt{RU} generates then a set of
+new pieces corresponding to the blue fileds. The difference on the
+right board is that \texttt{eval} is called with a red piece and therefore the
+field (4, 8) is not reachable anymore because it is already occupied by
+another red piece.
 
-\noindent
-As you should have seen in the earlier parts, a naive search for tours beyond
-$8 \times 8$ boards and also searching for closed tours even on small
-boards takes too much time. There is a heuristics, called \emph{Warnsdorf's
-Rule} that can speed up finding a tour. This heuristics states that a
-knight is moved so that it always proceeds to the field from which the
-knight will have the \underline{fewest} onward moves.  For example for
-a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
-onward moves, namely 2.
+\begin{center}
+\begin{tabular}{cc}  
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 
+  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (5,5) rectangle ++ (1,1);
+\fill[blue!50] (3,7) rectangle ++ (1,1);
+\fill[blue!50] (4,6) rectangle ++ (1,1);
+\fill[blue!50] (6,4) rectangle ++ (1,1);
+\fill[blue!50] (7,3) rectangle ++ (1,1);
+
+% black pieces
+\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}
+  \pic[fill=white] at (\x,\y) {piece={\e}};
+% white pieces
+\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}
+  \pic[fill=red] at (\x,\y)     {piece={\e}};
+\pic[fill=white] at (5.0,1.0) {king={1}};
+\pic[fill=red]   at (4.0,8.0) {king={2}};
 
-\chessboard[maxfield=g7,
-            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
-            text = \small 3, markfield=Z5,
-            text = \small 7, markfield=b5,
-            text = \small 7, markfield=c4,
-            text = \small 7, markfield=c2,
-            text = \small 5, markfield=b1,
-            text = \small 2, markfield=Z1,
-            setpieces={Na3}]
+\pic[fill=white] at (4,4) {piece={4}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+&
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 
+  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (5,5) rectangle ++ (1,1);
+\fill[blue!50] (4,6) rectangle ++ (1,1);
+\fill[blue!50] (6,4) rectangle ++ (1,1);
+\fill[blue!50] (7,3) rectangle ++ (1,1);
 
-\noindent
-Warnsdorf's Rule states that the moves on the board above should be
-tried in the order
+% black pieces
+\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}
+  \pic[fill=white] at (\x,\y) {piece={\e}};
+% white pieces
+\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}
+  \pic[fill=red] at (\x,\y)     {piece={\e}};
+\pic[fill=white] at (5.0,1.0) {king={1}};
+\pic[fill=red]   at (4.0,8.0) {king={2}};
 
-\[
-(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
-\]
-
-\noindent
-Whenever there are ties, the corresponding onward moves can be in any
-order.  When calculating the number of onward moves for each field, we
-do not count moves that revisit any field already visited.
+\pic[fill=red] at (4,4) {piece={4}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\\[-5mm]                    
+\end{tabular}                    
+\end{center}\hfill[3 Marks]
 
-\begin{itemize}
-\item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of
-  onward moves like in (2) but orders them according to 
-  Warnsdorf’s Rule. That means moves with the fewest legal onward moves
-  should come first (in order to be tried out first). \hfill[1 Mark]
-  
-\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristics}
-  function that searches for a single
-  \textbf{closed} tour on a $6\times 6$ board. It should try out
-  onward moves according to
-  the \texttt{ordered\_moves} function from (6). It is more likely to find
-  a solution when started in the middle of the board (that is
-  position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
+\item[(2)] Implement an \texttt{all\_moves} function that calculates for a
+  piece and a board, \textit{all} pieces on legal onward positions. For this
+  you have to call \texttt{eval} for all possible moves \texttt{m} (that is \texttt{U},
+  \texttt{D}, \ldots, \texttt{DL}). An example for all moves for the red piece on (4, 4) are
+  shown in \eqref{moves} on page \pageref{moves}.\\ 
+  \mbox{}\hfill[1 Mark]
+
+\item[(3)] Implement a function \texttt{attacked} that takes a colour and a board
+  and calculates all pieces of the opposite side that are attacked. For example
+  below on the left are all the attacked pieces by red, and on the right for white:
 
-\item[(8)] Implement a \texttt{first\_tour\_heuristics} function
-  for boards up to
-  $30\times 30$.  It is the same function as in (7) but searches for
-  tours (not just closed tours). It might be called with any field on the
-  board as starting field.\\
-  %You have to be careful to write a
-  %tail-recursive function of the \texttt{first\_tour\_heuristics} function
-  %otherwise you will get problems with stack-overflows.\\
-  \mbox{}\hfill[1 Mark]
-\end{itemize}    
+\begin{center}
+\begin{tabular}{cc}      
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 
+  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (7,3) rectangle ++ (1,1);
+\fill[blue!50] (6,0) rectangle ++ (1,1);
+
+
+% black pieces
+\foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}
+  \pic[fill=red] at (\x,\y) {piece={\e}};
+% white pieces
+\foreach\x/\y/\e in {8/4/2,4/1/2,8/7/3}
+  \pic[fill=white] at (\x,\y)     {piece={\e}};
+
+\pic[fill=red] at (4,2) {king={2}};
+\pic[fill=white] at (7,1) {king={2}};
 
-\subsubsection*{Task 3 (file knight3.scala)}
-\begin{itemize}
-\item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is
-  the same function as in (8), \textbf{but} should be able to
-  deal with boards up to
-  $70\times 70$ \textbf{within 30 seconds} (on my laptop). This will be tested
-  by starting from field $(0, 0)$. You have to be careful to
-  write a tail-recursive function otherwise you will get problems
-  with stack-overflows. Please observe the requirements about
-  the submissions: no tricks involving \textbf{.par}.\medskip
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+&
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]    
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25} 
+  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (5,0) rectangle ++ (1,1);
+
+
+% black pieces
+\foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}
+  \pic[fill=red] at (\x,\y) {piece={\e}};
+% white pieces
+\foreach\x/\y/\e in {8/4/2,4/1/2,8/7/3}
+  \pic[fill=white] at (\x,\y)     {piece={\e}};
 
-  The timelimit of 30 seconds is with respect to the laptop on which the
-  marking will happen. You can roughly estimate how well your
-  implementation performs by running \texttt{knight3.jar} on your
-  computer. For example the reference implementation shows
-  on my laptop:
-  
-  \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp knight3.jar
-  
-scala> M4c.tour_on_mega_board(70, List((0, 0)))
-Time needed: 9.484 secs.
-...<<long_list>>...
-\end{lstlisting}%$
+\pic[fill=red] at (4,2) {king={2}};
+\pic[fill=white] at (7,1) {king={2}};
 
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\\[-5mm]                       
+\end{tabular}
+\end{center}\mbox{}\hfill[1 Mark]
+
+\item[(4)] Implement a function \texttt{attackedN} that takes a piece and a board
+  and calculates the number of times this pieces is attacked by pieces of the opposite colour.
+  For example the piece on field (8, 4) above is attacked by 3 red pieces, and
+  the piece on (6, 1) by 1 white piece.
+  \\
+  \mbox{}\hfill[1 Mark]
+
+\item[(5)] Implement a function \texttt{protectedN} that takes a piece and a board
+  and calculates the number of times this pieces is protected by pieces of the same colour.
+  For example the piece on field (8, 4) above is protected by 1 white pieces (the one on (8, 7)),
+  and the piece on (5, 3) is protected by three red pieces ((6, 1), (4, 2), and (6, 5)).
+  \\
   \mbox{}\hfill[1 Mark]
 \end{itemize}
 
-\subsubsection*{Task 4 (file knight4.scala)}
-\begin{itemize}
-\item[(10)] In this task we want to solve the problem of finding a single
-  tour (if there exists one) on what is sometimes called ``mutilated''
-  chessboards, for example rectangular chessbords or chessboards where
-  fields are missing. For this implement a search function
-
-  \begin{center}
-    \begin{tabular}{@{}l@{}}
-    \texttt{def one\_tour\_pred(dim: Int, path: Path,}\\
-      \texttt{\phantom{def one\_tour\_pred(}n: Int, f: Pos => Boolean): Option[Path]}
-      \end{tabular}
-  \end{center}
-
-  which has, like before, the dimension and current path as arguments,
-  and in addtion it takes an integer, which specifies the length of
-  the longest path (or length of the path after which the search
-  should backtrack), and a function from positions to Booleans. This
-  function acts as a predicate in order to restrict which onward legal
-  moves should be considered in the search. The function
-  \texttt{one\_tour\_pred} should return a single tour
-  (\texttt{Some}-case), if one or more tours exist, and \texttt{None}, if no
-  tour exists. For example when called with 
-
-  \begin{center}
-  \texttt{one\_tour\_pred(7, List((0, 0)), 35, x => x.\_1 < 5)}
-  \end{center}  
-
-  we are looking for a tour starting from position \texttt{(0,0)} on a
-  7 $\times$ 5 board, where the maximum length of the path is 35. The
-  predicate \texttt{x => x.\_1 < 5} ensures that no position with an
-  x-coordinate bigger than 4 is considered. One possible solution is
-
-  \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
-   0   13   22   33   28   11   20 
-  23   32    1   12   21   34   27 
-  14    7   16   29    2   19   10 
-  31   24    5    8   17   26    3 
-   6   15   30   25    4    9   18 
-  -1   -1   -1   -1   -1   -1   -1 
-  -1   -1   -1   -1   -1   -1   -1
-\end{lstlisting}%$
-
-where \texttt{print\_board} prints a \texttt{-1} for all fields that
-have not been visited.
-
-  \mbox{}\hfill[2 Marks]
-\end{itemize}
-
-
-
 \end{document}
 
 %%% Local Variables: 




