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

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

     3 

     4 object CW9a {   // 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 

    52 

    53 // testcases

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

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

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

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

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

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

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

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

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

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

    64 

    65 // 2 marks

    66 

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

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

    69   else 

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

    71 }

    72 

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

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

    75 

    76 

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

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

    79   else 

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

    81 }

    82 

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

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

    85 

    86 // test cases

    87 

    88 /*

    89 def count_all_tours(dim: Int) = {

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

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

    92 }

    93 

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

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

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

    97 }

    98 

    99 

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

   101 

   102 for (dim <- 1 to 5) {

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

   104 }

   105 

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

   107 

   108 for (dim <- 1 to 5) {

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

   110 }

   111 

   112 for (dim <- 1 to 5) {

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

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

   115   if (ts != Nil) {

   116     print_board(dim, ts.head)

   117     println(ts.head)

   118   }

   119 }

   120 */

   121 

   122 // 1 mark

   123 

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

   125   case Nil => None

   126   case x::xs => {

   127     val result = f(x)

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

   129   }

   130 }

   131 

   132 // test cases

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

   134 //

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

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

   137 

   138 

   139 // 1 mark

   140 

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

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

   143   else

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

   145 }

   146 

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

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

   149 

   150 

   151 /*

   152 for (dim <- 1 to 8) {

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

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

   155 }

   156 */

   157 

   158 // 15 secs for 8 x 8

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

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

   161 

   162 // no result for 4 x 4

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

   164 

   165 // 0.3 secs for 6 x 6

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

   167 

   168 // 15 secs for 8 x 8

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

   170 

   171 

   172 

   173 

   174 

   175 }

   176 

   177