--- a/main_solution4/knight3.scala Sat Nov 04 18:53:37 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,73 +0,0 @@
-// Part 3 about finding a single tour using the Warnsdorf Rule
-//=============================================================
-
-object M4c { // for preparing the jar
-
-type Pos = (Int, Int)
-type Path = List[Pos]
-
-
-// for measuring time in the JAR
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-
-def print_board(dim: Int, path: Path): Unit = {
- println()
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((i, j))}%4.0f ")
- }
- println()
- }
-}
-
-def add_pair(x: Pos, y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal(dim: Int, path: Path, x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _))
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- moves(x).filter(is_legal(dim, path, _))
-
-def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
-
-import scala.annotation.tailrec
-
-@tailrec
-def tour_on_mega_board_aux(dim: Int, paths: List[Path]): Option[Path] = paths match {
- case Nil => None
- case (path::rest) =>
- if (path.length == dim * dim) Some(path)
- else tour_on_mega_board_aux(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest)
-}
-
-def ttour_on_mega_board(dim: Int, path: Path): Option[Path] =
- tour_on_mega_board_aux(dim, List(path))
-
-
-def tour_on_mega_board(dim: Int, path: Path) =
- time_needed(ttour_on_mega_board(dim: Int, path: Path))
-
-
-// testcases
-//print_board(70, tour_on_mega_board(70, List((0, 0))).get)
-
-
-}
-
-
-//val dim = 66 //75
-M4c.print_board(30, M4c.tour_on_mega_board(30, List((0, 0))).get)
-M4c.print_board(66, M4c.tour_on_mega_board(66, List((0, 0))).get)