|
160
|
1 |
import scala.annotation.tailrec
|
|
145
|
2 |
object CW7c {
|
|
160
|
3 |
type Pos = (Int, Int) // a position on a chessboard
|
|
|
4 |
type Path = List[Pos] // a path...a list of positions
|
|
145
|
5 |
|
|
160
|
6 |
def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = {
|
|
|
7 |
if((x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)){
|
|
|
8 |
!(path.contains(x))
|
|
|
9 |
} else false
|
|
|
10 |
}
|
|
|
11 |
|
|
|
12 |
def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
|
|
|
13 |
val lst = List( (1,2),(2,1),(2,-1),(1,-2), (-1,-2),(-2,-1),(-2,1),(-1,2) )
|
|
|
14 |
val mapping = lst.map(s => ( s._1 + x._1, s._2 + x._2) )
|
|
|
15 |
for( i <- mapping if ( is_legal(dim,path)(i) )) yield i
|
|
|
16 |
}
|
|
|
17 |
|
|
|
18 |
def ordered_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
|
|
|
19 |
legal_moves(dim,path,x).sortBy(legal_moves(dim,path,_).length )
|
|
145
|
20 |
}
|
|
|
21 |
|
|
160
|
22 |
def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] ={
|
|
|
23 |
if(xs.isEmpty)
|
|
|
24 |
None
|
|
|
25 |
else {
|
|
|
26 |
val b = f(xs.head)
|
|
|
27 |
if (b!=None)
|
|
|
28 |
b
|
|
|
29 |
else
|
|
|
30 |
first(xs.tail,f)
|
|
|
31 |
}
|
|
|
32 |
}
|
|
145
|
33 |
|
|
160
|
34 |
def first_closed_tour_heuristic(dim: Int, path: Path) : Option[Path] = {
|
|
|
35 |
if (dim < 5) None
|
|
|
36 |
else
|
|
|
37 |
if(path.length==dim*dim) Some(path)
|
|
|
38 |
else
|
|
|
39 |
first(ordered_moves(dim,path,path.head),y => first_closed_tour_heuristic(dim, y::path))
|
|
145
|
40 |
}
|
|
160
|
41 |
|
|
145
|
42 |
}
|
|
|
43 |
|
|
|
44 |
|
|
160
|
45 |
first_closed_tour_heuristic(6, List((3, 3)))
|