# HG changeset patch # User Christian Urban # Date 1478134433 0 # Node ID aae25698525156f9c0ac4bc2dbf81a5ed869c4e5 # Parent c1e6123d02f46529942ca6d55310872326b8e385 updated diff -r c1e6123d02f4 -r aae256985251 cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r c1e6123d02f4 -r aae256985251 cws/cw01.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cws/cw01.tex Thu Nov 03 00:53:53 2016 +0000 @@ -0,0 +1,217 @@ +\documentclass{article} +\usepackage{style} +%%\usepackage{../langs} + +\begin{document} + +\section*{Coursework 1 (Strand 1)} + +This coursework is worth 4\% and is due on 25 October at +16:00. You are asked to implement a regular expression matcher +and submit a document containing the answers for the questions +below. You can do the implementation in any programming +language you like, but you need to submit the source code with +which you answered the questions, otherwise a mark of 0\% will +be awarded. You can submit your answers in a txt-file or pdf. +Code send as code. + + + +\subsubsection*{Disclaimer} + +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 + + +\subsubsection*{Task} + +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 + +\[ +\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^* +\] + +\noindent +but also with the following extended regular expressions: + +\begin{center} +\begin{tabular}{ll} +$[c_1 c_2 \ldots c_n]$ & a range of characters\\ +$r^+$ & one or more times $r$\\ +$r^?$ & optional $r$\\ +$r^{\{n,m\}}$ & at least $n$-times $r$ but no more than $m$-times\\ +$\sim{}r$ & not-regular expression of $r$\\ +\end{tabular} +\end{center} + +\noindent In the case of $r^{\{n,m\}}$ you can assume the +convention that $0 \le n \le m$. The meanings of the extended +regular expressions are + +\begin{center} +\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} +$L([c_1 c_2 \ldots c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ +$L(r^+)$ & $\dn$ & $\bigcup_{1\le i}. L(r)^i$\\ +$L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ +$L(r^{\{n,m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\ +$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$ +\end{tabular} +\end{center} + +\noindent whereby in the last clause the set $\Sigma^*$ stands +for the set of \emph{all} strings over the alphabet $\Sigma$ +(in the implementation the alphabet can be just what is +represented by, say, the type \texttt{Char}). So $\sim{}r$ +means `all the strings that $r$ cannot match'. + +Be careful that your implementation of \textit{nullable} and +\textit{der} satisfies for every $r$ the following two +properties (see also Question 2): + +\begin{itemize} +\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$ +\item $L(der\,c\,r) = Der\,c\,(L(r))$ +\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. + + +\subsection*{Question 1} + +What is your King's email address (you will need it in +Question 3)? + +\subsection*{Question 2} + +This question does not require any implementation. From the +lectures you have seen the definitions for the functions +\textit{nullable} and \textit{der} for the basic regular +expressions. Give the rules for the extended regular +expressions: + +\begin{center} +\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +$\textit{nullable}([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ +$\textit{nullable}(r^+)$ & $\dn$ & $?$\\ +$\textit{nullable}(r^?)$ & $\dn$ & $?$\\ +$\textit{nullable}(r^{\{n,m\}})$ & $\dn$ & $?$\\ +$\textit{nullable}(\sim{}r)$ & $\dn$ & $?$\medskip\\ +$der\, c\, ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ +$der\, c\, (r^+)$ & $\dn$ & $?$\\ +$der\, c\, (r^?)$ & $\dn$ & $?$\\ +$der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\ +$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ +\end{tabular} +\end{center} + +\noindent +Remember your definitions have to satisfy the two properties + +\begin{itemize} +\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$ +\item $L(der\,c\,r)) = Der\,c\,(L(r))$ +\end{itemize} + +\subsection*{Question 3} + +Implement the following regular expression for email addresses + +\[ +([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}}) +\] + +\noindent and calculate the derivative according to your email +address. When calculating the derivative, simplify all regular +expressions as much as possible by applying the +following 7 simplification rules: + +\begin{center} +\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll} +$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ +$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ +$r \cdot \ONE$ & $\mapsto$ & $r$\\ +$\ONE \cdot r$ & $\mapsto$ & $r$\\ +$r + \ZERO$ & $\mapsto$ & $r$\\ +$\ZERO + r$ & $\mapsto$ & $r$\\ +$r + r$ & $\mapsto$ & $r$\\ +\end{tabular} +\end{center} + +\noindent Write down your simplified derivative in a readable +notation using parentheses where necessary. That means you +should use the infix notation $+$, $\cdot$, $^*$ and so on, +instead of code. + +\subsection*{Question 4} + +Suppose \textit{[a-z]} stands for the range regular expression +$[a,b,c,\ldots,z]$. Consider the regular expression $/ \cdot * \cdot +(\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * +\cdot /$ and decide wether the following four strings are matched by +this regular expression. Answer yes or no. + +\begin{enumerate} +\item \texttt{"/**/"} +\item \texttt{"/*foobar*/"} +\item \texttt{"/*test*/test*/"} +\item \texttt{"/*test/*test*/"} +\end{enumerate} + +\noindent +Also test your regular expression matcher with the regular +expression $a^{\{3,5\}}$ and the strings + +\begin{enumerate} +\setcounter{enumi}{4} +\item \texttt{aa} +\item \texttt{aaa} +\item \texttt{aaaaa} +\item \texttt{aaaaaa} +\end{enumerate} + +\noindent +Does your matcher produce the expected results? + +\subsection*{Question 5} + +Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be +$(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three +strings consisting of $a$s only can be matched by $(r_1^+)^+$. +Similarly test them with $(r_2^+)^+$. Again answer in all six cases +with yes or no. \medskip + +\noindent +These are strings are meant to be entirely made up of $a$s. Be careful +when copy-and-pasting the strings so as to not forgetting any $a$ and +to not introducing any other character. + +\begin{enumerate} +\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} +\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} +\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} +\end{enumerate} + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff -r c1e6123d02f4 -r aae256985251 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r c1e6123d02f4 -r aae256985251 cws/cw02.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cws/cw02.tex Thu Nov 03 00:53:53 2016 +0000 @@ -0,0 +1,111 @@ +\documentclass{article} +\usepackage{../style} +\usepackage{chessboard} +\usepackage[LSBC4,T1]{fontenc} + + +\begin{document} + +\setchessboard{smallboard, + showmover=false, + boardfontencoding=LSBC4, + hlabelformat=\arabic{ranklabel}, + vlabelformat=\arabic{filelabel}} + + + +\section*{Coursework 2 (Knight's Tour)} + +This coursework is worth XXX\% and is due on 21 November at 16:00. You +are asked to implement a Scala program that solves the \textit{knight's + tour problem} on an $n\times n$ chessboard. This problem is about +finding a tour such that the knight visits every field on the +chessboard once. One a $5\times 5$ chessboard, a knight's tour +is as follows: + +\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 + ] + +\noindent +The tour starts in the left-upper corner, then moves to field $(4,3)$, +then $(5,1)$ and so on. 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 not closed (that is 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 is one on a $6\times +6$ board. + +If you cannot remember how a knight moved in chess, below are all +potential moves indicated for two knights, one on field $(3, 3)$ and +another on $(8, 8)$: + + +\chessboard[color=blue!50, + linewidth=0.2em, + shortenstart=0.5ex, + shortenend=0.5ex, + markstyle=cross, + markfields={b5, d5, a4, e4, a2, e2, b1, d1}, + color=red!50, + markfields={g6, f7}, + setpieces={Nh8, Nc3}] + + +\subsubsection*{Disclaimer} + +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 + + +\subsubsection*{Task} + +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 + +\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. + + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff -r c1e6123d02f4 -r aae256985251 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r c1e6123d02f4 -r aae256985251 cws/cw03.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cws/cw03.tex Thu Nov 03 00:53:53 2016 +0000 @@ -0,0 +1,226 @@ +\documentclass{article} +\usepackage{style} +%%\usepackage{../langs} + +\begin{document} + +\section*{Coursework 3} + +This coursework is worth XXX\% and is due on XXXX at +16:00. You are asked to implement a regular expression matcher. + + + + +\subsubsection*{Disclaimer} + +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 + + +\subsubsection*{Task} + +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} +\begin{tabular}{lcll} + $r$ & $::=$ & $\ZERO$ & cannot match anything\\ + & $|$ & $\ONE$ & can only match the empty string\\ + & $|$ & $c$ & can match a character $c$\\ + & $|$ & $r_1 + r_2$ & can match either with $r_1$ or with $r_2$\\ + & $|$ & $r_1 \cdot r_2$ & can match first with $r_1$ and then with $r_2$\\ + & $|$ & $r^*$ & can match zero or more times $r$\\ + & $|$ & $r^{\{\uparrow n\}}$ & can match zero upto $n$ times $r$\\ + & $|$ & $r^{\{n\}}$ & can match exactly $n$ times $r$\\ +\end{tabular} +\end{center} + +\noindent +Implement a function called \textit{nullable} by recursion over +regular expressions: + +\begin{center} +\begin{tabular}{lcl} +$\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\ +$\textit{nullable}(\ONE)$ & $\dn$ & $\textit{true}$\\ +$\textit{nullable}(c)$ & $\dn$ & $\textit{false}$\\ +$\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\ +$\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\ +$\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\ +$\textit{nullable}(r^{\{\uparrow n\}})$ & $\dn$ & $\textit{true}$\\ +$\textit{nullable}(r^{\{n\}})$ & $\dn$ & + $\textit{if}\;n = 0\; \textit{then} \; \textit{true} \; \textit{else} \; \textit{nullable}(r)$\\ +\end{tabular} +\end{center} + +\begin{center} +\begin{tabular}{lcl} +$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\ +$\textit{der}\;c\;(\ONE)$ & $\dn$ & $\ZERO$\\ +$\textit{der}\;c\;(d)$ & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\ +$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\ +$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\ + & & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\ + & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\ +$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\ +$\textit{der}\;c\;(r^{\{\uparrow n\}})$ & $\dn$ & $\textit{if}\;n = 0\;\textit{then}\;\ZERO\;\text{else}\; + (\textit{der}\;c\;r)\cdot (r^{\{\uparrow n-1\}})$\\ +$\textit{der}\;c\;(r^{\{n\}})$ & $\dn$ & + $\textit{if}\;n = 0\; \textit{then} \; \ZERO\; \textit{else}\;$\\ + & & $\textit{if} \;\textit{nullable}(r)\;\textit{then}\;(\textit{der}\;c\;r)\cdot (r^{\{\uparrow n-1\}})$\\ + & & $\textit{else}\;(\textit{der}\;c\;r)\cdot (r^{\{n-1\}})$ +\end{tabular} +\end{center} + + +Be careful that your implementation of \textit{nullable} and +\textit{der}\;c\; satisfies for every $r$ the following two +properties (see also Question 2): + +\begin{itemize} +\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$ +\item $L(der\,c\,r) = Der\,c\,(L(r))$ +\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}\;c\; for the extended regular +expressions. + + +\subsection*{Question 1} + +What is your King's email address (you will need it in +Question 3)? + +\subsection*{Question 2} + +This question does not require any implementation. From the +lectures you have seen the definitions for the functions +\textit{nullable} and \textit{der}\;c\; for the basic regular +expressions. Give the rules for the extended regular +expressions: + +\begin{center} +\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +$\textit{nullable}([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ +$\textit{nullable}(r^+)$ & $\dn$ & $?$\\ +$\textit{nullable}(r^?)$ & $\dn$ & $?$\\ +$\textit{nullable}(r^{\{n,m\}})$ & $\dn$ & $?$\\ +$\textit{nullable}(\sim{}r)$ & $\dn$ & $?$\medskip\\ +$der\, c\, ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ +$der\, c\, (r^+)$ & $\dn$ & $?$\\ +$der\, c\, (r^?)$ & $\dn$ & $?$\\ +$der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\ +$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ +\end{tabular} +\end{center} + +\noindent +Remember your definitions have to satisfy the two properties + +\begin{itemize} +\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$ +\item $L(der\,c\,r)) = Der\,c\,(L(r))$ +\end{itemize} + +\subsection*{Question 3} + +Implement the following regular expression for email addresses + +\[ +([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}}) +\] + +\noindent and calculate the derivative according to your email +address. When calculating the derivative, simplify all regular +expressions as much as possible by applying the +following 7 simplification rules: + +\begin{center} +\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll} +$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ +$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ +$r \cdot \ONE$ & $\mapsto$ & $r$\\ +$\ONE \cdot r$ & $\mapsto$ & $r$\\ +$r + \ZERO$ & $\mapsto$ & $r$\\ +$\ZERO + r$ & $\mapsto$ & $r$\\ +$r + r$ & $\mapsto$ & $r$\\ +\end{tabular} +\end{center} + +\noindent Write down your simplified derivative in a readable +notation using parentheses where necessary. That means you +should use the infix notation $+$, $\cdot$, $^*$ and so on, +instead of code. + +\subsection*{Question 4} + +Suppose \textit{[a-z]} stands for the range regular expression +$[a,b,c,\ldots,z]$. Consider the regular expression $/ \cdot * \cdot +(\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * +\cdot /$ and decide wether the following four strings are matched by +this regular expression. Answer yes or no. + +\begin{enumerate} +\item \texttt{"/**/"} +\item \texttt{"/*foobar*/"} +\item \texttt{"/*test*/test*/"} +\item \texttt{"/*test/*test*/"} +\end{enumerate} + +\noindent +Also test your regular expression matcher with the regular +expression $a^{\{3,5\}}$ and the strings + +\begin{enumerate} +\setcounter{enumi}{4} +\item \texttt{aa} +\item \texttt{aaa} +\item \texttt{aaaaa} +\item \texttt{aaaaaa} +\end{enumerate} + +\noindent +Does your matcher produce the expected results? + +\subsection*{Question 5} + +Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be +$(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three +strings consisting of $a$s only can be matched by $(r_1^+)^+$. +Similarly test them with $(r_2^+)^+$. Again answer in all six cases +with yes or no. \medskip + +\noindent +These are strings are meant to be entirely made up of $a$s. Be careful +when copy-and-pasting the strings so as to not forgetting any $a$ and +to not introducing any other character. + +\begin{enumerate} +\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} +\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} +\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ +aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} +\end{enumerate} + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff -r c1e6123d02f4 -r aae256985251 progs/knight2.scala --- a/progs/knight2.scala Wed Nov 02 13:26:26 2016 +0000 +++ b/progs/knight2.scala Thu Nov 03 00:53:53 2016 +0000 @@ -24,22 +24,15 @@ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n)) } -def ordered_moves(n: Int)(steps: List[Pos])(x : Pos): List[Pos] = - moves(n)(x).sortBy((x: Pos) => moves(n)(x).filterNot(steps.contains(_)).length) - -moves(8)(1,3) -ordered_moves(8)(Nil)(1,3) -ordered_moves(8)(List((2, 4), (2, 6)))(1,3) - -// non-circle tour -def tour(n: Int)(steps: List[Pos]): Unit = { - if (steps.length == n * n) - print_board(n)(steps) +// non-circle tours +def tour(n: Int)(steps: List[Pos]): List[List[Pos]] = { + if (steps.length == n * n) List(steps) else - for (x <- moves(n)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps) + (for (x <- moves(n)(steps.head); if (!steps.contains(x))) yield tour(n)(x :: steps)).flatten } -val n = 8 -println(s"simple tour: n = $n") +//val n = 8 +val n = 6 +println(s"number simple tours: n = $n") -for (i <- 0 until n; j <- 0 until n) tour(n)(List((i, j))) +println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size)