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

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

     3 

     4 

     5 

     6 type Pos = (Int, Int)

     7 type Path = List[Pos]

     8 

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

    10   println

    11   for (i <- 0 until dim) {

    12     for (j <- 0 until dim) {

    13       print(f"${path.reverse.indexOf((i, j))}%3.0f ")

    14     }

    15     println

    16   } 

    17 }

    18 

    19 def add_pair(x: Pos)(y: Pos): Pos = 

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

    21 

    22 def dist(dim: Int, y: Pos) = 

    23   (dim / 2 - y._1).abs + (dim / 2 - y._2).abs

    24 

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

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

    27 

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

    29   List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),

    30        (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair(x))

    31 

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

    33   moves(x).filter(is_legal(dim, path))

    34 

    35 

    36 def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = 

    37   legal_moves(dim, path, x).sortBy((x) => (legal_moves(dim, path, x).length, dist(dim, x)))

    38 

    39 

    40 //moves(8)(1,3)

    41 //ordered_moves(8)(Nil)(1,3)

    42 //ordered_moves(8)(List((2, 4), (2, 6)))(1,3)

    43 

    44 

    45 

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

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

    48   else 

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

    50 }

    51 

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

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

    54   else 

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

    56 }

    57 

    58 def count_all_tours(dim: Int): Int = {

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

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

    61 }

    62 

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

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

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

    66 }

    67 

    68 /*

    69 for (dim <- 1 to 5) {

    70   println(s"${dim} x ${dim} " + count_all_tours(dim))

    71 }

    72 

    73 for (dim <- 1 to 5) {

    74   val ts = enum_all_tours(dim)

    75   println(s"${dim} x ${dim} " + (if (ts == Nil) "" else { print_board(dim, ts.head) ; "" }))

    76 }

    77 */

    78 

    79 

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

    81   case Nil => None

    82   case x::xs => {

    83     val result = f(x)

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

    85   }

    86 }

    87 

    88 

    89 

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

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

    92   else

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

    94 }

    95 

    96 for (dim <- 1 to 8) {

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

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

    99 }

   100  

   101 

   102 /*

   103 def first2[A, B](xs: List[A], f: A => Option[B]): Option[B] =

   104   xs.par.flatMap(f(_)).headOption

   105 */

   106 

   107 def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = {

   108   if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)

   109   else

   110     first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path))

   111 }

   112 

   113  

   114 for (dim <- 1 to 6) {

   115   val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2)))

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

   117 }

   118 

   119 

   120 def first_tour_heuristics(dim: Int, path: Path): Option[Path] = {

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

   122   else

   123     first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path))

   124 }

   125 

   126 /*

   127 for (dim <- 1 to 50) {

   128   val t = first_tour_heuristics(dim, List((dim / 2, dim / 2)))

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

   130 }

   131 */

   132