# HG changeset patch # User Christian Urban # Date 1542907163 0 # Node ID f968188d4a9bfd490ad97afe65ee5fcba81f04f8 # Parent 4bda49ec24da8544c1c64f3709a00d76850dc69d updated diff -r 4bda49ec24da -r f968188d4a9b cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 4bda49ec24da -r f968188d4a9b cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 4bda49ec24da -r f968188d4a9b cws/cw03.tex --- a/cws/cw03.tex Tue Nov 20 14:31:14 2018 +0000 +++ b/cws/cw03.tex Thu Nov 22 17:19:23 2018 +0000 @@ -3,6 +3,7 @@ \usepackage[LSBC4,T1]{fontenc} \let\clipbox\relax \usepackage{../style} +\usepackage{../langs} \usepackage{disclaimer} \begin{document} @@ -16,7 +17,7 @@ \mbox{}\\[-18mm]\mbox{} -\section*{Coursework 7 (Scala)} +\section*{Coursework 8 (Scala)} This coursework is worth 10\%. It is about searching and backtracking. The first part is due on 29 November at 11pm; the @@ -24,11 +25,11 @@ asked to implement Scala programs that solve various versions of the \textit{Knight's Tour Problem} on a chessboard. Note the second, more advanced, part might include material you have not yet seen in the -first two lectures. \bigskip +first three lectures. \bigskip \IMPORTANT{} Also note that the running time of each part will be restricted to a -maximum of 360 seconds on my laptop: If you calculate a result once, +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}. @@ -138,8 +139,7 @@ chess, below are all potential moves indicated for two knights, one on field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves): - -\chessboard[maxfield=g7, +{\chessboard[maxfield=g7, color=blue!50, linewidth=0.2em, shortenstart=0.5ex, @@ -148,24 +148,61 @@ markfields={a4, c4, Z3, d3, Z1, d1, a0, c0}, color=red!50, markfields={f5, e6}, - setpieces={Ng7, Nb2}] + setpieces={Ng7, Nb2}, + boardfontsize=12pt,labelfontsize=9pt]} + +\subsection*{Reference Implementation} + +The Scala assignment comes with reference implementations in form of +a \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 +template file. + +\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scala -cp knight1.jar + +scala> CW8a.enum_tours(5, List((0, 0))).length +Time needed: 1.722 secs. +res0: Int = 304 + +scala> CW8a.print_board(8, CW8a.first_tour(8, List((0, 0))).get) +Time needed: 15.411 secs. + + 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}%$ + + +\subsection*{Hints} + +\noindent +\textbf{Part 1} 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 functions takes an \texttt{Int} as an argument.\medskip \noindent -\textbf{Hints:} 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}). - -\noindent -\textbf{Hints:} a useful list function: \texttt{.sortBy} sorts a list +\textbf{Part 2} 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}. - -\subsection*{Part 1 (7 Marks)} + + + +\subsection*{Part 1 (6 Marks)} You are asked to implement the knight's tour problem such that the dimension of the board can be changed. Therefore most functions will @@ -178,8 +215,8 @@ \noindent Let us first fix the basic datastructures for the implementation. The -board dimension is an integer (we will never go beyond board sizes of -$40 \times 40$). A \emph{position} (or field) on the chessboard is +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 @@ -244,11 +281,11 @@ 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.}\bigskip + 19591828170979904, respectively.}\smallskip -\subsubsection*{Tasks (file knight2.scala)} +\subsubsection*{Tasks (cont.)} \begin{itemize} \item[(4)] Implement a \texttt{first}-function. This function takes a list of @@ -271,7 +308,9 @@ 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]}. There is one additional point however you should + 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 @@ -279,7 +318,7 @@ is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark] \item[(5)] Implement a \texttt{first\_tour} function that uses the - \texttt{first}-function from (2a), and searches recursively for a tour. + \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] @@ -290,16 +329,10 @@ sizes of up to $8 \times 8$. \bigskip -\noindent -\textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a -list according to a boolean function; a useful option function: -\texttt{.isDefined} returns true, if an option is \texttt{Some(..)}; -anonymous functions can be constructed using \texttt{(x:Int) => ...}, -this functions takes an \texttt{Int} as an argument. %%\newpage -\subsection*{Part 2 (3 Marks)} +\subsection*{Advanced Part 2 (4 Marks)} As you should have seen in Part 1, a naive search for tours beyond $8 \times 8$ boards and also searching for closed tours even on small @@ -333,7 +366,7 @@ 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 knight3.scala)} +\subsubsection*{Tasks (file knight2.scala)} \begin{itemize} \item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of @@ -341,20 +374,48 @@ 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\_heuristic} - function that searches for a - \textbf{closed} tour on a $6\times 6$ board. It should use the - \texttt{first}-function from (4) and tries out onward moves according to - the \texttt{ordered\_moves} function from (3a). It is more likely to find +\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristic} + 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[(8)] Implement a \texttt{first\_tour\_heuristic} function for boards up to - $40\times 40$. It is the same function as in (7) but searches for - tours (not just closed tours). You have to be careful to write a - tail-recursive function of the \texttt{first\_tour\_heuristic} function - otherwise you will get problems with stack-overflows.\\ + $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 start.\\ + %You have to be careful to write a + %tail-recursive function of the \texttt{first\_tour\_heuristic} function + %otherwise you will get problems with stack-overflows.\\ + \mbox{}\hfill[1 Mark] +\end{itemize} + +\subsubsection*{Task (file knight3.scala)} +\begin{itemize} +\item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is + the same function as (7), \textbf{but} can deal with boards up to + $70\times 70$ \textbf{within 30 seconds}. 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 + + The timelimit of 30 secs is with respect to the laptop on which the + marking will happen. You can estimate how well your + implementation performs by running \texttt{knight3.jar} on your + computer. For example: + + \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scala -cp knight3.jar + +scala> CW8c.tour_on_mega_board(70, List((0, 0))) +Time needed: 9.484 secs. +...<>... +\end{lstlisting}%$ + \mbox{}\hfill[1 Mark] \end{itemize} \bigskip diff -r 4bda49ec24da -r f968188d4a9b progs/knight1.scala --- a/progs/knight1.scala Tue Nov 20 14:31:14 2018 +0000 +++ b/progs/knight1.scala Thu Nov 22 17:19:23 2018 +0000 @@ -1,9 +1,19 @@ -// Part 1 about finding and counting Knight's tours -//================================================== +// Part 1 about finding Knight's tours +//===================================== type Pos = (Int, Int) // a position on a chessboard type Path = List[Pos] // a path...a list of positions +// 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 +} + +// for printing a board def print_board(dim: Int, path: Path): Unit = { println for (i <- 0 until dim) { @@ -20,22 +30,22 @@ 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) -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) +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 = +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, -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)) + moves(x).filter(is_legal(dim, path, _)) assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) @@ -62,6 +72,7 @@ } // as far as tasks go +// test cases for CW @@ -79,11 +90,13 @@ println("Number of tours starting from (0, 0)") for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0)))) + 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} " + count_all_tours(dim)) + println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim))) } for (dim <- 1 to 5) { @@ -96,3 +109,49 @@ } +// 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 first_tour(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::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) + +// 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 4bda49ec24da -r f968188d4a9b progs/knight2.scala --- a/progs/knight2.scala Tue Nov 20 14:31:14 2018 +0000 +++ b/progs/knight2.scala Thu Nov 22 17:19:23 2018 +0000 @@ -1,21 +1,81 @@ // Part 2 about finding a single tour for a board //================================================ -// copy any function you need from file knight1.scala - type Pos = (Int, Int) // a position on a chessboard type Path = List[Pos] // a path...a list of positions -//(2a) 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. +// for measuring time +def time_needed[T](n: Int, code: => T) : T = { + val start = System.nanoTime() + for (i <- 0 until n) code + val result = code + val end = System.nanoTime() + println("Time needed: " + (end - start) / 1.0e9 + " secs.") + result +} + -def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = ... +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%3.0f ") + } + println + } +} + +def add_pair(x: Pos)(y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +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) + +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)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path)) + -//(2b) Implement a function that uses the first-function for -// trying out onward moves, and searches recursively for an -// *open* tour on a dim * dim-board. +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) + } +} + +first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None)) +first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None)) + + + +def first_tour(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path)) +} -def first_tour(dim: Int, path: Path): Option[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) + +// 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 4bda49ec24da -r f968188d4a9b progs/knight3.scala --- a/progs/knight3.scala Tue Nov 20 14:31:14 2018 +0000 +++ b/progs/knight3.scala Thu Nov 22 17:19:23 2018 +0000 @@ -1,24 +1,124 @@ // Part 3 about finding a single tour using the Warnsdorf Rule //============================================================= -// copy any function you need from files knight1.scala and -// knight2.scala + +type Pos = (Int, Int) +type Path = List[Pos] + +// for measuring time +def time_needed[T](n: Int, code: => T) : T = { + val start = System.nanoTime() + for (i <- 0 until n) code + val result = code + val end = System.nanoTime() + println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") + result +} + +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%4.0f ") + } + println + } +} + +def add_pair(x: Pos, y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions +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) + +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, _)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path, _)) + +def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = + legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) -//(3a) Complete the function that calculates a list of onward -// moves like in (1b) but orders them according to the Warnsdorf’s -// rule. That means moves with the fewest legal onward moves -// should come first. +import scala.annotation.tailrec + +@tailrec +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) + } +} + + +//def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = +// xs.flatMap(f(_)).headOption + -def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = .. +def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path)) +} + +// heuristic cannot be used to search for closed tours on 7 x 7 +for (dim <- 1 to 6) { + val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2)))) + println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +} + -//(3b) Complete the function that searches for a single *closed* -// tour using the ordered moves function. +//@tailrec +/* +def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { + + @tailrec + def aux(dim: Int, path: Path, moves: List[Pos]): Option[Path] = + if (path.length == dim * dim) Some(path) + else + moves match { + case Nil => None + case x::xs => { + val r = first_tour_heuristics(dim, x::path) + if (r.isDefined) r else aux(dim, path, xs) + } + } + + aux(dim, path, ordered_moves(dim, path, path.head)) +} +*/ -def first_closed_tour_heuristic(dim: Int, path: Path): Option[Path] = ... +@tailrec +def tour_on_mega_board(dim: Int, paths: List[Path]): Option[Path] = paths match { + case Nil => None + case (path::rest) => + if (path.length == dim * dim) Some(path) + else tour_on_mega_board(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest) +} + + -//(3c) Same as (3b) but searches for *open* tours. +/* +def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + for (p <- ordered_moves(dim, path, path.head)) + val r = first_tour_heuristics(dim, x::path) + //first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path)) + ordered_moves(dim, path, path.head).view.flatMap((x: Pos) => first_tour_heuristics(dim, x::path)).headOption +} +*/ -def first_tour_heuristic(dim: Int, path: Path): Option[Path] = ... +/* +for (dim <- 1 to 50) { + val t = first_tour_heuristics(dim, List((dim / 2, dim / 2))) + println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +} +*/ + +val dim = 70 +println(s"${dim} x ${dim}:") +print_board(dim, time_needed(0, tour_on_mega_board(dim, List(List((0, 0)))).get)) + diff -r 4bda49ec24da -r f968188d4a9b solutions3/knight1.jar Binary file solutions3/knight1.jar has changed diff -r 4bda49ec24da -r f968188d4a9b solutions3/knight1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/solutions3/knight1.scala Thu Nov 22 17:19:23 2018 +0000 @@ -0,0 +1,173 @@ +// Part 1 about finding and counting Knight's tours +//================================================== + +object CW8a { // 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(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) + +// 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 4bda49ec24da -r f968188d4a9b solutions3/knight2.jar Binary file solutions3/knight2.jar has changed diff -r 4bda49ec24da -r f968188d4a9b solutions3/knight2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/solutions3/knight2.scala Thu Nov 22 17:19:23 2018 +0000 @@ -0,0 +1,89 @@ +// Part 3 about finding a single tour using the Warnsdorf Rule +//============================================================= + +object CW8b { // for preparing the jar + +type Pos = (Int, Int) +type Path = List[Pos] + + +// 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 +} + + +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%4.0f ") + } + println + } +} + +def add_pair(x: Pos, y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +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) + +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, _)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path, _)) + +def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = + legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) + +import scala.annotation.tailrec + +@tailrec +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) + } +} + + +def tfirst_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_closed_tour_heuristics(dim, x::path)) +} + +def first_closed_tour_heuristics(dim: Int, path: Path) = + time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path)) + + +// heuristic cannot be used to search for closed tours on 7 x 7 an beyond +//for (dim <- 1 to 6) { +// val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2)))) +// println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +//} + + +def tfirst_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_tour_heuristics(dim, x::path)) +} + + +def first_tour_heuristics(dim: Int, path: Path) = + time_needed(tfirst_tour_heuristics(dim: Int, path: Path)) + + +// will be called with boards up to 30 x 30 + + +} diff -r 4bda49ec24da -r f968188d4a9b solutions3/knight3.jar Binary file solutions3/knight3.jar has changed diff -r 4bda49ec24da -r f968188d4a9b solutions3/knight3.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/solutions3/knight3.scala Thu Nov 22 17:19:23 2018 +0000 @@ -0,0 +1,63 @@ +// Part 3 about finding a single tour using the Warnsdorf Rule +//============================================================= + +object CW8c { // for preparing the jar + +type Pos = (Int, Int) +type Path = List[Pos] + + +// 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 +} + + +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%4.0f ") + } + println + } +} + +def add_pair(x: Pos, y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +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) + +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, _)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path, _)) + +def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = + legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) + +import scala.annotation.tailrec + +@tailrec +def tour_on_mega_board_aux(dim: Int, paths: List[Path]): Option[Path] = paths match { + case Nil => None + case (path::rest) => + if (path.length == dim * dim) Some(path) + else tour_on_mega_board_aux(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest) +} + +def ttour_on_mega_board(dim: Int, path: Path): Option[Path] = + tour_on_mega_board_aux(dim, List(path)) + + +def tour_on_mega_board(dim: Int, path: Path) = + time_needed(ttour_on_mega_board(dim: Int, path: Path)) + +}