|
4
|
1 |
import scala.util._
|
|
5
|
2 |
type Pos = (Int, Int)
|
|
4
|
3 |
|
|
5
|
4 |
|
|
|
5 |
def print_board(n: Int)(steps: List[Pos]): Unit = {
|
|
4
|
6 |
for (i <- 0 until n) {
|
|
|
7 |
for (j <- 0 until n) {
|
|
|
8 |
print(f"${steps.indexOf((i, j))}%3.0f ")
|
|
|
9 |
}
|
|
|
10 |
println
|
|
|
11 |
}
|
|
|
12 |
//readLine()
|
|
|
13 |
System.exit(0)
|
|
|
14 |
}
|
|
|
15 |
|
|
5
|
16 |
def add_pair(x: Pos)(y: Pos) =
|
|
4
|
17 |
(x._1 + y._1, x._2 + y._2)
|
|
|
18 |
|
|
5
|
19 |
def is_legal(n: Int)(x: Pos) =
|
|
4
|
20 |
0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n
|
|
|
21 |
|
|
5
|
22 |
def moves(n: Int)(x: Pos): List[Pos] = {
|
|
4
|
23 |
List((1, 2),(2, 1),(2, -1),(1, -2),
|
|
|
24 |
(-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)).filter(is_legal(n))
|
|
|
25 |
}
|
|
|
26 |
|
|
6
|
27 |
// non-circle tours
|
|
|
28 |
def tour(n: Int)(steps: List[Pos]): List[List[Pos]] = {
|
|
39
|
29 |
if (steps.length == n * n) // && moves(n)(steps.head).contains(steps.last))
|
|
|
30 |
List(steps)
|
|
4
|
31 |
else
|
|
39
|
32 |
(for (x <- moves(n)(steps.head).par;
|
|
|
33 |
if (!steps.contains(x))) yield tour(n)(x :: steps)).toList.flatten
|
|
4
|
34 |
}
|
|
|
35 |
|
|
6
|
36 |
//val n = 8
|
|
|
37 |
val n = 6
|
|
|
38 |
println(s"number simple tours: n = $n")
|
|
4
|
39 |
|
|
8
|
40 |
println(tour(n)(List((1,1))).distinct.size)
|
|
|
41 |
//println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size)
|