diff -r 59e005dcf163 -r 7550c816187a 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. -...<>... -\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: