# HG changeset patch # User Christian Urban # Date 1636132801 0 # Node ID 085fefce672ef3488c6f28a8c04294f33fa0b053 # Parent 3ffe978a5664841c5729eed575ee893f04edab00 updated diff -r 3ffe978a5664 -r 085fefce672e cws/main_cw04.tex --- 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. ...<>... \end{lstlisting}%$ diff -r 3ffe978a5664 -r 085fefce672e main_solution4/knight1.scala --- /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)) + + + + + +} + + diff -r 3ffe978a5664 -r 085fefce672e main_templates4/knight1.scala --- /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() + } +} + + +*/ + +} diff -r 3ffe978a5664 -r 085fefce672e main_templates4/knight2.scala --- 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 !!! diff -r 3ffe978a5664 -r 085fefce672e main_templates4/knight3.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 !!! diff -r 3ffe978a5664 -r 085fefce672e pre_solution4/knight1.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)) - - - - - -} - - diff -r 3ffe978a5664 -r 085fefce672e pre_templates4/knight1.jar Binary file pre_templates4/knight1.jar has changed diff -r 3ffe978a5664 -r 085fefce672e pre_templates4/knight1.scala --- 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() - } -} - - -*/ - -}