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