1 // Part 1 about finding and counting Knight's tours

     2 //==================================================

     3 

     4 //object CW8a {   // for preparing the jar

     5 

     6 type Pos = (Int, Int)    // a position on a chessboard 

     7 type Path = List[Pos]    // a path...a list of positions

     8 

     9 

    10 // for measuring time in the JAR

    11 def time_needed[T](code: => T) : T = {

    12   val start = System.nanoTime()

    13   val result = code

    14   val end = System.nanoTime()

    15   println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")

    16   result

    17 }

    18 

    19 // for printing a board

    20 def print_board(dim: Int, path: Path): Unit = {

    21   println

    22   for (i <- 0 until dim) {

    23     for (j <- 0 until dim) {

    24       print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")

    25     }

    26     println

    27   } 

    28 }

    29 

    30 def is_legal(dim: Int, path: Path, x: Pos): Boolean = 

    31   0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)

    32 

    33 // testcases

    34 //assert(is_legal(8, Nil, (3, 4)) == true)

    35 //assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)

    36 //assert(is_legal(2, Nil, (0, 0)) == true)

    37 

    38 

    39 def add_pair(x: Pos, y: Pos): Pos = 

    40   (x._1 + y._1, x._2 + y._2)

    41 

    42 def moves(x: Pos): List[Pos] = 

    43   List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),

    44        (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair(x, _))

    45 

    46 // 1 mark

    47 

    48 def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = 

    49   moves(x).filter(is_legal(dim, path, _))

    50 

    51 // testcases

    52 //assert(legal_moves(8, Nil, (2,2)) == 

    53 //  List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))

    54 //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))

    55 //assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == 

    56 //  List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))

    57 //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))

    58 //assert(legal_moves(1, Nil, (0,0)) == List())

    59 //assert(legal_moves(2, Nil, (0,0)) == List())

    60 //assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))

    61 

    62 // 2 marks

    63 

    64 def tcount_tours(dim: Int, path: Path): Int = {

    65   if (path.length == dim * dim) 1

    66   else 

    67     (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum

    68 }

    69 

    70 def count_tours(dim: Int, path: Path) =

    71   time_needed(tcount_tours(dim: Int, path: Path))

    72 

    73 

    74 def tenum_tours(dim: Int, path: Path): List[Path] = {

    75   if (path.length == dim * dim) List(path)

    76   else 

    77     (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten

    78 }

    79 

    80 def enum_tours(dim: Int, path: Path) =

    81   time_needed(tenum_tours(dim: Int, path: Path))

    82 

    83 // test cases

    84 

    85 /*

    86 def count_all_tours(dim: Int) = {

    87   for (i <- (0 until dim).toList; 

    88        j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))

    89 }

    90 

    91 def enum_all_tours(dim: Int): List[Path] = {

    92   (for (i <- (0 until dim).toList; 

    93         j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten

    94 }

    95 

    96 

    97 println("Number of tours starting from (0, 0)")

    98 

    99 for (dim <- 1 to 5) {

   100   println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))

   101 }

   102 

   103 println("Number of tours starting from all fields")

   104 

   105 for (dim <- 1 to 5) {

   106   println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))

   107 }

   108 

   109 for (dim <- 1 to 5) {

   110   val ts = enum_tours(dim, List((0, 0)))

   111   println(s"${dim} x ${dim} ")   

   112   if (ts != Nil) {

   113     print_board(dim, ts.head)

   114     println(ts.head)

   115   }

   116 }

   117 */

   118 

   119 // 1 mark

   120 

   121 def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {

   122   case Nil => None

   123   case x::xs => {

   124     val result = f(x)

   125     if (result.isDefined) result else first(xs, f)

   126   }

   127 }

   128 

   129 // test cases

   130 //def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None

   131 //

   132 //first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)

   133 //first(List((1, 0),(2, 0),(3, 0)), foo)

   134 

   135 

   136 // 1 mark

   137 

   138 def tfirst_tour(dim: Int, path: Path): Option[Path] = {

   139   if (path.length == dim * dim) Some(path)

   140   else

   141     first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))

   142 }

   143 

   144 def first_tour(dim: Int, path: Path) = 

   145   time_needed(tfirst_tour(dim: Int, path: Path))

   146 

   147 

   148 /*

   149 for (dim <- 1 to 8) {

   150   val t = first_tour(dim, List((0, 0)))

   151   println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))

   152 }

   153 */

   154 

   155 // 15 secs for 8 x 8

   156 //val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)

   157 

   158 // no result for 4 x 4

   159 //val ts2 = time_needed(0, first_tour(4, List((0, 0))))

   160 

   161 // 0.3 secs for 6 x 6

   162 //val ts3 = time_needed(0, first_tour(6, List((0, 0))))

   163 

   164 // 15 secs for 8 x 8

   165 //time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))

   166 

   167 

   168 //}

   169 

   170