17 def add_pair(x: Pos)(y: Pos): Pos = |
17 def add_pair(x: Pos)(y: Pos): Pos = |
18 (x._1 + y._1, x._2 + y._2) |
18 (x._1 + y._1, x._2 + y._2) |
19 |
19 |
20 def is_legal(dim: Int, path: Path)(x: Pos): Boolean = |
20 def is_legal(dim: Int, path: Path)(x: Pos): Boolean = |
21 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) |
21 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) |
|
22 |
|
23 assert(is_legal(8, Nil)((3,4)) == true) |
|
24 assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false) |
|
25 assert(is_legal(2, Nil)((0,0)) == true) |
22 |
26 |
23 def moves(x: Pos): List[Pos] = |
27 def moves(x: Pos): List[Pos] = |
24 List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), |
28 List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), |
25 (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)) |
29 (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)) |
26 |
30 |
48 if (path.length == dim * dim) List(path) |
52 if (path.length == dim * dim) List(path) |
49 else |
53 else |
50 (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten |
54 (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten |
51 } |
55 } |
52 |
56 |
53 def count_all_tours(dim: Int): Int = { |
57 def count_all_tours(dim: Int) = { |
54 (for (i <- (0 until dim).toList; |
58 for (i <- (0 until dim).toList; |
55 j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))).sum |
59 j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) |
56 } |
60 } |
57 |
61 |
58 def enum_all_tours(dim: Int): List[Path] = { |
62 def enum_all_tours(dim: Int): List[Path] = { |
59 (for (i <- (0 until dim).toList; |
63 (for (i <- (0 until dim).toList; |
60 j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten |
64 j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten |
61 } |
65 } |
|
66 |
|
67 |
|
68 def add_pair_urban(x: Pos)(y: Pos): Pos = |
|
69 (x._1 + y._1, x._2 + y._2) |
|
70 |
|
71 def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = |
|
72 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) |
|
73 |
|
74 def moves_urban(x: Pos): List[Pos] = |
|
75 List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), |
|
76 (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x)) |
|
77 |
|
78 def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = |
|
79 moves_urban(x).filter(is_legal_urban(dim, path)) |
|
80 |
|
81 def correct_urban(dim: Int)(p: Path): Boolean = p match { |
|
82 case Nil => true |
|
83 case x::Nil => true |
|
84 case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false |
|
85 } |
|
86 |
|
87 enum_tours(5, List((0, 2))).map(correct_urban(5)).forall(_ == true) |
|
88 |
62 |
89 |
63 for (dim <- 1 to 5) { |
90 for (dim <- 1 to 5) { |
64 println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0)))) |
91 println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0)))) |
65 } |
92 } |
66 |
93 |