diff -r c3d3461a5e77 -r e3878cdd38bc marking3/marking2/knight1.scala --- a/marking3/marking2/knight1.scala Tue Feb 04 11:20:31 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,79 +0,0 @@ -// Part 1 about finding and counting Knight's tours -//================================================== - -object CW7a { - -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions - -def print_board(dim: Int, path: Path): Unit = { - println - for (i <- 0 until dim) { - for (j <- 0 until dim) { - print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.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) - -assert(is_legal(8, Nil)((3,4)) == true) -assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false) -assert(is_legal(2, Nil)((0,0)) == true) - - - -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 count_tours(dim: Int, path: Path): Int = { - if (path.length == dim * dim) 1 - else - (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum -} - -def enum_tours(dim: Int, path: Path): List[Path] = { - if (path.length == dim * dim) List(path) - else - (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten -} - -def count_all_tours(dim: Int) = { - for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) -} - -def enum_all_tours(dim: Int): List[Path] = { - (for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten -} - -/* -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0)))) -} - -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + count_all_tours(dim)) -} - -for (dim <- 1 to 5) { - val ts = enum_tours(dim, List((0, 0))) - println(s"${dim} x ${dim} ") - if (ts != Nil) { - print_board(dim, ts.head) - println(ts.head) - } -} -*/ - -}