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