29 moves(x).filter(is_legal(dim, path)) |
29 moves(x).filter(is_legal(dim, path)) |
30 |
30 |
31 def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = |
31 def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = |
32 legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) |
32 legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) |
33 |
33 |
|
34 import scala.annotation.tailrec |
34 |
35 |
|
36 /* |
|
37 @tailrec |
35 def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { |
38 def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { |
36 case Nil => None |
39 case Nil => None |
37 case x::xs => { |
40 case x::xs => { |
38 val result = f(x) |
41 val result = f(x) |
39 if (result.isDefined) result else first(xs, f) |
42 if (result.isDefined) result else first(xs, f) |
40 } |
43 } |
41 } |
44 } |
|
45 */ |
|
46 |
|
47 def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = |
|
48 xs.flatMap(f(_)).headOption |
42 |
49 |
43 |
50 |
44 def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { |
51 def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { |
45 if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path) |
52 if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path) |
46 else |
53 else |
47 first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path)) |
54 first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path)) |
48 } |
55 } |
49 |
56 |
|
57 /* |
50 for (dim <- 1 to 6) { |
58 for (dim <- 1 to 6) { |
51 val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))) |
59 val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))) |
52 println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) |
60 println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) |
53 } |
61 } |
|
62 */ |
|
63 |
|
64 //@tailrec |
|
65 def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { |
|
66 |
|
67 @tailrec |
|
68 def aux(dim: Int, path: Path, moves: List[Position]): Option[Path |
|
69 if (path.length == dim * dim) Some(path) |
|
70 else |
|
71 moves match { |
|
72 case Nil => None |
|
73 case x::xs => { |
|
74 val r = first_tour_heuristics(dim, x::path) |
|
75 if (r.isDefined) Some(r) else aux(dim, path, xs) |
|
76 } |
|
77 aux(dim, path, ordered_moves(dim, path, path.head)) |
|
78 } |
54 |
79 |
55 |
80 |
|
81 /* |
56 def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { |
82 def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { |
57 if (path.length == dim * dim) Some(path) |
83 if (path.length == dim * dim) Some(path) |
58 else |
84 else |
59 first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path)) |
85 for (p <- ordered_moves(dim, path, path.head)) |
|
86 val r = first_tour_heuristics(dim, x::path) |
|
87 //first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path)) |
|
88 ordered_moves(dim, path, path.head).view.flatMap((x: Pos) => first_tour_heuristics(dim, x::path)).headOption |
60 } |
89 } |
|
90 */ |
61 |
91 |
|
92 /* |
62 for (dim <- 1 to 50) { |
93 for (dim <- 1 to 50) { |
63 val t = first_tour_heuristics(dim, List((dim / 2, dim / 2))) |
94 val t = first_tour_heuristics(dim, List((dim / 2, dim / 2))) |
64 println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) |
95 println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) |
65 } |
96 } |
|
97 */ |
|
98 |
|
99 print_board(50, first_tour_heuristics(50, (25,25)::Nil).get) |