--- a/cws/cw02.tex Sun Nov 13 17:14:29 2016 +0000
+++ b/cws/cw02.tex Mon Nov 14 03:25:14 2016 +0000
@@ -6,16 +6,17 @@
\begin{document}
\setchessboard{smallboard,
+ zero,
showmover=false,
boardfontencoding=LSBC4,
hlabelformat=\arabic{ranklabel},
vlabelformat=\arabic{filelabel}}
-
+\mbox{}\\[-18mm]\mbox{}
\section*{Coursework 7 (Scala, Knight's Tour)}
-This coursework is about depth-first search in Scala and worth
+This coursework is about searching and backtracking, and worth
10\%. The first part is due on 23 November at 11pm; the second, more
advanced part, is due on 30 November at 11pm. You are asked to
implement Scala programs that solve various versions of the
@@ -28,94 +29,269 @@
It should be understood that the work you submit represents
your own effort. You have not copied from anyone else. An
exception is the Scala code I showed during the lectures or
-uploaded to KEATS, which you can freely use.\bigskip
+uploaded to KEATS, which you can freely use.\medskip
\subsection*{Background}
The \textit{Knight's Tour Problem} is about finding a tour such that
-the knight visits every field on a $n\times n$ chessboard once and
-only once. For example on a $5\times 5$ chessboard, a knight's tour is
-as follows:
+the knight visits every field on an $n\times n$ chessboard once. For
+example on a $5\times 5$ chessboard, a knight's tour is:
+
+\chessboard[maxfield=d4,
+ pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+ text = \small 24, markfield=Z4,
+ text = \small 11, markfield=a4,
+ text = \small 6, markfield=b4,
+ text = \small 17, markfield=c4,
+ text = \small 0, markfield=d4,
+ text = \small 19, markfield=Z3,
+ text = \small 16, markfield=a3,
+ text = \small 23, markfield=b3,
+ text = \small 12, markfield=c3,
+ text = \small 7, markfield=d3,
+ text = \small 10, markfield=Z2,
+ text = \small 5, markfield=a2,
+ text = \small 18, markfield=b2,
+ text = \small 1, markfield=c2,
+ text = \small 22, markfield=d2,
+ text = \small 15, markfield=Z1,
+ text = \small 20, markfield=a1,
+ text = \small 3, markfield=b1,
+ text = \small 8, markfield=c1,
+ text = \small 13, markfield=d1,
+ text = \small 4, markfield=Z0,
+ text = \small 9, markfield=a0,
+ text = \small 14, markfield=b0,
+ text = \small 21, markfield=c0,
+ text = \small 2, markfield=d0
+ ]
+
+\noindent
+The tour starts in the right-upper corner, then moves to field
+$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
+$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
+bigger board there is.
+
+A knight's tour is called \emph{closed}, if the last step in the tour
+is within a knight's move to the beginning of the tour. So the above
+knight's tour is \underline{not} closed (it is open) because the last
+step on field $(0, 4)$ is not within the reach of the first step on
+$(4, 4)$. It turns out there is no closed knight's tour on a $5\times
+5$ board. But there are on a $6\times 6$ board, for example
\chessboard[maxfield=e5,
pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
- text = \bf\small 24, markfield=a5,
- text = \small 11, markfield=b5,
- text = \small 6, markfield=c5,
- text = \small 17, markfield=d5,
- text = \small 0, markfield=e5,
- text = \small 19, markfield=a4,
- text = \small 16, markfield=b4,
- text = \small 23, markfield=c4,
- text = \small 12, markfield=d4,
- text = \small 7, markfield=e4,
- text = \small 10, markfield=a3,
- text = \small 5, markfield=b3,
- text = \small 18, markfield=c3,
- text = \small 1, markfield=d3,
- text = \small 22, markfield=e3,
- text = \small 15, markfield=a2,
- text = \small 20, markfield=b2,
- text = \small 3, markfield=c2,
- text = \small 8, markfield=d2,
- text = \small 13, markfield=e2,
- text = \small 4, markfield=a1,
- text = \small 9, markfield=b1,
- text = \small 14, markfield=c1,
- text = \small 21, markfield=d1,
- text = \small 2, markfield=e1
+ text = \small 10, markfield=Z5,
+ text = \small 5, markfield=a5,
+ text = \small 18, markfield=b5,
+ text = \small 25, markfield=c5,
+ text = \small 16, markfield=d5,
+ text = \small 7, markfield=e5,
+ text = \small 31, markfield=Z4,
+ text = \small 26, markfield=a4,
+ text = \small 9, markfield=b4,
+ text = \small 6, markfield=c4,
+ text = \small 19, markfield=d4,
+ text = \small 24, markfield=e4,
+ % 4 11 30 17 8 15
+ text = \small 4, markfield=Z3,
+ text = \small 11, markfield=a3,
+ text = \small 30, markfield=b3,
+ text = \small 17, markfield=c3,
+ text = \small 8, markfield=d3,
+ text = \small 15, markfield=e3,
+ %29 32 27 0 23 20
+ text = \small 29, markfield=Z2,
+ text = \small 32, markfield=a2,
+ text = \small 27, markfield=b2,
+ text = \small 0, markfield=c2,
+ text = \small 23, markfield=d2,
+ text = \small 20, markfield=e2,
+ %12 3 34 21 14 1
+ text = \small 12, markfield=Z1,
+ text = \small 3, markfield=a1,
+ text = \small 34, markfield=b1,
+ text = \small 21, markfield=c1,
+ text = \small 14, markfield=d1,
+ text = \small 1, markfield=e1,
+ %33 28 13 2 35 22
+ text = \small 33, markfield=Z0,
+ text = \small 28, markfield=a0,
+ text = \small 13, markfield=b0,
+ text = \small 2, markfield=c0,
+ text = \small 35, markfield=d0,
+ text = \small 22, markfield=e0,
+ vlabel=false,
+ hlabel=false
]
+
\noindent
-The tour starts in the right-upper corner, then moves to field $(4,3)$,
-then $(5,1)$ and so on. There are no knight's tours on $2\times 2$, $3\times 3$
-and $4\times 4$ chessboards, but for every bigger board there is.
+where the 35th move can join up again with the 0th move.
+
+If you cannot remember how a knight moved in chess, or never played
+chess, below are all potential moves indicated for two knights, one on
+field $(2, 2)$ (blue) and another on $(7, 7)$ (red):
-A knight's tour is called \emph{closed}, if
-the last step in the tour is within a knight's move to the beginning
-of the tour. So the above knight's tour is \underline{not} closed (it is
-open) because the last step on field $(1, 5)$ is not within the reach
-of the first step on $(5, 5)$. It turns out there is no closed
-knight's tour on a $5\times 5$ board. But there are on a $6\times
-6$ board.\bigskip
-
-\noindent
-If you cannot remember how a knight moved in chess, or never played
-chess, below are all potential moves indicated for two knights, one on
-field $(3, 3)$ and another on $(8, 8)$:
-
-
-\chessboard[color=blue!50,
+\chessboard[maxfield=g7,
+ color=blue!50,
linewidth=0.2em,
shortenstart=0.5ex,
shortenend=0.5ex,
markstyle=cross,
- markfields={b5, d5, a4, e4, a2, e2, b1, d1},
+ markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
color=red!50,
- markfields={g6, f7},
- setpieces={Nh8, Nc3}]
+ markfields={f5, e6},
+ setpieces={Ng7, Nb2}]
+
+\subsection*{Part 1 (6 Marks)}
+
+We will implement the knight's tour problem such that we can change
+quickly the dimension of the chessboard. The fun with this problem is
+that even for small chessbord dimensions it has already an incredably
+large search space---finding a tour is like finding a needle in a
+haystack. In the first part we want to see far we get with
+exhaustively exploring the complete search space for small dimensions.
+Let us first fix the basic datastructures for the implementation. A
+\emph{position} (or field) on the chessboard is a pair of integers. A
+\emph{path} is a list of positions. The first (or 0th move) in a path
+should be the last element in this list; and the last move is the
+first element. For example the path for the $5\times 5$ chessboard
+above is represented by
+\[
+\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
+ $\underbrace{\texttt{(2, 3)}}_{23}$, ..., (3, 2), $\underbrace{\texttt{(4, 4)}}_0$)}
+\]
+
+\noindent
+Suppose the dimension of a chessboard is $n$, then a path is a
+\emph{tour} if the length of the path is $n \times n$, each element
+occurs only once in the path, and each move follows the rules of how a
+knight moves (see above for the rules).
-\subsubsection*{Task}
+\subsubsection*{Tasks (file knight1.scala)}
+
+\begin{itemize}
+\item[(1a)] Implement a is-legal-move function that takes a dimension, a path
+and a position as argument and tests whether the position is inside
+the board and not yet element in the path.
+
+\item[(1b)] Implement a legal-moves function that calculates for a
+ position all legal follow-on moves. If the follow-on moves are
+ placed on a circle, you should produce them starting from
+ ``12-oclock'' following in clockwise order. For example on an
+ $8\times 8$ board for a knight on position $(2, 2)$ and otherwise
+ empty board, the legal-moves function should produce the follow-on
+ positions
-The task is to implement a regular expression matcher based on
-derivatives of regular expressions. The implementation should
-be able to deal with the usual (basic) regular expressions
+ \begin{center}
+ \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
+ \end{center}
+
+ If the board is not empty, then maybe some of the moves need to be filtered out from this list.
+ For a knight on field $(7, 7)$ and an empty board, the legal moves
+ are
+
+ \begin{center}
+ \texttt{List((6,5), (5,6))}
+ \end{center}
+
+\item[(1c)] Implement two recursive functions (count-tours and
+ enum-tours). They each take a dimension and a path as
+ arguments. They exhaustively search for \underline{open} tours
+ starting from the given path. The first function counts all possible
+ open tours (there can be none for certain board sizes) and the second
+ collects all open tours in a list of paths.
+\end{itemize}
-\noindent {\bf Important!} Your implementation should have
-explicit cases for the basic regular expressions, but also
-explicit cases for the extended regular expressions. That
-means do not treat the extended regular expressions by just
-translating them into the basic ones. See also Question 2,
-where you are asked to explicitly give the rules for
-\textit{nullable} and \textit{der} for the extended regular
-expressions.
+\noindent \textbf{Test data:} For the marking, these functions will be
+called with board sizes up to $5 \times 5$. If you only search for
+open tours starting from field $(0, 0)$, there are 304 of them. If you
+try out every field of a $5 \times 5$-board as a starting field and
+add up all open tours, you obtain 1728. A $6\times 6$ board is already
+too large to search exhaustively: the number of open tours on
+$6\times 6$, $7\times 7$ and $8\times 8$ are
+
+\begin{center}
+\begin{tabular}{ll}
+ $6\times 6$ & 6637920\\
+ $7\times 7$ & 165575218320\\
+ $8\times 8$ & 19591828170979904
+\end{tabular}
+\end{center}
+
+\subsubsection*{Tasks (file knight2.scala)}
+
+\begin{itemize}
+\item[(2a)] Implement a first-function. This function takes a list of
+ positions and a function $f$ as arguments. The function $f$ takes a
+ position as argument and produces an optional path. The idea behind
+ the first-function is as follows:
+
+ \[
+ \begin{array}{lcl}
+ first(\texttt{Nil}, f) & \dn & \texttt{None}\\
+ first(x\!::\!xs, f) & \dn & \begin{cases}
+ f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
+ first(xs, f) & \textit{otherwise}\\
+ \end{cases}
+ \end{array}
+ \]
+
+\item[(2b)] Implement a first-tour function. Using the first-function
+ from (2a), search recursively for an open tour. Only use the field
+ $(0, 0)$ as a starting field of the tour. As there might not be such
+ a tour at all, the first-tour function needs to return an
+ \texttt{Option[Path]}. For the marking, this function will be called
+ with board sizes up to $8 \times 8$.
+\end{itemize}
+\subsection*{Part 2 (4 Marks)}
+
+For open tours beyond $8 \times 8$ boards and also for searching for
+closed tours, an heuristic (called Warnsdorf's rule) needs to be
+implemented. This rule states that a knight is moved so that it
+always proceeds to the square from which the knight will have the
+fewest onward moves. For example for a knight on field $(1, 3)$,
+the field $(0, 1)$ has the fewest possible onward moves.
+
+\chessboard[maxfield=g7,
+ pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+ text = \small 3, markfield=Z5,
+ text = \small 7, markfield=b5,
+ text = \small 7, markfield=c4,
+ text = \small 7, markfield=c2,
+ text = \small 5, markfield=b1,
+ text = \small 2, markfield=Z1,
+ setpieces={Na3}]
+
+\noindent
+Warnsdorf's rule states that the moves sould be tried out in the
+order
+
+\[
+(0, 1), (0, 5), (2, 5), (3, 4), (3, 2)
+\]
+
+Whenever there are ties, the correspoding onward moves can be in any
+order. When calculating the number of onward moves for each field, we
+do not count moves that revisit any field already visited.
+
+\subsubsection*{Tasks (file knight3.scala)}
+
+\begin{itemize}
+\item[(3a)] orderered-moves
+
+\item[(3b)] first-closed tour heuristics; up to $6\times 6$
+
+\item[(3c)] first tour heuristics; up to $50\times 50$
+\end{itemize}
\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/k1_sol.scala Mon Nov 14 03:25:14 2016 +0000
@@ -0,0 +1,132 @@
+// Part 1 about finding anod counting Knight's tours
+//===================================================
+
+
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+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 dist(dim: Int, y: Pos) =
+ (dim / 2 - y._1).abs + (dim / 2 - y._2).abs
+
+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, dist(dim, x)))
+
+
+//moves(8)(1,3)
+//ordered_moves(8)(Nil)(1,3)
+//ordered_moves(8)(List((2, 4), (2, 6)))(1,3)
+
+
+
+def count_tours(dim: Int, path: Path): Int = {
+ if (path.length == dim * dim) 1
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
+}
+
+def enum_tours(dim: Int, path: Path): List[Path] = {
+ if (path.length == dim * dim) List(path)
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
+}
+
+def count_all_tours(dim: Int): Int = {
+ (for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))).sum
+}
+
+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
+}
+
+/*
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + count_all_tours(dim))
+}
+
+for (dim <- 1 to 5) {
+ val ts = enum_all_tours(dim)
+ println(s"${dim} x ${dim} " + (if (ts == Nil) "" else { print_board(dim, ts.head) ; "" }))
+}
+*/
+
+
+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_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) ; "" }))
+}
+
+
+/*
+def first2[A, B](xs: List[A], f: A => Option[B]): Option[B] =
+ xs.par.flatMap(f(_)).headOption
+*/
+
+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))
+}
+
+
+for (dim <- 1 to 6) {
+ val t = 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 first_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) => first_tour_heuristics(dim, x::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) ; "" }))
+}
+*/
+