# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1477920076 0
# Node ID 575a5c07c7fee51c90e30016b79f63358fd6780b
# Parent  e0ec73c462c71c62693062fba26163e245882482
updated

diff -r e0ec73c462c7 -r 575a5c07c7fe progs/knight.scala
--- a/progs/knight.scala	Mon Oct 31 10:43:11 2016 +0000
+++ b/progs/knight.scala	Mon Oct 31 13:21:16 2016 +0000
@@ -1,14 +1,15 @@
-
+import scala.util._
 
 def print_board(n: Int)(steps: List[(Int, Int)]): Unit = {
   for (i <- 0 until n) {
     for (j <- 0 until n) {
-      print(f"${steps.indexOf((i, j))}%2.0f ")
+      print(f"${steps.indexOf((i, j))}%3.0f ")
     }
     println
   } 
   //readLine()
-  System.exit(0)
+  //System.exit(0)
+  throw new Exception("\n")
 }
 
 def add_pair(x: (Int, Int))(y: (Int, Int)) = 
@@ -22,15 +23,66 @@
        (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
 }
 
+def ordered_moves(n: Int)(steps: List[(Int, Int)])(x : (Int, Int)): List[(Int, Int)] = 
+  moves(n)(x).sortBy((x: (Int, Int)) => 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 parallel
 def tour(n: Int)(steps: List[(Int, Int)]): Unit = {
-  if (steps.length ==  n * n && moves(n)(steps.head).contains(steps.last))
+  if (steps.length ==  n * n)
     print_board(n)(steps)
   else 
     for (x <- moves(n)(steps.head); if (!steps.contains(x))) tour(n)(x :: steps)
 }
 
-val n = 6
+// non-circle tour
+def ctour(n: Int)(steps: List[(Int, Int)]): Unit = {
+  if (steps.length ==  n * n && moves(n)(steps.head).contains(steps.last))
+    print_board(n)(steps)
+  else 
+    for (x <- moves(n)(steps.head).par; if (!steps.contains(x))) ctour(n)(x :: steps)
+}
+
+
+def faster_tour(n: Int)(steps: List[(Int, Int)]): Unit = {
+  if (steps.length ==  n * n && moves(n)(steps.head).contains(steps.last))
+    print_board(n)(steps)
+  else 
+    for (x <- ordered_moves(n)(steps)(steps.head).par; if (!steps.contains(x))) faster_tour(n)(x :: steps)
+}
+
+
+val n1 = 5
+println(s"simple tour: n = $n1")
 
-println("started")
-for (i <- 0 until n; j <- 0 until n) tour(n)(List((i, j)))
+Try {
+  for (i <- 0 until n1; j <- 0 until n1) {
+    tour(n1)(List((i, j))) 
+  }
+}
+
+
+/*
+val n2 = 6
+println(s"circle tour: n = $n2")
+
+Try {
+  for (i <- 0 until n2; j <- 0 until n2) {
+    ctour(n2)(List((i, j))) 
+  }
+}
+*/
+
+val n3 = 9
+println(s"fast circle tour: n = $n3")
+
+Try {
+  for (i <- 0 until n3; j <- 0 until n3) {
+    faster_tour(n3)(List((i, j))) 
+  }
+}
+
 println("finished")