main_solution4/knight3.scala
author Christian Urban <christian.urban@kcl.ac.uk>
Mon, 08 Nov 2021 00:17:50 +0000
changeset 400 e48ea8300b2d
parent 379 5616b45d656f
child 418 fa7f7144f2bb
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
213
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     1
// Part 3 about finding a single tour using the Warnsdorf Rule
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     2
//=============================================================
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
400
e48ea8300b2d updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 379
diff changeset
     4
object M4c { // for preparing the jar
213
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     5
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
type Pos = (Int, Int)
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     7
type Path = List[Pos]
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     8
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    10
// for measuring time in the JAR
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    11
def time_needed[T](code: => T) : T = {
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    12
  val start = System.nanoTime()
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    13
  val result = code
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    14
  val end = System.nanoTime()
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    15
  println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    16
  result
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    17
}
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    18
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    19
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    20
def print_board(dim: Int, path: Path): Unit = {
347
4de31fdc0d67 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 213
diff changeset
    21
  println()
213
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    22
  for (i <- 0 until dim) {
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    23
    for (j <- 0 until dim) {
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    24
      print(f"${path.reverse.indexOf((i, j))}%4.0f ")
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
    }
347
4de31fdc0d67 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 213
diff changeset
    26
    println()
213
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    27
  } 
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    28
}
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    29
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    30
def add_pair(x: Pos, y: Pos): Pos = 
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    31
  (x._1 + y._1, x._2 + y._2)
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    32
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    33
def is_legal(dim: Int, path: Path, x: Pos): Boolean = 
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    34
  0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    35
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    36
def moves(x: Pos): List[Pos] = 
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    37
  List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    38
       (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair(x, _))
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    39
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    40
def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    41
  moves(x).filter(is_legal(dim, path, _))
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    42
 
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    43
def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    44
  legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    45
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    46
import scala.annotation.tailrec
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    47
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    48
@tailrec
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    49
def tour_on_mega_board_aux(dim: Int, paths: List[Path]): Option[Path] = paths match {
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    50
  case Nil => None
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    51
  case (path::rest) =>
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    52
    if (path.length == dim * dim) Some(path)
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    53
    else tour_on_mega_board_aux(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest)
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    54
}
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    55
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    56
def ttour_on_mega_board(dim: Int, path: Path): Option[Path] =
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    57
  tour_on_mega_board_aux(dim, List(path))
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    58
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    59
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    60
def tour_on_mega_board(dim: Int, path: Path) =
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    61
  time_needed(ttour_on_mega_board(dim: Int, path: Path))
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    62
379
5616b45d656f updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 347
diff changeset
    63
400
e48ea8300b2d updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 379
diff changeset
    64
// testcases
e48ea8300b2d updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 379
diff changeset
    65
//print_board(70, tour_on_mega_board(70, List((0, 0))).get)
379
5616b45d656f updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 347
diff changeset
    66
213
f968188d4a9b updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    67
}