|
331
|
1 |
import CW8b._
|
|
258
|
2 |
|
|
|
3 |
//type Pos = (Int, Int)
|
|
|
4 |
//type Path = List[Pos]
|
|
|
5 |
|
|
|
6 |
def add_pair_urban(x: Pos)(y: Pos): Pos =
|
|
|
7 |
(x._1 + y._1, x._2 + y._2)
|
|
|
8 |
|
|
|
9 |
def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
|
|
|
10 |
0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
|
|
|
11 |
|
|
|
12 |
def moves_urban(x: Pos): List[Pos] =
|
|
|
13 |
List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
|
|
|
14 |
(-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
|
|
|
15 |
|
|
|
16 |
def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
|
|
|
17 |
moves_urban(x).filter(is_legal_urban(dim, path))
|
|
|
18 |
|
|
|
19 |
def correct_urban(dim: Int)(p: Path): Boolean = p match {
|
|
|
20 |
case Nil => true
|
|
|
21 |
case x::Nil => true
|
|
|
22 |
case x::y::p =>
|
|
|
23 |
if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
|
|
|
24 |
}
|
|
|
25 |
|
|
|
26 |
def correct_closed_urban(dim: Int)(p: Path) =
|
|
|
27 |
correct_urban(6)(p) && moves_urban(p.head).contains(p.last)
|
|
|
28 |
|
|
|
29 |
|
|
331
|
30 |
val tsc_urban = first_closed_tour_heuristics(6, List((3, 3))).get
|
|
|
31 |
assert(correct_closed_urban(6)(tsc_urban) == true)
|
|
258
|
32 |
|