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

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

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

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

     3 

     3 

     5 

     5 

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

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

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

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

     8 

     8 

     9 

     9 

    41 

    41 

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

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

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

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

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

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

    45 

    45 

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

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

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

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

    50 

    48 

    51 

    49 

    52 

    50 

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

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

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

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

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

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

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

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

    64 

    62 

    66 

    63 

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

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

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

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

    69   else 

    66   else 

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

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

   117     println(ts.head)

   114     println(ts.head)

   118   }

   115   }

   119 }

   116 }

   120 */

   117 */

   121 

   118 

   123 

   119 

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

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

   125   case Nil => None

   121   case Nil => None

   126   case x::xs => {

   122   case x::xs => {

   127     val result = f(x)

   123     val result = f(x)

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

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

   134 //

   130 //

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

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

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

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

   137 

   133 

   140 

   134 

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

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

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

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

   143   else

   137   else

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

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

   155 }

   149 }

   156 */

   150 */

   157 

   151 

   158 // 15 secs for 8 x 8

   152 // 15 secs for 8 x 8

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

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

   161 

   155 

   162 // no result for 4 x 4

   156 // no result for 4 x 4

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

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

   164 

   158 

   165 // 0.3 secs for 6 x 6

   159 // 0.3 secs for 6 x 6