# HG changeset patch
# User Christian Urban <christian.urban@kcl.ac.uk>
# Date 1612052294 0
# Node ID 0930e4555b6054fee5a3b3b7ff8945e74021b7bd
# Parent  175a950470a96cd19f958cdd73e2e91ae85404b8
added main4 marking

diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight1.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight1.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,177 @@
+// Part 1 about finding and counting Knight's tours
+//==================================================
+
+object CW9a {   // for preparing the jar
+
+type Pos = (Int, Int)    // a position on a chessboard 
+type Path = List[Pos]    // a path...a list of positions
+
+
+// for measuring time in the JAR
+def time_needed[T](code: => T) : T = {
+  val start = System.nanoTime()
+  val result = code
+  val end = System.nanoTime()
+  println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+  result
+}
+
+// for printing a board
+def print_board(dim: Int, path: Path): Unit = {
+  println()
+  for (i <- 0 until dim) {
+    for (j <- 0 until dim) {
+      print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+    }
+    println()
+  } 
+}
+
+def is_legal(dim: Int, path: Path, x: Pos): Boolean = 
+  0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+// testcases
+//assert(is_legal(8, Nil, (3, 4)) == true)
+//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
+//assert(is_legal(2, Nil, (0, 0)) == true)
+
+
+def add_pair(x: Pos, y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+def moves(x: Pos): List[Pos] = 
+  List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),
+       (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair(x, _))
+
+// 1 mark
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
+  moves(x).filter(is_legal(dim, path, _))
+
+
+
+// testcases
+//assert(legal_moves(8, Nil, (2,2)) == 
+//  List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == 
+//  List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0)))
+//assert(legal_moves(1, Nil, (0,0)) == List())
+//assert(legal_moves(2, Nil, (0,0)) == List())
+//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+// 2 marks
+
+def tcount_tours(dim: Int, path: Path): Int = {
+  if (path.length == dim * dim) 1
+  else 
+    (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum
+}
+
+def count_tours(dim: Int, path: Path) =
+  time_needed(tcount_tours(dim: Int, path: Path))
+
+
+def tenum_tours(dim: Int, path: Path): List[Path] = {
+  if (path.length == dim * dim) List(path)
+  else 
+    (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten
+}
+
+def enum_tours(dim: Int, path: Path) =
+  time_needed(tenum_tours(dim: Int, path: Path))
+
+// test cases
+
+/*
+def count_all_tours(dim: Int) = {
+  for (i <- (0 until dim).toList; 
+       j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
+
+def enum_all_tours(dim: Int): List[Path] = {
+  (for (i <- (0 until dim).toList; 
+        j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+
+
+println("Number of tours starting from (0, 0)")
+
+for (dim <- 1 to 5) {
+  println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
+}
+
+println("Number of tours starting from all fields")
+
+for (dim <- 1 to 5) {
+  println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
+}
+
+for (dim <- 1 to 5) {
+  val ts = enum_tours(dim, List((0, 0)))
+  println(s"${dim} x ${dim} ")   
+  if (ts != Nil) {
+    print_board(dim, ts.head)
+    println(ts.head)
+  }
+}
+*/
+
+// 1 mark
+
+def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+  case Nil => None
+  case x::xs => {
+    val result = f(x)
+    if (result.isDefined) result else first(xs, f)
+  }
+}
+
+// test cases
+//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
+//
+//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
+//first(List((1, 0),(2, 0),(3, 0)), foo)
+
+
+// 1 mark
+
+def tfirst_tour(dim: Int, path: Path): Option[Path] = {
+  if (path.length == dim * dim) Some(path)
+  else
+    first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))
+}
+
+def first_tour(dim: Int, path: Path) = 
+  time_needed(tfirst_tour(dim: Int, path: Path))
+
+
+/*
+for (dim <- 1 to 8) {
+  val t = first_tour(dim, List((0, 0)))
+  println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+// 15 secs for 8 x 8
+//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
+//val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
+
+// no result for 4 x 4
+//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
+
+// 0.3 secs for 6 x 6
+//val ts3 = time_needed(0, first_tour(6, List((0, 0))))
+
+// 15 secs for 8 x 8
+//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
+
+
+
+
+
+}
+
+
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight1_test4.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight1_test4.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,7 @@
+import CW9a._
+
+
+val f_urban = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
+
+assert(first(List((1,0),(2,0),(3,0),(4,0)), f_urban) == Some(List((4,0))))
+assert(first(List((1,0),(2,0),(3,0)), f_urban) == None)
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight1_test5.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight1_test5.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,31 @@
+import CW9a._
+
+//type Pos = (Int, Int)    // a position on a chessboard 
+//type Path = List[Pos]    // a path...a list of positions
+
+def add_pair_urban(x: Pos)(y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = 
+  0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] = 
+  List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),
+       (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = 
+  moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+  case Nil => true
+  case x::Nil => true
+  case x::y::p => 
+    if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+val ts1_urban = first_tour(6, List((0, 0))).get
+assert(correct_urban(6)(ts1_urban) == true)
+
+val ts2_urban = first_tour(4, List((0, 0)))
+assert(ts2_urban == None)  
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight2.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight2.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,94 @@
+// Part 3 about finding a single tour using the Warnsdorf Rule
+//=============================================================
+
+object CW9b {
+
+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))
+
+def first_closed_tour_heuristic(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))
+
+def first_tour_heuristic(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 175a950470a9 -r 0930e4555b60 main_marking4/knight2_test.sh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight2_test.sh	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,310 @@
+#!/bin/bash
+
+# to make the script fail safely
+set -euo pipefail
+
+
+out=${1:-output}
+
+echo "" > $out
+
+echo -e `date` >> $out
+echo -e  "" >> $out
+echo "Below is the feedback and provisional marks for your submission" >> $out
+echo "for the Main Part 4 (Scala).  Please note all marks are provisional until" >> $out
+echo "ratified by the assessment board -- this is not an official" >> $out
+echo "results transcript." >> $out
+echo "" >> $out
+
+# marks for core CW9
+marks=$(( 0 ))
+
+# compilation tests
+
+function scala_compile {
+  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out)
+}
+
+# functional tests
+
+function scala_assert {
+  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+function scala_assert_thirty {
+  (ulimit -t 40; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null)  
+}
+
+# purity test
+
+function scala_vars {
+   (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null)
+}
+
+echo -e "" >> $out
+echo -e  "Below is the feedback for your submission knight1.scala" >> $out
+echo -e  "" >> $out
+
+
+# compilation test
+
+echo -e "knight1.scala is present?" | tee -a $out
+
+if [ -f "knight1.scala" ]; then
+    echo -e "  --> success" | tee -a $out
+    tsts=$(( 0 ))
+else 
+    echo -e "  --> knight1.scala is not present\n" | tee -a $out
+    tsts=$(( 1 )) 
+fi
+
+
+
+
+if [ $tsts -eq 0 ]
+then
+    echo -e "knight1.scala runs?" | tee -a $out
+    
+    if (scala_compile knight1.scala)
+    then
+	echo -e "  --> success " | tee -a $out
+	tsts=$(( 0 ))
+    else
+	echo -e "  --> SCALA DID NOT RUN knight1.scala\n" | tee -a $out
+	tsts=$(( 1 )) 
+    fi
+else
+    tsts=$(( 1 ))  
+fi 
+
+# knights1: purity test
+
+
+if [ $tsts -eq 0 ]
+then 
+    echo -e "knight1.scala does not contain VARS, RETURNS etc?" | tee -a $out
+
+    if (scala_vars knight1.scala)
+    then
+	echo -e "  --> TEST FAILED\n" | tee -a $out
+	tsts=$(( 1 ))
+    else
+	echo -e "  --> success" | tee -a $out
+	tsts=$(( 0 )) 
+    fi
+else
+    tsts=$(( 1 ))  
+fi    
+
+
+### knight4 test
+
+if [ $tsts -eq 0 ]
+then
+  echo -e " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " | tee -a $out
+  echo -e "   first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" | tee -a $out
+  echo -e "   first(List((1,0),(2,0),(3,0)), f) == None" | tee -a $out  
+  
+  if (scala_assert "knight1.scala" "knight1_test4.scala") 
+  then
+      echo -e "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
+  else
+      echo -e "  --> ONE OF THE TESTS FAILED\n" | tee -a $out
+  fi
+fi
+
+sleep 4
+
+### knight5 test
+
+if [ $tsts -eq 0 ]
+then
+  echo -e " is first_tour(6, List((0,0))) ok? " | tee -a $out
+  echo -e " is first_tour(4, List((0,0))) == None " | tee -a $out
+  START=$(date +%s)
+  
+  if (scala_assert_thirty "knight1.scala" "knight1_test5.scala") 
+  then
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo -e "  This test ran for $DIFF seconds" | tee -a $out  
+      echo -e "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
+  else
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo -e "  This test ran for $DIFF seconds" | tee -a $out 
+      echo -e "  --> TEST FAILED\n" | tee -a $out
+  fi
+fi
+
+
+echo -e "" >> $out
+echo -e  "Below is the feedback for your submission knight2.scala" >> $out
+echo -e  "" >> $out
+
+
+# knights2: compilation test
+
+echo "knight2.scala runs?" | tee -a $out
+
+if (scala_compile knight2.scala)
+then
+    echo -e "  --> success" | tee -a $out
+    tsts=$(( 0 ))
+else
+    echo -e "  --> SCALA DID NOT RUN knight2.scala\n" | tee -a $out
+    tsts=$(( 1 )) 
+fi
+
+
+
+# knights2: purity test
+#
+if [ $tsts -eq 0 ]
+then 
+    echo "knight2.scala does not VARS, RETURNS etc?" | tee -a $out
+
+    if (scala_vars knight2.scala)
+    then   
+	echo -e "  --> TEST FAILED\n" | tee -a $out
+	tsts=$(( 1 ))
+    else
+	echo -e "  --> success" | tee -a $out
+	tsts=$(( 0 )) 
+    fi
+else
+    tsts=$(( 1 ))  
+fi
+
+
+# ordered move test
+
+if [ $tsts -eq 0 ]
+then
+  echo -e " ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5))" | tee -a $out
+  echo -e " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" | tee -a $out
+  echo -e " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" | tee -a $out
+  
+  if (scala_assert "knight2.scala" "knight2_test6.scala")
+  then
+      echo -e "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
+  else
+      echo -e "  --> ONE OF THE TESTS FAILED\n" | tee -a $out
+  fi
+fi
+
+sleep 4
+
+# first-closed-tour test
+
+if [ $tsts -eq 0 ]
+then
+  echo -e " first_closed_tour_heuristics(6, List((3,3))) found and correct?" | tee -a $out
+  START=$(date +%s)
+  
+  if (scala_assert_thirty "knight2.scala" "knight2_test7.scala")
+  then
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo -e "  This test ran for $DIFF seconds" | tee -a $out 
+      echo -e "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
+  else
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo -e "  This test ran for $DIFF seconds." | tee -a $out 
+      echo -e "  --> TEST FAILED\n" | tee -a $out
+  fi
+fi
+
+sleep 4
+
+# first-tour test
+
+if [ $tsts -eq 0 ]
+then
+  echo -e " first_tour_heuristics(8, List((0,0))) found and correct?" | tee -a $out
+  echo -e " first_tour_heuristics(30, List((0,0))) found and correct?" | tee -a $out
+  START=$(date +%s)
+  
+  if (scala_assert_thirty "knight2.scala" "knight2_test8.scala")
+  then
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo "  This test ran for $DIFF seconds" | tee -a $out
+      echo -e "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
+  else
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo "  This test ran for $DIFF seconds." | tee -a $out
+      echo -e "  --> ONE OF THE TESTS FAILED\n" | tee -a $out
+  fi
+fi
+
+echo -e "" >> $out
+echo -e  "Below is the feedback for your submission knight3.scala" >> $out
+echo -e  "" >> $out
+
+# compilation test
+echo "knight3.scala runs?" | tee -a $out
+
+if (scala_compile knight3.scala)
+then
+    echo "  --> success" | tee -a $out
+    tsts=$(( 0 ))
+else
+    echo -e "  --> SCALA DID NOT RUN knight3.scala\n" | tee -a $out  
+    tsts=$(( 1 )) 
+fi
+
+
+# knights3: purity test
+#
+if [ $tsts -eq 0 ]
+then 
+    echo -e "knight3.scala does not contain VARS, RETURNS etc?" | tee -a $out
+
+    if (scala_vars knight3.scala)
+    then
+	echo "  --> TEST FAILED\n" | tee -a $out
+	tsts=$(( 1 ))
+    else
+	echo "  --> success" | tee -a $out
+	tsts=$(( 0 )) 
+    fi
+else
+    tsts=$(( 1 ))  
+fi
+
+sleep 4
+
+if [ $tsts -eq 0 ]
+then
+  echo -e " tour_on_mega_board(70, List((0,0))) found and correct?" | tee -a $out
+  START=$(date +%s)
+  
+  if (scala_assert_thirty "knight3.scala" "knight3_test9.scala")
+  then
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo -e "  This test ran for $DIFF seconds." | tee -a $out
+      echo -e "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
+  else
+      END=$(date +%s)
+      DIFF=$(( $END - $START ))
+      echo -e "  This test ran for $DIFF seconds." | tee -a $out
+      echo -e "  --> TEST FAILED\n" | tee -a $out 
+  fi
+fi
+
+sleep 4
+
+## final marks
+echo -e "" >> $out
+echo -e "Overall mark for Main Part 4 (Scala)" | tee -a $out
+echo -e "$marks" | tee -a $out
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight2_test6.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight2_test6.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,19 @@
+import CW9b._
+
+assert(ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5)))
+assert(ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2)))
+assert(ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1)))
+
+
+
+/*
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps 
+
+lazy val f = Future {
+}
+
+Await.result(f, 120 second)
+*/
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight2_test7.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight2_test7.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,32 @@
+import CW9b._
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+def add_pair_urban(x: Pos)(y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = 
+  0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] = 
+  List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),
+       (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = 
+  moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+  case Nil => true
+  case x::Nil => true
+  case x::y::p => 
+    if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+def correct_closed_urban(dim: Int)(p: Path) =
+  correct_urban(6)(p) &&  moves_urban(p.head).contains(p.last)
+
+
+val tsc_urban = first_closed_tour_heuristics(6, List((3, 3))).get
+assert(correct_closed_urban(6)(tsc_urban) == true)
+
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight2_test8.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight2_test8.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,32 @@
+import CW9b._
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+def add_pair_urban(x: Pos)(y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = 
+  0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] = 
+  List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),
+       (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = 
+  moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+  case Nil => true
+  case x::Nil => true
+  case x::y::p => 
+    if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+val ts8_urban = first_tour_heuristics(8, List((0,0))).get
+assert(correct_urban(8)(ts8_urban) == true)
+
+val ts30_urban = first_tour_heuristics(30, List((0,0))).get
+assert(correct_urban(30)(ts30_urban) == true)
+
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight3.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight3.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,63 @@
+// Part 3 about finding a single tour using the Warnsdorf Rule
+//=============================================================
+
+object CW9c { 
+
+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))
+
+}
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/knight3_test9.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/knight3_test9.scala	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,29 @@
+import CW9c._
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+def add_pair_urban(x: Pos)(y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = 
+  0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] = 
+  List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),
+       (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = 
+  moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+  case Nil => true
+  case x::Nil => true
+  case x::y::p => 
+    if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+val ts70_urban = tour_on_mega_board(70, List((0,0))).get
+assert(correct_urban(70)(ts70_urban) == true)
+
diff -r 175a950470a9 -r 0930e4555b60 main_marking4/mk
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_marking4/mk	Sun Jan 31 00:18:14 2021 +0000
@@ -0,0 +1,32 @@
+#!/bin/sh
+###set -e
+
+trap "exit" INT
+
+files=${1:-*/main4}
+
+for sd in $files; do
+  cd $sd
+  echo $sd
+  sleep 5
+  touch .
+  cp ../../../../../main_marking4/knight2_test.sh .
+  cp ../../../../../main_marking4/knight1_test4.scala .
+  cp ../../../../../main_marking4/knight1_test5.scala .
+  cp ../../../../../main_marking4/knight2_test6.scala .
+  cp ../../../../../main_marking4/knight2_test7.scala .
+  cp ../../../../../main_marking4/knight2_test8.scala .
+  cp ../../../../../main_marking4/knight3_test9.scala .
+  ./knight2_test.sh output
+  rm knight2_test.sh
+  rm knight1_test4.scala
+  rm knight1_test5.scala
+  rm knight2_test6.scala
+  rm knight2_test7.scala
+  rm knight2_test8.scala
+  rm knight3_test9.scala
+  cd ..
+  cd ..
+done
+
+