# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1479057269 0
# Node ID 9cfa37c91444b83679b174dc8709a9d2eb22fb47
# Parent  ba4081c70de42b77142c5a18ef0f4358024f71b1
updated

diff -r ba4081c70de4 -r 9cfa37c91444 progs/knight2.scala
--- a/progs/knight2.scala	Sun Nov 13 11:56:06 2016 +0000
+++ b/progs/knight2.scala	Sun Nov 13 17:14:29 2016 +0000
@@ -1,10 +1,22 @@
-import scala.util._
+
 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.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: List[Pos])(x: Pos): Boolean = 
+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] = {
@@ -12,9 +24,9 @@
        (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair(x))
 }
 
-def legal_moves(dim: Int, path: List[Pos], x: Pos): List[Pos] = {
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
   moves(x).filter(is_legal(dim, path))
-}
+
 
 
 // non-circle tours
@@ -27,20 +39,40 @@
 }
 */
 
-def tour(dim: Int, path: List[Pos]): Int = {
+def tour(dim: Int, path: Path): Int = {
   if (path.length == dim * dim) 1
   else 
-    (for (x <- legal_moves(dim, path, path.head).par) yield tour(dim, x::path)).sum
+    (for (x <- legal_moves(dim, path, path.head) yield tour(dim, x::path))).sum
 }
 
+
+def dtour(dim: Int): List[List[Pos]] = {
+  var counter = 100000000
+
+  def etour(dim: Int, path: List[Pos]): List[List[Pos]] = {
+    counter = counter - 1
+    if (counter <= 0) List() else
+      if (path.length == dim * dim) List(path)
+      else 
+        (for (x <- legal_moves(dim, path, path.head)) yield etour(dim, x::path)).flatten
+  }
+
+  (for (i <- (0 until dim).toList; 
+        j <- (0 until dim).toList) yield etour(dim, List((i, j)))).flatten
+}
+
+
+
 //val n = 8
-val n = 6
+val n = 5
 println(s"number simple tours: n = $n")
 
-println(tour(n, List((0, 0))))
+//println(etour(n, List((0, 0))).size)
+
+
 
-/*
-for (d <- 1 to 6) {
-  println(s"${d} x ${d} " + (for (i <- 0 until d; j <- 0 until d) yield tour(d, List((i, j)))).sum)
-} 
-*/
+for (d <- 9 to 9) {
+  println(s"${d} x ${d} " + dtour(d).length)
+}
+
+