1 // Part 1 about finding Knight's tours

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

     3 

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

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

     6 

     7 // for measuring time

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

     9   val start = System.nanoTime()

    10   val result = code

    11   val end = System.nanoTime()

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

    13   result

    14 }

    15 

    16 // for printing a board

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

    18   println

    19   for (i <- 0 until dim) {

    20     for (j <- 0 until dim) {

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

    22     }

    23     println

    24   } 

    25 }

    26 

    27 

    28 // 1 mark

    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 assert(is_legal(8, Nil, (3, 4)) == true)

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

    35 assert(is_legal(2, Nil, (0, 0)) == true)

    36 

    37 

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

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

    40 

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

    42   List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),

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

    44 

    45 // 1 mark

    46 

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

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

    49 

    50 assert(legal_moves(8, Nil, (2,2)) == 

    51   List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))

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

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

    54   List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))

    55 assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))

    56 assert(legal_moves(1, Nil, (0,0)) == List())

    57 assert(legal_moves(2, Nil, (0,0)) == List())

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

    59 

    60 // 2 marks

    61 

    62 def count_tours(dim: Int, path: Path): Int = {

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

    64   else 

    65     (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum

    66 }

    67 

    68 def enum_tours(dim: Int, path: Path): List[Path] = {

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

    70   else 

    71     (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten

    72 }

    73 

    74 // as far as tasks go

    75 // test cases for CW

    76 

    77 

    78 

    79 def count_all_tours(dim: Int) = {

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

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

    82 }

    83 

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

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

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

    87 }

    88 

    89 

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

    91 

    92 for (dim <- 1 to 5) {

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

    94 }

    95 

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

    97 

    98 for (dim <- 1 to 5) {

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

   100 }

   101 

   102 for (dim <- 1 to 5) {

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

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

   105   if (ts != Nil) {

   106     print_board(dim, ts.head)

   107     println(ts.head)

   108   }

   109 }

   110 

   111 

   112 // 1 mark

   113 

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

   115   case Nil => None

   116   case x::xs => {

   117     val result = f(x)

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

   119   }

   120 }

   121 

   122 // test cases

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

   124 

   125 first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)

   126 first(List((1, 0),(2, 0),(3, 0)), foo)

   127 

   128 

   129 // 1 mark

   130 

   131 def first_tour(dim: Int, path: Path): Option[Path] = {

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

   133   else

   134     first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))

   135 }

   136 

   137 

   138 

   139 /*

   140 for (dim <- 1 to 8) {

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

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

   143 }

   144 */

   145 

   146 // 15 secs for 8 x 8

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

   148 

   149 // no result for 4 x 4

   150 val ts2 = time_needed(0, first_tour(4, List((0, 0))))

   151 

   152 // 0.3 secs for 6 x 6

   153 val ts3 = time_needed(0, first_tour(6, List((0, 0))))

   154 

   155 // 15 secs for 8 x 8

   156 time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))

   157