--- a/cws/main_cw04.tex Fri Nov 05 16:47:55 2021 +0000
+++ b/cws/main_cw04.tex Fri Nov 05 17:20:01 2021 +0000
@@ -19,7 +19,7 @@
\mbox{}\\[-18mm]\mbox{}
-\section*{Preliminary and Main Part 4 (Scala, 4 + 6 Marks)}
+\section*{Main Part 4 (Scala, 9 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}\\
@@ -29,11 +29,14 @@
\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. The preliminary part (4\%) is
-due on \sout{\cwNINE{}} \textcolor{red}{16 December} at 5pm; the core part (6\%) is due on \cwNINEa{} at 5pm.
-Any 1\% you achieve in the preliminary part counts as your ``weekly engagement''.
+\textit{Knight's Tour Problem} on a chessboard.
+% The preliminary part (4\%) is due on \sout{\cwNINE{}}
+% \textcolor{red}{16 December} at 5pm; the core part (6\%)
+% is due on \cwNINEa{} at 5pm. Any 1\% you achieve in the
+% preliminary part counts as your ``weekly engagement''.
\bigskip
-%Note the core, more advanced, part might include material you have not
+
+% Note the core, more advanced, part might include material you have not
%yet seen in the first three lectures. \bigskip
\IMPORTANTNONE{}
@@ -164,9 +167,9 @@
\subsection*{Reference Implementation}
-\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from KEATS. The one
-supplied with github does not contain the correct code. See Scala coursework
-section on KEATS.}\medskip
+%\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
\noindent
This Scala part comes with three reference implementations in form of
@@ -174,17 +177,17 @@
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{CW9a}, \texttt{CW9b} and \texttt{CW9c}.
+prefix the calls with \texttt{M4a}, \texttt{M4b} and \texttt{M4c}.
Since some of the calls are time sensitive, I included some timing
information. For example
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ scala -cp knight1.jar
-scala> CW9a.enum_tours(5, List((0, 0))).length
+scala> M4a.enum_tours(5, List((0, 0))).length
Time needed: 1.722 secs.
res0: Int = 304
-scala> CW9a.print_board(8, CW9a.first_tour(8, List((0, 0))).get)
+scala> M4a.print_board(8, M4a.first_tour(8, List((0, 0))).get)
Time needed: 15.411 secs.
51 46 55 44 53 4 21 12
@@ -201,18 +204,15 @@
\subsection*{Hints}
\noindent
-\textbf{Preliminary Part} useful list functions: \texttt{.contains(..)} checks
+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.\medskip
-
-
-\noindent
-\textbf{Main Part} a useful list function: \texttt{.sortBy} sorts a list
+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
@@ -220,7 +220,7 @@
-\subsection*{Preliminary Part (4 Marks)}
+\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
@@ -254,7 +254,7 @@
knight moves (see above for the rules).
-\subsubsection*{Tasks (file knight1.scala)}
+\subsubsection*{Task 1 (file knight1.scala)}
@@ -294,9 +294,9 @@
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[2 Marks]
+ \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)$,
@@ -307,18 +307,6 @@
$6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
19591828170979904, respectively.}\smallskip
-
-\subsection*{Core Part (6 Marks)}
-
-
-\subsubsection*{Tasks (file knight1.scala cont.)}
-
-\mbox{}\alert{}\textcolor{red}{You need to copy your \texttt{knight1.scala}
- from the preliminary part to the main part and then solve Tasks 4 and 5
- inside the copied file. Do not forget to ``git add'' the file for
- pushing the results to the directory \texttt{main4}.}\medskip
-
-
\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
@@ -353,7 +341,7 @@
\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]
+ \texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark]
\end{itemize}
\noindent
@@ -362,6 +350,7 @@
\bigskip
%%\newpage
+\subsubsection*{Task 2 (file knight2.scala)}
\noindent
As you should have seen in the earlier parts, a naive search for tours beyond
@@ -396,8 +385,6 @@
order. When calculating the number of onward moves for each field, we
do not count moves that revisit any field already visited.
-\subsubsection*{Tasks (file knight2.scala)}
-
\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
@@ -423,7 +410,7 @@
\mbox{}\hfill[1 Mark]
\end{itemize}
-\subsubsection*{Task (file knight3.scala)}
+\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
@@ -443,7 +430,7 @@
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ scala -cp knight3.jar
-scala> CW9c.tour_on_mega_board(70, List((0, 0)))
+scala> M4c.tour_on_mega_board(70, List((0, 0)))
Time needed: 9.484 secs.
...<<long_list>>...
\end{lstlisting}%$
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_solution4/knight1.scala Fri Nov 05 17:20:01 2021 +0000
@@ -0,0 +1,177 @@
+// Part 1 about finding and counting Knight's tours
+//==================================================
+
+object CW9a { // for preparing the jar
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+
+// for measuring time in the JAR
+def time_needed[T](code: => T) : T = {
+ val start = System.nanoTime()
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+// for printing a board
+def print_board(dim: Int, path: Path): Unit = {
+ println()
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+ }
+ println()
+ }
+}
+
+def is_legal(dim: Int, path: Path, x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+// testcases
+//assert(is_legal(8, Nil, (3, 4)) == true)
+//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
+//assert(is_legal(2, Nil, (0, 0)) == true)
+
+
+def add_pair(x: Pos, y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _))
+
+// 1 mark
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path, _))
+
+
+
+// testcases
+//assert(legal_moves(8, Nil, (2,2)) ==
+// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0)))
+//assert(legal_moves(1, Nil, (0,0)) == List())
+//assert(legal_moves(2, Nil, (0,0)) == List())
+//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+// 2 marks
+
+def tcount_tours(dim: Int, path: Path): Int = {
+ if (path.length == dim * dim) 1
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum
+}
+
+def count_tours(dim: Int, path: Path) =
+ time_needed(tcount_tours(dim: Int, path: Path))
+
+
+def tenum_tours(dim: Int, path: Path): List[Path] = {
+ if (path.length == dim * dim) List(path)
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten
+}
+
+def enum_tours(dim: Int, path: Path) =
+ time_needed(tenum_tours(dim: Int, path: Path))
+
+// test cases
+
+/*
+def count_all_tours(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
+
+def enum_all_tours(dim: Int): List[Path] = {
+ (for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+
+
+println("Number of tours starting from (0, 0)")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
+}
+
+println("Number of tours starting from all fields")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
+}
+
+for (dim <- 1 to 5) {
+ val ts = enum_tours(dim, List((0, 0)))
+ println(s"${dim} x ${dim} ")
+ if (ts != Nil) {
+ print_board(dim, ts.head)
+ println(ts.head)
+ }
+}
+*/
+
+// 1 mark
+
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+ case Nil => None
+ case x::xs => {
+ val result = f(x)
+ if (result.isDefined) result else first(xs, f)
+ }
+}
+
+// test cases
+//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
+//
+//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
+//first(List((1, 0),(2, 0),(3, 0)), foo)
+
+
+// 1 mark
+
+def tfirst_tour(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))
+}
+
+def first_tour(dim: Int, path: Path) =
+ time_needed(tfirst_tour(dim: Int, path: Path))
+
+
+/*
+for (dim <- 1 to 8) {
+ val t = first_tour(dim, List((0, 0)))
+ println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+// 15 secs for 8 x 8
+//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
+//val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
+
+// no result for 4 x 4
+//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
+
+// 0.3 secs for 6 x 6
+//val ts3 = time_needed(0, first_tour(6, List((0, 0))))
+
+// 15 secs for 8 x 8
+//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
+
+
+
+
+
+}
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_templates4/knight1.scala Fri Nov 05 17:20:01 2021 +0000
@@ -0,0 +1,107 @@
+// Main Part 4 about finding Knight's tours
+//==========================================
+
+
+object M4a {
+
+// If you need any auxiliary function, feel free to
+// implement it, but do not make any changes to the
+// templates below. Also have a look whether the functions
+// at the end are of any help.
+
+
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+//(1) Complete the function that tests whether the position x
+// is inside the board and not yet element in the path.
+
+def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ???
+
+
+
+//(2) Complete the function that calculates for a position x
+// all legal onward moves that are not already in the path.
+// The moves should be ordered in a "clockwise" manner.
+
+def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ???
+
+
+//some testcases
+//
+//assert(legal_moves(8, Nil, (2,2)) ==
+// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+
+
+//(3) Complete the two recursive functions below.
+// They exhaustively search for knight's tours starting from the
+// given path. The first function counts all possible tours,
+// and the second collects all tours in a list of paths.
+
+def count_tours(dim: Int, path: Path) : Int = ???
+
+def enum_tours(dim: Int, path: Path) : List[Path] = ???
+
+
+//(4) Implement a first-function that finds the first
+// element, say x, in the list xs where f is not None.
+// In that case Return f(x), otherwise None. If possible,
+// calculate f(x) only once.
+
+def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ???
+
+
+// testcases
+//
+//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
+//
+//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0)))
+//first(List((1, 0),(2, 0),(3, 0)), foo) // None
+
+
+//(5) Implement a function that uses the first-function from (4) for
+// trying out onward moves, and searches recursively for a
+// knight tour on a dim * dim-board.
+
+def first_tour(dim: Int, path: Path) : Option[Path] = ???
+
+
+
+/* Helper functions
+
+
+// for measuring time
+def time_needed[T](code: => T) : T = {
+ val start = System.nanoTime()
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+// can be called for example with
+// time_needed(count_tours(dim, List((0, 0))))
+// in order to print out the time that is needed for
+// running count_tours
+
+
+// for printing a board
+def print_board(dim: Int, path: Path): Unit = {
+ println()
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+ }
+ println()
+ }
+}
+
+
+*/
+
+}
--- a/main_templates4/knight2.scala Fri Nov 05 16:47:55 2021 +0000
+++ b/main_templates4/knight2.scala Fri Nov 05 17:20:01 2021 +0000
@@ -2,7 +2,7 @@
// Warnsdorf Rule
//==============================================================
-object CW9b {
+object M4b {
// !!! Copy any function you need from file knight1.scala !!!
--- a/main_templates4/knight3.scala Fri Nov 05 16:47:55 2021 +0000
+++ b/main_templates4/knight3.scala Fri Nov 05 17:20:01 2021 +0000
@@ -1,7 +1,7 @@
// Finding a single tour on a "mega" board
//=========================================
-object CW9c {
+object M4c {
// !!! Copy any function you need from file knight1.scala !!!
// !!! or knight2.scala !!!
--- a/pre_solution4/knight1.scala Fri Nov 05 16:47:55 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,177 +0,0 @@
-// Part 1 about finding and counting Knight's tours
-//==================================================
-
-object CW9a { // for preparing the jar
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-
-// for measuring time in the JAR
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-// for printing a board
-def print_board(dim: Int, path: Path): Unit = {
- println()
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
- }
- println()
- }
-}
-
-def is_legal(dim: Int, path: Path, x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-// testcases
-//assert(is_legal(8, Nil, (3, 4)) == true)
-//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
-//assert(is_legal(2, Nil, (0, 0)) == true)
-
-
-def add_pair(x: Pos, y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _))
-
-// 1 mark
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path, _))
-
-
-
-// testcases
-//assert(legal_moves(8, Nil, (2,2)) ==
-// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
-// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0)))
-//assert(legal_moves(1, Nil, (0,0)) == List())
-//assert(legal_moves(2, Nil, (0,0)) == List())
-//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
-
-// 2 marks
-
-def tcount_tours(dim: Int, path: Path): Int = {
- if (path.length == dim * dim) 1
- else
- (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum
-}
-
-def count_tours(dim: Int, path: Path) =
- time_needed(tcount_tours(dim: Int, path: Path))
-
-
-def tenum_tours(dim: Int, path: Path): List[Path] = {
- if (path.length == dim * dim) List(path)
- else
- (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten
-}
-
-def enum_tours(dim: Int, path: Path) =
- time_needed(tenum_tours(dim: Int, path: Path))
-
-// test cases
-
-/*
-def count_all_tours(dim: Int) = {
- for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
-}
-
-def enum_all_tours(dim: Int): List[Path] = {
- (for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
-}
-
-
-println("Number of tours starting from (0, 0)")
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
-}
-
-println("Number of tours starting from all fields")
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
-}
-
-for (dim <- 1 to 5) {
- val ts = enum_tours(dim, List((0, 0)))
- println(s"${dim} x ${dim} ")
- if (ts != Nil) {
- print_board(dim, ts.head)
- println(ts.head)
- }
-}
-*/
-
-// 1 mark
-
-def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
- case Nil => None
- case x::xs => {
- val result = f(x)
- if (result.isDefined) result else first(xs, f)
- }
-}
-
-// test cases
-//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
-//
-//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
-//first(List((1, 0),(2, 0),(3, 0)), foo)
-
-
-// 1 mark
-
-def tfirst_tour(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))
-}
-
-def first_tour(dim: Int, path: Path) =
- time_needed(tfirst_tour(dim: Int, path: Path))
-
-
-/*
-for (dim <- 1 to 8) {
- val t = first_tour(dim, List((0, 0)))
- println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-// 15 secs for 8 x 8
-//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
-//val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
-
-// no result for 4 x 4
-//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
-
-// 0.3 secs for 6 x 6
-//val ts3 = time_needed(0, first_tour(6, List((0, 0))))
-
-// 15 secs for 8 x 8
-//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
-
-
-
-
-
-}
-
-
Binary file pre_templates4/knight1.jar has changed
--- a/pre_templates4/knight1.scala Fri Nov 05 16:47:55 2021 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,107 +0,0 @@
-// Preliminary Part about finding Knight's tours
-//===============================================
-
-
-object CW9a {
-
-// If you need any auxiliary function, feel free to
-// implement it, but do not make any changes to the
-// templates below. Also have a look whether the functions
-// at the end are of any help.
-
-
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-//(1) Complete the function that tests whether the position x
-// is inside the board and not yet element in the path.
-
-def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ???
-
-
-
-//(2) Complete the function that calculates for a position x
-// all legal onward moves that are not already in the path.
-// The moves should be ordered in a "clockwise" manner.
-
-def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ???
-
-
-//some testcases
-//
-//assert(legal_moves(8, Nil, (2,2)) ==
-// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
-// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-
-
-//(3) Complete the two recursive functions below.
-// They exhaustively search for knight's tours starting from the
-// given path. The first function counts all possible tours,
-// and the second collects all tours in a list of paths.
-
-def count_tours(dim: Int, path: Path) : Int = ???
-
-def enum_tours(dim: Int, path: Path) : List[Path] = ???
-
-
-//(4) Implement a first-function that finds the first
-// element, say x, in the list xs where f is not None.
-// In that case Return f(x), otherwise None. If possible,
-// calculate f(x) only once.
-
-def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ???
-
-
-// testcases
-//
-//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
-//
-//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0)))
-//first(List((1, 0),(2, 0),(3, 0)), foo) // None
-
-
-//(5) Implement a function that uses the first-function from (5) for
-// trying out onward moves, and searches recursively for a
-// knight tour on a dim * dim-board.
-
-def first_tour(dim: Int, path: Path) : Option[Path] = ???
-
-
-
-/* Helper functions
-
-
-// for measuring time
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-// can be called for example with
-// time_needed(count_tours(dim, List((0, 0))))
-// in order to print out the time that is needed for
-// running count_tours
-
-
-// for printing a board
-def print_board(dim: Int, path: Path): Unit = {
- println()
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
- }
- println()
- }
-}
-
-
-*/
-
-}