Binary file cws/cw02.pdf has changed
Binary file cws/cw03.pdf has changed
--- 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.
+...<<long_list>>...
+\end{lstlisting}%$
+
\mbox{}\hfill[1 Mark]
\end{itemize}
\bigskip
--- 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))
+
--- 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))
+
+
--- 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))
+
Binary file solutions3/knight1.jar has changed
--- /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))
+
+
+
+
+
+}
+
+
Binary file solutions3/knight2.jar has changed
--- /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
+
+
+}
Binary file solutions3/knight3.jar has changed
--- /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))
+
+}