|
1 import scala.util._ |
|
2 |
|
3 type Pos = (Int, Int) |
|
4 |
|
5 |
|
6 def print_board(n: Int)(steps: List[Pos]): Unit = { |
|
7 for (i <- 0 until n) { |
|
8 for (j <- 0 until n) { |
|
9 print(f"${steps.reverse.indexOf((i, j))}%3.0f ") |
|
10 } |
|
11 println |
|
12 } |
|
13 } |
|
14 |
|
15 def add_pair(x: Pos)(y: Pos) = |
|
16 (x._1 + y._1, x._2 + y._2) |
|
17 |
|
18 def dist(n: Int)(y: Pos) = |
|
19 (n / 2 - y._1).abs + (n / 2 - y._2).abs |
|
20 |
|
21 def is_legal(n: Int)(x: Pos) = |
|
22 0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n |
|
23 |
|
24 def moves(n: Int)(x: Pos): List[Pos] = { |
|
25 List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), |
|
26 (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n)) |
|
27 } |
|
28 |
|
29 def moves_filtered(n: Int)(steps: List[Pos])(x: Pos): List[Pos] = { |
|
30 moves(n)(x).filterNot(steps.contains(_)) |
|
31 } |
|
32 |
|
33 def ordered_moves(n: Int)(steps: List[Pos])(x: Pos): List[Pos] = |
|
34 moves_filtered(n)(steps)(x).sortBy((x: Pos) => (moves_filtered(n)(steps)(x).length, dist(n)(x))) |
|
35 |
|
36 /*def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = xs match { |
|
37 case Nil => None |
|
38 case x::xs => { |
|
39 val result = f(x) |
|
40 if (result.isDefined) result else first(xs, f) |
|
41 } |
|
42 }*/ |
|
43 |
|
44 def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = |
|
45 xs.par.flatMap(f(_)).headOption |
|
46 |
|
47 // non-circle tours, including distance |
|
48 def tour(n: Int)(steps: List[Pos]): Option[List[Pos]] = { |
|
49 if (steps.length == n * n) //&& moves(n)(steps.head).contains(steps.last)) |
|
50 Some(steps) |
|
51 else first(ordered_moves(n)(steps)(steps.head), (x: Pos) => tour(n)(x::steps)) |
|
52 } |
|
53 |
|
54 //val n = 8 |
|
55 val n = 6 |
|
56 println(s"number simple tours: n = $n") |
|
57 |
|
58 println(print_board(n)((tour(n)(List((0, 0)))).get)) |
|
59 //println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size) |
|
60 |
|
61 |
|
62 |
|
63 |
|
64 |
|
65 /* |
|
66 def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = |
|
67 xs.view.flatMap(f(_)).headOption |
|
68 */ |
|
69 |
|
70 /* |
|
71 |
|
72 */ |